Java教程

【xsong说算法】第一期:排序算法

本文主要是介绍【xsong说算法】第一期:排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

第一章:排序算法

1.1 选择排序

选择排序无论什么数据进去都是 O(N²) 的时间复杂度,唯一好处就是不占用额外的存储空间

算法思路步骤

首先先找到最大(小) 的元素,存放起始位置,重复找最小的往后排,直到所有的元素排序完毕

  • 下面是代码演示:
    /**
     * 使用选择排序解题
     *
     * @param nums 数组
     * @return 返回排序好的数组
     */
    public int[] sortArray(int[] nums) {
        //最小值的下标
        for (int i = 0; i < nums.length ; i++) {
            int min = i;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = nums[i];
                nums[i] = nums[min];
                nums[min] = temp;
            }
        }
        return nums;
    }

选择排序的优点:交换次数最少

「选择排序」看起来好像最没有用,但是如果在交换成本较高的排序任务中,就可以使用「选择排序」(《算法 4》相关章节课后练习题)。

不要对算法带有个人色彩,在面试回答问题的时候和看待一个人和事物的时候,可以参考的回答模式是「具体问题具体分析,在什么什么情况下,用什么什么算法」。

1.2 冒泡排序

最快:当输入的数据已经是正序时(我还要你冒泡排序有何用)

最慢:当输入的数据是反序时(干嘛要用你冒泡排序呢,我是闲的吗)。

算法思路步骤

每次比较相邻的元素,如果第一个比第二个打,直接交换;直到没有任何一对数字需要比较

  • 下面是代码演示
     /**
         * 使用冒泡排序解题
         *
         * @param nums 数组
         * @return 返回排序好的数组
         */
        public int[] sortArray(int[] nums) {
            boolean mark = true;
            while (mark) {
                boolean end = false;
                for (int i = 0; i < nums.length - 1; i++) {
                    if (nums[i] > nums[i + 1]) {
                        int temp = nums[i];
                        nums[i] = nums[i + 1];
                        nums[i + 1] = temp;
                        end = true;
                    }
                }
                mark = end;
            }
            return nums;
        }
    
  • 比较官方的解答
        public int[] sortArray(int[] nums) {        
            int len = nums.length;
            for (int i = len - 1; i >= 0; i--) {
                // 先默认数组是有序的,只要发生一次交换,就必须进行下一轮比较
                boolean sorted = true;
                for (int j = 0; j < i; j++) {
                    if (nums[j] > nums[j + 1]) {
                        swap(nums, j, j + 1);
                        sorted = false;
                    }
                }
    
                // 如果在内层循环中,都没有执行一次交换操作,说明此时数组已经是升序数组
                if (sorted) {
                    break;
                }
            }
            return nums;
        }
        private void swap(int[] nums, int index1, int index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    

1.3 插入排序

插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。

算法解题步骤:

默认第一个有序,然后从后往前比较,直到找不到比自己小的,然后插进去

  • 算法实现:
    /**
     * 使用插入排序解题
     *
     * @param nums 数组
     * @return 返回排序好的数组
     */
    public int[] sortArray(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int temp = nums[i];
            int j = i;
            while(j>0 && temp<nums[j-1]){
                nums[j] = nums[j-1];
                j--;
            }
            if(j != i){
                nums[j] =temp;
            }
        }
        return nums;
    }

1.4 希尔排序

是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法

1.5 归并排序

该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

算法解题步骤:

归并排序的核心是递归,我们需要先把数组的左右两部分分别排序,然后再把左右两部分有序的数组合并到一起,形成一个有序的数组

  • 代码演示:
/**
 * @author song
 * 归并排序 对一个数组进行排序
 */
public class Code02_MerageSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 1, 4, 9, 7};
        process(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merage(arr, L, mid, R);
    }

    public static void merage(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        //说明左右区间都有数
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //只有左侧有数
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        //同理只有右侧有数
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }
    }
}

****ps:有一个经典的例题LeetCode剑指offer51 我建议每次复习归并排序的时候,都去做一遍这个题【在做这个题的时候,其核心部分在判断临界值的时候一定要小心】

1.6 快速排序

快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

算法思想

  1. 从数组中挑出来一个元素、称为基准(pivot)
  2. 重新排序,比基准小的在基准前面,泛指比基准大的在后面
  3. 递归,以基准为标准,左右两边的数分别执行一二步骤img
  • 代码实现
import java.util.Random;

public class Solution {

    // 快速排序 3:三指针快速排序

    /**
     * 列表大小等于或小于该大小,将优先于 quickSort 使用插入排序
     */
    private static final int INSERTION_SORT_THRESHOLD = 7;

    private static final Random RANDOM = new Random();

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        quickSort(nums, 0, len - 1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        // 小区间使用插入排序
        if (right - left <= INSERTION_SORT_THRESHOLD) {
            insertionSort(nums, left, right);
            return;
        }

        int randomIndex = left + RANDOM.nextInt(right - left + 1);
        swap(nums, randomIndex, left);

        
        int pivot = nums[left];
        int lt = left;
        int gt = right + 1;

        int i = left + 1;
        while (i < gt) {
            if (nums[i] < pivot) {
                lt++;
                swap(nums, i, lt);
                i++;
            } else if (nums[i] == pivot) {
                i++;
            } else {
                gt--;
                swap(nums, i, gt);
            }
        }
        swap(nums, left, lt);
        // 注意这里,大大减少了两侧分治的区间
        quickSort(nums, left, lt - 1);
        quickSort(nums, gt, right);
    }

    /**
     * 对数组 nums 的子区间 [left, right] 使用插入排序
     *
     * @param nums  给定数组
     * @param left  左边界,能取到
     * @param right 右边界,能取到
     */
    private void insertionSort(int[] nums, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = nums[i];
            int j = i;
            while (j > left && nums[j - 1] > temp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

LeetCode实战

  • LeetCode 75 颜色分类
  • LeetCode 215 数组中第K个最大元素
这篇关于【xsong说算法】第一期:排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!