排序第四讲-总结及应用

排序总结

本系列一共提到选择排序、插入排序、归并排序、快速排序、堆排序这五种排序算法，下面我们从不同维度将其进行对比

算法	稳定性	时间复杂度	空间复杂度	备注
选择排序	否	\(O(N^2)\)	\(O(1)\)
插入排序	是	\(O(N) \sim O(N^2)\)	\(O(1)\)	效率受输入影响，逆序时最低
归并排序	是	\(O(Nlog_{2}N)\)	\(O(N)\)
快速排序	否	\(O(Nlog_{2}N)\)	\(O(1)\)	效率受元素重复度影响
堆排序	否	\(O(Nlog_{2}N)\)	\(O(1)\)

稳定性

稳定性是针对重复元素在排序后相对顺序是否改变说的
举个例子，对于数组[2₀, 2₁, 1, 3]

• 使用选择排序，数组变为[1, 2₁, 2₀, 3]，重复元素2的下标交换了，所以选择排序是不稳定的
• 使用插入排序，数组变为[1, 2₀, 2₁, 3]，重复元素2都在原位置，所以插入排序是稳定的
• 其他算法的稳定性试请大家自行测试

时间复杂度

从时间复杂度来讲，归并排序、快速排序、堆排序效率显然是最高的，而且《算法第四版》中证明了，基于比较的排序算法的时间复杂度上限就是\(O(Nlog_{2}N)\)
并且快速排序具有最低的常数因子，也就是说，快速排序的平均时间复杂度是最低的
尽管存在一些特例会使得快速排序的时间复杂度退化到平方级别，但这些例子（比如都是重复元素）在概率上占比极低，并且可以通过三向切分的快速排序进行优化
所以通用场景下使用快速排序是非常高效的

应用

多主键排序

多主键排序在业务上应用极广，比如先按年龄排序，年龄相同则按身高排序，有两种方式实现

• 编写一个比较器，逻辑为先按年龄比较，相同则按身高比较
• 先按身高排序，然后按年龄排序，但这样排序了两次，效率太低

去重

排序后去除重复元素即可，比如[3, 2, 3, 5, 1, 2]排序后为[1, 2, 2, 3, 3, 5]，去重后为[1, 2, 3, 5]

topK

topK就是求出一个数组中第K大的元素，数组可能包含重复元素
最简单的方式应该是将数组排序，再找出第K大的元素，时间复杂度为\(O(Nlog_{2}N)\)，下面探讨更高效的方法

优先队列

优先队列是一种可以将集合中最大（或最小）值出队的数据结构，可以使用堆实现，本文不讨论具体实现
借助优先队列实现topK的思路如下

• 创建一个求最小值的优先队列，大小为K
• 将数组中的值依次置入优先队列
  • 队列未满时直接置入
  • 队列满时，将最小值出队，和置入值比较，将较大的值入队
• 执行完毕，队列中即为数组的全部top1到K的元素，出队即得topK元素

举例说明，假设数组为[3, 2, 4, 5, 6, 1, 5]，求top2

• 首先填满队列，队列为[3, 2]
• 置入4，踢出最小的2，得到[4, 3]
• 置入5，踢出3，得到[5, 4]
• 置入6，踢出4，得到[6, 5]
• 不置入1
• 不置入5，最终队列为[6,5]，出队得到top2为5

理解该算法的关键在于，队列每次都只会踢出较小的元素，且队列大小为K，作为topK的元素，在执行过程中不会被踢出，所以最终留下的是前topK个元素 空间复杂度：优先队列如果使用堆实现，空间占用为\(O(K)\) 时间复杂度：优先队列入队和出队复杂度均为\(log_{2}n\)，n为队列中元素个数，前K个元素入队，用时为

\[log_{2}1+log_{2}2+...+log_{2}K=log_{2}(K!)≈Klog_{2}K\]

之后N-K个元素（N为数组大小）出队和入队，耗时为\((N-K)log_{2}K\)
两项加和为\(Nlog_{2}K\)，即是最终的复杂度
代码如下

https://leetcode.cn/problems/kth-largest-element-in-an-array/submissions/588248965/
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            if (i < k) {
                minHeap.add(nums[i]);
            } else {
                int min = minHeap.poll();
                if (nums[i] > min) {
                    minHeap.add(nums[i]);
                } else {
                    minHeap.add(min);
                }
            }
        }

        return minHeap.poll();
    }

划分

大家应该还记得，划分是快速排序的基本操作，topK问题也可以借助划分来解决

• 仍旧使用[3, 2, 4, 5, 6, 1, 5]做例子，求top2，即排序后数组下标5上的元素
• 第一次划分，得到[2, 1]、[3₂]、[5, 6, 4, 5]，轴的位置定在下标2，这个位置就是元素3排序后的最终位置，所以top2落在右子数组中，需要对右子数组进行划分
• 第二次划分右子数组[5, 6, 4, 5] -> [4]、[5₄]、[6, 5]，轴的位置在下标4，仍需划分有子数组
• 第三次划分右子数组[6, 5] -> [5₅]、[6₆]、[]，轴的位置在下标6，左子数组只有一个元素，即top2=5

// https://leetcode.cn/problems/kth-largest-element-in-an-array/submissions/588289281/
// 使用一般的划分无法通过，因为重复元素多的用例会超时，使用三向切分可以通过，可参考 https://leetcode.cn/problems/kth-largest-element-in-an-array/submissions/536496155/
    public int findKthLargest(int[] nums, int k) {
        return select(nums, nums.length - k);
    }

    public int select(int[] nums, int i) {
        int l = 0, r = nums.length;
        while (true) {
            if (l == r - 1) {
                return nums[l];
            }

            int pivotal = partition(nums, l, r);
            if (pivotal == i) {
                return nums[pivotal];
            }

            if (pivotal < i) {
                l = pivotal + 1;
            } else {
                r = pivotal;
            }
        }

    }

    public int partition(int[] nums, int l, int r) {
        int i = l, j = r;
        int v = nums[l];
        while (true) {
            while (nums[++i] <= v) {
                if (i == r - 1) {
                    break;
                }
            }

            while (nums[--j] > v) {}

            if (i >= j) {
                break;
            }

            swap(nums, i, j);
        }

        swap(nums, l, j);
        return j;
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

空间复杂度：\(O(1)\)
时间复杂度：平均为\(O(N)\)，最坏情况为平方级别，比如有大量重复元素时，证明见《算法第四版》

结语

经典排序算法系列就先到此结束了，希望大家可以通过本系列学习和巩固排序知识，关于排序还有非常多的话题，有机会开新坑再一起研究。