2021-05-24 如何用快排思想在O(n)内查找第K大元素

红太狼 2022-10-15 10:56 58阅读 0赞

今天，我讲两种时间复杂度为 O(nlogn) 的排序算法，**归并排序**和**快速排序**。这两种排序算法适合大规模的数据排序。

归并排序和快速排序都用到了分治思想，非常巧妙。我们可以借鉴这个思想，来解决非排序的问题，比如：**如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素？**

# 归并排序的原理 #

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70][]

归并排序使用的就是**分治思想**。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

从我刚才的描述，你有没有感觉到，分治思想跟我们前面讲的递归思想很像。是的，分治算法一般都是用递归来实现的。**分治是一种解决问题的处理思想，递归是一种编程技巧**，这两者并不冲突。分治算法的思想我后面会有专门的一节来讲，现在不展开讨论，我们今天的重点还是排序算法。

前面我通过举例让你对归并有了一个感性的认识，又告诉你，归并排序用的是分治思想，可以用递归来实现。我们现在就来看看**如何用递归代码来实现归并排序**。

我在[第 10 节][10]讲的递归代码的编写技巧你还记得吗？写递归代码的技巧就是，分析得出递推公式，然

后找到终止条件，最后将递推公式翻译成递归代码。所以，要想写出归并排序的代码，我们先写出归并排序的递推公式。

递推公式：
    merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
     
    终止条件：
    p >= r 不用再继续分解

我们通过游标 i 把 A\[p…r-1\] 分成两部分。A\[p…i-1\] 的元素都是小于 pivot 的，我们暂且叫它“已处理区间”，A\[i…r-1\] 是“未处理区间”。我们每次都从未处理的区间 A\[i…r-1\] 中取一个元素 A\[j\]，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 A\[i\] 的位置。

数组的插入操作还记得吗？在数组某个位置插入元素，需要搬移数据，非常耗时。当时我们也讲了一种处理技巧，就是交换，在 O(1) 的时间复杂度内完成插入操作。这里我们也借助这个思想，只需要将 A\[i\] 与 A\[j\] 交换，就可以在 O(1) 时间复杂度内将 A\[j\] 放到下标为 i 的位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 1][]

public class MergeSort {
        public static void main(String []args){
            int []arr = {9,8,7,6,5,4,3,2,1};
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
        public static void sort(int []arr){
            int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
            sort(arr,0,arr.length-1,temp);
        }
        private static void sort(int[] arr,int left,int right,int []temp){
            if(left<right){
                int mid = (left+right)/2;
                sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
                sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
                merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
            }
        }
        private static void merge(int[] arr,int left,int mid,int right,int[] temp){
            int i = left;//左序列指针
            int j = mid+1;//右序列指针
            int t = 0;//临时数组指针
            while (i<=mid && j<=right){
                if(arr[i]<=arr[j]){
                    temp[t++] = arr[i++];
                }else {
                    temp[t++] = arr[j++];
                }
            }
            while(i<=mid){//将左边剩余元素填充进temp中
                temp[t++] = arr[i++];
            }
            while(j<=right){//将右序列剩余元素填充进temp中
                temp[t++] = arr[j++];
            }
            t = 0;
            //将temp中的元素全部拷贝到原数组中
            while(left <= right){
                arr[left++] = temp[t++];
            }
        }
    }

归并排序稳不稳定关键要看 merge() 函数，也就是两个有序子数组合并成一个有序数组的那部分代码。

在合并的过程中，如果 A\[p…q\] 和 A\[q+1…r\] 之间有值相同的元素，那我们可以像伪代码中那样，先把 A\[p…q\] 中的元素放入 tmp 数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。

归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。

在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

## 快速排序的原理 ##

快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。

我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 2][]

根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

如果我们用递推公式来将上面的过程写出来的话，就是这样：

递推公式：
    quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
     
    终止条件：
    p >= r

public class QuickSort {
        public static void main(String[] args) {
            int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
            quickSort(arr, 0, arr.length - 1);
            System.out.println("排序结果：" + Arrays.toString(arr));
        }
    
        /**
         * @param arr
         * @param left  左指针
         * @param right 右指针
         */
        public static void quickSort(int[] arr, int left, int right) {
            if (left < right) {
                //获取枢纽值，并将其放在当前待处理序列末尾
                dealPivot(arr, left, right);
                //枢纽值被放在序列末尾
                int pivot = right - 1;
                //左指针
                int i = left;
                //右指针
                int j = right - 1;
                while (true) {
                    while (arr[++i] < arr[pivot]) {
                    }
                    while (j > left && arr[--j] > arr[pivot]) {
                    }
                    if (i < j) {
                        swap(arr, i, j);
                    } else {
                        break;
                    }
                }
                if (i < right) {
                    swap(arr, i, right - 1);
                }
                quickSort(arr, left, i - 1);
                quickSort(arr, i + 1, right);
            }
    
        }
    
