每天学点小东西,可不能天天下班回来就看手机呀。。。

今天开的专题是排序,排序是学过好多遍的,但是学了忘,忘了学,汗。

一种非常典型的算法,简单地说就是一组数组,通过某种操作能让它变得有序,升序or降序。

下面总地说说各种排序算法的思想以及代码,当然,它们是最基础的,也还有优化空间。

默认对int[] arr进行升序排序


选择排序

它的思想非常简单,就是选择一个元素,把它放在它该在的地方。

比如索引为0的元素,那它就是最小的嘛,然后剩下的元素中找到最小的元素,放到第0个位置上,依此类推。

从前往后缩小排序的范围,因为前面的已经排好的嘛,一个一个地往后。

注意噢,它是交换次数最小的一种排序方式,不过也有它的缺点,就是运行时间和输入无关,即使它已经有序了,也和完全无序的元素的运行时间一样……

时间复杂度:$O(N^2)$

空间复杂度:$O(1)$

public static void main(String[] args) {
    int[] arr = new int[]{
            0, 6, 4, 3, 7, 5, 2, 1, 9, 8
    };
    for(int i = 0;i < arr.length;i++){
        // 选择一个最小的
        int min = i;
        // 从后面的数中找最小的
        for(int j = i + 1;j < arr.length;j++){
            if (arr[j] < arr[min]){
                min = j;
            }
        }
        // 把最小的放到它该在的地方
        exch(arr, min, i);
    }
    Arrays.stream(arr).forEach(System.out::print);
}

插入排序

这个排序我马上就想起打牌时整理扑克的场景 :我总会先把一边排好,比如把最大的2、1找出来放到左边,然后再把KQJ找出来,放到2、1的后面,依此类推。

正式点的话就是:当前索引的左边都是有序的,当遇到一个新的元素时,把它“插入”到有序元素的正确的位置。

它可以很快地把一个大致有序的数据进行排序。

时间复杂度:$O(N^2)$

空间复杂度:$O(1)$

public static void main(String[] args) {
    int[] arr = new int[]{
            0, 6, 4, 3, 7, 5, 2, 1, 9, 8
    };
    for(int i = 1;i < arr.length;i++){
        // 保持i的左边是有序的
        for(int j = i ;j > 0 && arr[j] < arr[j - 1];j--){
            // 与前一个元素交换,直到它在合适的位置
            exch(arr, j, j - 1);
        }
    }
    Arrays.stream(arr).forEach(System.out::print);
}

当然,这段代码也是可以优化的,可以看到它交换太多了,其实不应该,可以往后找到合适的位置,最后再交换一次即可。

public static void main(String[] args) {
    int[] arr = new int[]{
            0, 6, 4, 3, 7, 5, 2, 1, 9, 8
    };
    for(int i = 1 ;i < arr.length;i++){
        // 把当前元素value插入有序区[0, i)的恰当位置
        int value = arr[i];
        int j = i;
        // 与value相比!要是比它大,就放到后面
        while (j > 0 && arr[j - 1] > value){
            arr[j] = arr[j - 1];
            j--;
        }
        // 插入value
        arr[j] = value;
    }
    Arrays.stream(arr).forEach(System.out::print);
}

希尔排序

非常神奇的一个算法,是插入排序的一种优化:插入排序找恰当位置的时候,不是一步一步地移动吗?这里就绝绝子,它一次移动h步($h >= 1$)。每次排序后,让h逐渐变小,直到为1,即回到原始的插入排序,但此时元素已经“大致有序”,排序速度会很快。

其实它就是h把大数组分为了若干个小数组进行插入排序,兼顾了规模与有序性,因为插入排序非常适合短数组和部分有序的数组。渐渐地把小数组排序完,此时留下的是部分有序的大数组,这里处理就很快了。

《算法》这本书也提到,除了对于很大的N,它们(其它更高级的排序算法)可能只会比希尔排序快两倍(可能还不到),并且更复杂,我也很赞同,因为它确实简单。

好像还没有对这个排序的性能作出非常透彻的理解,下面的复杂度也是按主流所说。

平均时间复杂度:$O(NlogN)$ ?最坏情况下也达不到平方级别,最多是与N^1.5成正比。

空间复杂度:$O(1)$

public static void main(String[] args) {
    int[] arr = new int[]{
            0, 6, 4, 3, 7, 5, 2, 1, 9, 8
    };
    int h = 1;
    int n = arr.length;
    // 设定步长为3n+1
    while (h < n / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        // 步长为h的插入排序。
        for (int i = h; i < n; i += h){
            int value = arr[i];
            int j = i;
            while(j > 0 && arr[j - h] > value){
                arr[j] = arr[j - h];
                j -= h;
            }
            arr[j] = value;
        }
        h /= 3;
    } 
    Arrays.stream(arr).forEach(System.out::print);
}

看,果然是没啥区别吧,但是它却比插入排序快多了噢~

优化的话,还可以对步长h进行优化。

归并排序

原地归并

要想完成归并排序,先作以下一个小操作

把有序子数组arr[lo, mid]和arr[mid + 1, hi]归并成arr[lo, hi]。

