基本排序算法

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

一种非常典型的算法，简单地说就是一组数组，通过某种操作能让它变得有序，升序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;
}

计数排序

加一个，这个排序非常特别。

是一种特殊的桶排序，每个桶中的元素都是一样的，在一个桶中，即都是有序的元素。

它的思想是这样的，比如对一个范围是1-n的数组，我就创建一个1-n的桶，然后计数比较，每个桶中元素会是多少。

然后再根据这个计数，生成一个包含前面元素的和的数组，这个数组的值就是对应元素的下标。

从后往前遍历原数组，然后从计数数组中找到对应的下标，把它放进去，依此类推，即完成排序。

（说得有点奇怪。。之后再补充吧）

public static void countingSort(int[] arr) {
    int n = arr.length;
    if (n <= 1) {
        return;
    }
    // 5
    int max = Arrays.stream(arr).max().getAsInt();
    int[] count = new int[max + 1];
    // 2 0 2 3 0 1
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    // 2 2 4 7 7 8
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }
    int[] result = new int[n];
    // 2, 5, 3, 0, 2, 3, 0, 3
    for (int i = n - 1; i >= 0; i--) {
        // 比如第一个元素3，从count中找，它是第7个
        int index = count[arr[i]] - 1;
        // 把元素放到下标为6的位置
        result[index] = arr[i];
        // 计数减一
        count[arr[i]]--;
    }
    // 复制回原数组。
    for (int i = 0; i < n; i++) {
        arr[i] = result[i];
    }
}

真题演练

来做一下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;
    }
}

゛魚生