        /**
         * 处理枢纽值
         *
         * @param arr
         * @param left
         * @param right
         */
        public static void dealPivot(int[] arr, int left, int right) {
            int mid = (left + right) / 2;
            if (arr[left] > arr[mid]) {
                swap(arr, left, mid);
            }
            if (arr[left] > arr[right]) {
                swap(arr, left, right);
            }
            if (arr[right] < arr[mid]) {
                swap(arr, right, mid);
            }
            swap(arr, right - 1, mid);
        }
    
        /**
         * 交换元素通用处理
         *
         * @param arr
         * @param a
         * @param b
         */
        private static void swap(int[] arr, int a, int b) {
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 3][]

归并排序的处理过程是**由下到上**的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是**由上到下**的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

**如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素？**

快排核心思想就是**分治**和**分区**，我们可以利用分区的思想，来解答开篇的问题：O(n) 时间复杂度内求无序数组中的第 K 大元素。比如，4， 2， 5， 12， 3 这样一组数据，第 3 大元素就是 4。

我们选择数组区间 A\[0…n-1\] 的最后一个元素 A\[n-1\] 作为 pivot，对数组 A\[0…n-1\] 原地分区，这样数组就分成了三部分，A\[0…p-1\]、A\[p\]、A\[p+1…n-1\]。

如果 p+1=K，那 A\[p\] 就是要求解的元素；如果 K>p+1, 说明第 K 大元素出现在 A\[p+1…n-1\] 区间，我们再按照上面的思路递归地在 A\[p+1…n-1\] 这个区间内查找。同理，如果 K<p+1，那我们就在 A\[0…p-1\] 区间查找。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 4][]

我们再来看，为什么上述解决思路的时间复杂度是 O(n)？

第一次分区查找，我们需要对大小为 n 的数组执行分区操作，需要遍历 n 个元素。第二次分区查找，我们只需要对大小为 n/2 的数组执行分区操作，需要遍历 n/2 个元素。依次类推，分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.……直到区间缩小为 1。

如果我们把每次分区遍历的元素个数加起来，就是：n+n/2+n/4+n/8+…+1。这是一个等比数列求和，最后的和等于 2n-1。所以，上述解决思路的时间复杂度就为 O(n)。

你可能会说，我有个很笨的办法，每次取数组中的最小值，将其移动到数组的最前面，然后在剩下的数组中继续找最小值，以此类推，执行 K 次，找到的数据不就是第 K 大元素了吗？

不过，时间复杂度就并不是 O(n) 了，而是 O(K \* n)。你可能会说，时间复杂度前面的系数不是可以忽略吗？O(K \* n) 不就等于 O(n) 吗？

这个可不能这么简单地划等号。当 K 是比较小的常量时，比如 1、2，那最好时间复杂度确实是 O(n)；但当 K 等于 n/2 或者 n 时，这种最坏情况下的时间复杂度就是 O(n2) 了。

## 课后思考 ##

现在你有 10 个接口访问日志文件，每个日志文件大小约 300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这 10 个较小的日志文件，合并为 1 个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有 1GB，你有什么好的解决思路，能“快速”地将这 10 个日志文件合并吗？

先构建十条io流，分别指向十个文件，每条io流读取对应文件的第一条数据，然后比较时间戳，选择出时间戳最小的那条数据，将其写入一个新的文件，然后指向该时间戳的io流读取下一行数据，然后继续刚才的操作，比较选出最小的时间戳数据，写入新文件，io流读取下一行数据，以此类推，完成文件的合并， 这种处理方式，日志文件有n个数据就要比较n次，每次比较选出一条数据来写入，时间复杂度是O（n），空间复杂度是O（1）,几乎不占用内存

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70]: /images/20221014/81a16ef5575a4524ae7d53512f42cac8.png
[10]: https://time.geekbang.org/column/article/41440
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 1]: /images/20221014/fc27693fd53b4cc0a8d1de5901c68b4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 2]: /images/20221014/ace5dbc62f35488a8abdef8bfac0cedb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 3]: /images/20221014/868d7a6d5b0b4e35b65b37b2e320f10d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoY2NjY2ho_size_16_color_FFFFFF_t_70 4]: /images/20221014/05a81e3e809e4f55a216de8bbcb9a50f.png