这里采用临时数组的方法,把元素先放到临时数组中,然后再归并回原数组。

// 临时数组
private static int[] aux = new int[10];

public static void merge(int[] arr, int lo, int mid, int hi){
    int i = lo, j = mid + 1;
    // 复制到临时数组中保存。
    for(int k = lo;k <= hi;k++){
        aux[k] = arr[k];
    }
    for(int k = lo;k <= hi;k++){
        if (i > mid){      
            // 左边排完了
            arr[k] = aux[j++];
        }else if(j > hi){
            // 右边排完了
            arr[k] = aux[i++];
        }else if(aux[i] < aux[j]){
            // 左边比右边小,放左边
            arr[k] = aux[i++];
        }else{
            arr[k] = aux[j++];
        }
    }
}

自顶向下

有了上面的基础归并后,可以挖掘两个不同的归并方式。现在这种是自顶向下的,怎么说呢,它就是从上开始向下遍历,可以看看它的遍历树就知道了。

这也是我们遇到的最平常、最简单的一种写法,简单地说就是使用递归,先排左边,再排右边,然后再合并两个有序数组,听起来非常简单呢(确实是这样的!)

private static void topToBottomSort(int[] arr, int lo, int hi) {
    if (hi <= lo) {
        return;
    }
    // 找中间
    int mid = lo + (hi - lo) / 2;
    // 排左边
    topToBottomSort(arr, lo, mid);
    // 排右边
    topToBottomSort(arr, mid + 1, hi);
    // 合并左右
    merge(arr, lo, mid, hi);
}

它排左边的时候,是一路往下遍历,直到lo > mid的时候(其实也就是前两个元素),就合并它,然后再接着第三、第四个元素,再合并它,然后再把前四个元素排好序,依此类推。。。这就是向下的过程(可以画一画它的过程,这里是说给自己看的,如果有访客来,这肯定是看不懂的【x)

自底向下

还有一种是从底下开始向上遍历的,就是我先在底下排好,然后再向上合并。

比如,我一开始两个两个地排序、归并,然后再四个四个、八个八个。。。

private static void bottomToTopSort(int[] arr) {
    int n = arr.length;
    // size指每个要排序的小区间的大小,两个为一组
    for (int size = 1; size < n; size = size + size) {
        for (int lo = 0; lo < n - size; lo += size + size) {
            // [lo, lo + size - 1]就是对应上面的“排左边”
            // [lo + size - 1, Math.min(lo + size + size - 1, n - 1)] 就是排右边
            // 这个min,其实是怕最后越界了,比如当我八个八个地排的时候,“右边”不够8个了,这时最大就是n-1了
            merge(arr, lo, lo + size - 1, Math.min(lo + size + size - 1, n - 1));
        }
    }
}

快速排序

顾名思义,它就是很快了!

它也是和归并一样,有一种分治的思想,具体做法是:把一个数组切分现两部分,以某个元素为轴,左部分比该元素小,右部分比该元素大。然后对左边进行排序,对右边进行排序,这样就做好了。

private static void quicksort(int[] arr, int lo, int hi) {
    // 绝了,这里居然写反了
    if (hi <= lo) {
        return;
    }
    int j = partition(arr, lo, hi);
    quicksort(arr, lo, j);
    quicksort(arr, j + 1, hi);
}

把上面的话转成代码就是这样的……

切分算法是最重要的,下面的切分都是以第一个元素为轴。

private static int partition(int[] arr, int lo, int hi) {
    int pivot = arr[lo];
    while (lo < hi) {
        // 从后往前找,比枢轴大的放在右边不动
        while (lo < hi && pivot <= arr[hi]) {
            hi--;
        }
        // 找到一个小的,放到最前面(枢轴已经保存,放心覆盖)
        arr[lo] = arr[hi];
        // 从前往后找,比枢轴小的在左边不动
        while (lo < hi && arr[lo] <= pivot) {
            lo++;
        }
        // 直到遇到一个大的,把它也覆盖到刚刚枢轴右边
        arr[hi] = arr[lo];
    }
    // 最后把枢轴放到正确的位置上,也就是lo == hi的地方
    arr[lo] = pivot;
    return lo;
}

真题演练

来做一下leetcode上与排序有关的题目吧。

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k,请返回数组中第 **k** 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

提示:

  • 1 <= k <= nums.length <= 104
  • -104 <= nums[i] <= 104
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int lo = 0, hi = nums.length - 1;
        int target = nums.length - k;
        while(lo < hi){
            // 刚好划分到第nums.length - k个(即第k大)
            int mid = partition(nums, lo, hi);
            if(mid == target){
                return nums[mid];
            }else if(mid > target){
                hi = mid - 1;
            }else{
                lo = mid + 1;
            }
        }
        return nums[lo];
    }

    private int partition(int[] arr, int lo, int hi){
        int pivot = arr[lo];
        while(lo < hi){
            while(lo < hi && pivot <= arr[hi]){
                hi--;
            }
            arr[lo] = arr[hi];
            while(lo < hi && arr[lo] <= pivot){
                lo++;
            }
            arr[hi] = arr[lo];
        }
        arr[lo] = pivot;
        return lo;
    }
}