本文共 10251 字，大约阅读时间需要 34 分钟。

快速排序

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

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

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

递推公式如下：

$$递推公式：quic{k}_{s}ort(p\dots r)=quic{k}_{s}ort(p\dots q-1)+quic{k}_{s}ort(q+1,r)$$ $$终止条件：p>=r$$

代码如下：

// 快速排序，a是数组，n表示数组的大小    public static void quickSort(int []a, int n){
           quickSortInternally(a, 0, n-1);    }    private static void quickSortInternally(int[] a, int p, int r){
           if(p >= r){
               return;        }        int q = partition(a, p, r); //获取分区点        quickSortInternally(a, p, q - 1);        quickSortInternally(a, q + 1, r);    }

归并排序中有一个 merge() 合并函数，我们这里有一个 partition() 分区函数。partition()分区函数实际上我们前面已经讲过了，就是随机选择一个元素作为pivot（一般情况下，可以选择p到r区间的最后一个元素），然后对A[p…r]分区，函数返回pivot的下标。

如果我们不考虑空间消耗的话，partition()分区函数可以写的非常简单。我们申请两个临时数组X和Y，遍历A[p…r]，将小于pivot的元素都拷贝到临时数据X，将大于pivot的元素都拷贝到临时数组Y，最后再将数组X和数据Y中数据顺序拷贝到A[p…r]

但是，如果按照这种思路实现的话，partition()函数就需要很多额外的内存空间，所以快排就不是原地排序算法了。如果我们希望快排是原地排序算法，那它的空间复杂度就需要是O(1)，那 partition() 分区函数就不能占用太多额外的内存空间，我们就需要在 A[p…r] 的原地完成分区操作。其代码如下：

private static int partition(int []a, int p, int r){
           int pivot = a[r];        int i = p;        for(int j = p; j < r; ++j){
               if(a[j] < pivot){
                   if(i == j){
                       ++i; // 有序区扩大                }else{
                       int tmp = a[i];                    a[i] = a[j];                    a[j] = tmp;  //先交换                    ++i; //有序区扩大                }            }        }        int tmp = a[i];  //处理[基准]        a[i] = a[r];        a[r] = tmp;        return i;    }

这里的处理有点类似选择排序。我们通过游标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的位置。

因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。

性能分析：

（1）快排的时间复杂度

快排也是用递归实现的。如果每次分区操作，都能正好的把数组分成大小接近的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的。所以，快排的时间复杂度也是 O(nlogn)。

$$T(1)=C；n=1时，只需要常量级的执行时间，所以表示为C。$$

$$T(n)=2\ast T(n/2)+n；n>1$$

但是公式成立的前提是每次分区操作，我们选择的pivot都很合适，正好能将大区间对等的一分为二。但实际上这种情况是很难实现的。

举一个比较极端的例子，如果数组中的数据原来就是已经有序的了，比如1、3、5、6、8，如果我们每次选择最后一个元素作为pivot，那每次分区得到的两个区间但是不均等的，我们需要进行大约n次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O($n^2$)。

我们刚刚讲了两个极端情况下的时间复杂度，一个是分区极其均衡，一个是分区极其不均衡。它们分别对应快排的最好情况时间复杂度和最坏情况时间复杂度。那快排的平均情况时间复杂度是多少呢？

T(n) 在大部分情况下的时间复杂度都可以做到O(nlogn)，只有在极端情况下，才会退化到 O($n^2$)。而且，我们也有很多方法将这个概率降到很低

/**     * 快速排序     *     * @param arr     */    public static void quickSort(int[] arr, int left, int right) {
           if (left >= right) {
               return;        }        int q = partition2(arr, left, right);        quickSort(arr, left, q - 1);        quickSort(arr, q + 1, right);    }    private static int partition(int[] arr, int left, int right) {
           int pivot = arr[right];        int i = left;        for (int j = left; j < right; j++) {
               if (arr[j] < pivot) {
                   if (i == j) {
                       ++i;                } else {
                       int tmp = arr[i];                    arr[i++] = arr[j];                    arr[j] = tmp;                }            }        }        int tmp = arr[i];        arr[i] = arr[right];        arr[right] = tmp;        return i;    }    private static int partition2(int[] arr, int left, int right) {
           // 三数取中法 , 随机数在这里写        int middle = (left + right) / 2;        int pivot = arr[middle];        // 交换到最右边        int val = arr[right];        arr[right] = pivot;        arr[middle] = val;        int i = left;        for (int j = left; j < right; j++) {
               if (arr[j] < pivot) {
                   if (i == j) {
                       ++i;                } else {
                       int tmp = arr[i];                    arr[i++] = arr[j];                    arr[j] = tmp;                }            }        }        int tmp = arr[i];        arr[i] = arr[right];        arr[right] = tmp;        return i;    }    /**     * 三向切分快速排序     *     * @param arr     * @param left     * @param right     * @return     */    private static void quickSort3(int[] arr, int left, int right) {
           if (left >= right) {
               return;        }        int l = left;        int k = left + 1;        int r = right;        int pivot = arr[l];        while (k <= r) {
               if (arr[k] < pivot) {
                   int tmp = arr[l];                arr[l] = arr[k];                arr[k] = tmp;                l++;                k++;            } else if (arr[k] == pivot) {
                   k++;            } else {
                   if (arr[r] > pivot) {
                       r--;                } else if (arr[r] == pivot) {
                       int tmp = arr[k];                    arr[k] = arr[r];                    arr[r] = tmp;                    k++;                    r--;                } else {
                       int tmp = arr[l];                    arr[l] = arr[r];                    arr[r] = arr[k];                    arr[k] = tmp;                    l++;                    k++;                    r--;                }            }        }        quickSort(arr, left, l - 1);        quickSort(arr, r + 1, right);    }    /**     * 双轴快速排序     *     * @param arr     * @param left     * @param right     */    private static void quickSort4(int[] arr, int left, int right) {
           if (left >= right) {
               return;        }        int l = left;        int k = left + 1;        int r = right;        // 判断pivot1 与 pivot2 大小        if (arr[l] > arr[r]) {
               int tmp = arr[l];            arr[l] = arr[r];            arr[r] = tmp;        }        int pivot1 = arr[l];        int pivot2 = arr[r];        while (k < r) {
               if (arr[k] < pivot1) {
                   l++;                if (l != k) {
                       int tmp = arr[l];                    arr[l] = arr[k];                    arr[k] = tmp;                }                k++;            } else if (arr[k] >= pivot1 && arr[k] <= pivot2) {
                   k++;            } else {
                   --r;                if (arr[r] > pivot2) {
                   } else if (arr[r] >= pivot1 && arr[r] <= pivot2) {
                       int tmp = arr[k];                    arr[k] = arr[r];                    arr[r] = tmp;                    k++;                } else {
                       l++;                    int tmp = arr[l];                    arr[l] = arr[r];                    arr[r] = arr[k];                    arr[k] = tmp;                    k++;                }            }        }        // 交换pivot1 和 pivot2        arr[left] = arr[l];        arr[l] = pivot1;        arr[right] = arr[r];        arr[r] = pivot2;        quickSort(arr, left, l - 1);        quickSort(arr, l + 1, r - 1);        quickSort(arr, r + 1, right);    }

问题：快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢？

可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后在合并。而快排的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为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] 区间查找。

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

第一次分区查找，我们需要对大小为n的数组执行分区操作，需要遍历n个元素。第二次分区查找，我们只需要对大小为n/2的数组执行分区操作，需要遍历n/2个元素。依次类推，分区遍历元素的个数分别为n、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\ast n)$。你可能会说，时间复杂度前面的系数不是可以忽略吗？$O(K\ast n)$不就等于 $O(n)$吗？

问题是当 K 是比较小的常量时，比如 1、2，那最好时间复杂度确实是 O(n)；但当 K 等于 n/2 或者 n 时，这种最坏情况下的时间复杂度就是 $O(n^2)$了。

public static int kthSmallest(int[] arr, int k) {
           if (arr == null || arr.length < k) {
               return -1;        }        int partition = partition(arr, 0, arr.length - 1);        while (partition + 1 != k) {
               if (partition + 1 < k) {
                   partition = partition(arr, partition + 1, arr.length - 1);            } else {
                   partition = partition(arr, 0, partition - 1);            }        }        return arr[partition];    }    private static int partition(int[] arr, int p, int r) {
           int pivot = arr[r];        int i = p;        for (int j = p; j < r; j++) {
               // 这里要是 <= ，不然会出现死循环，比如查找数组 [1,1,2] 的第二小的元素            if (arr[j] <= pivot) {
                   swap(arr, i, j);                i++;            }        }        swap(arr, i, r);        return i;    }    private static void swap(int[] arr, int i, int j) {
           if (i == j) {
               return;        }        int tmp = arr[i];        arr[i] = arr[j];        arr[j] = tmp;    }

/**     * O(n)  时间复杂度内求无序数组中的第 K  大元素。比如， 4 ， 2 ， 5 ， 12 ， 3  这样一组数据，第 3  大元素就是 4 。     *     * @param arr     */    public static int sort(int[] arr, int l, int r, int k) {
           if (l >= r) {
               return 0;        }        int p = partition(arr, l, r);        if ((p + 1) == k) {
               return arr[p];        } else if ((p + 1) < k) {
               return sort(arr, p + 1, r, k);        } else {
               return sort(arr, l, p - 1, k);        }    }

总结

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是 O(n)。正因为此，它也没有快排应用广泛。

快速排序算法虽然最坏情况下的时间复杂度是$O(n^2)$，但是平均情况下时间复杂度都是O(nlogn)。不仅如此，快速排序算法时间复杂度退化到 $O(n^2)$的概率非常小，我们可以通过合理地选择 pivot 来避免这种情况。

转载地址：https://blog.csdn.net/zhizhengguan/article/details/122399076 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！