请注意,本文编写于 230 天前,最后修改于 230 天前,其中某些信息可能已经过时。

目录

引言
快速排序
算法图解
算法分析
总结

引言

上一篇数据结构与算法 --- 排序算法(二)中,介绍了分治算法思想及借助分治算法思想实现的归并排序。

本篇来讲解一下快速排序,它也是借助分治算法思想实现,但其处理思路与归并排序完全不一样。

快速排序

来看一下快速排序的算法原理:

算法图解

如果要排序数组中 pprr 的数据,那么,我们选择 pp 到r之间的任意一个数据作为 pivotpivot(分区点),然后遍历从 pprr 的数据,将小于 pivotpivot 的放到左边,将大于或等于 pivotpivot 的放右边,将 pivotpivot 放中间,经过这一步骤处理之后,从 pprr 的数据就被分成了3部分。

假设 pivotpivot 现在的位置下标是 qq,那么从 ppq1q-1 的数据都小于 pivotpivot ,中间是 pivotpivot ,从q+1q+1rr 都是大于 pivotpivot,如下图:

image.png

根据分治的处理思想,分区完成之后,开始递归下标从 ppq1q-1 的数据和下标q+1q+1rr 的数据,知道待排序区间的大小缩小为1,就说明数据都有序了。

如果使用递推公式将上面的过程表示出来,递推公式:

quick_sort(p,r)=partition(p,r)+quick_sort(p,q1)+quick_sort(q+1,r)终止条件:prquick\_sort(p,r)=partition(p,r)+quick\_sort(p,q-1)+quick\_sort(q+1,r) \qquad 终止条件:p \ge r

其中 partition() 分区函数要做的就是随机选择一个元素作为 pivotpivot(一般选择pprr区间中的最后一个元素),然后基于 pivotpivot 对区间 Arr[p,r] 进行分区,分区函数返回分区之后的 piovtpiovt 的下标。

使用C#代码实现快速排序:

csharp
class QuickSort { public static void Sort(int[] arr) { if (arr == null || arr.Length == 0) return; QuickSortRecursive(arr, 0, arr.Length - 1); } private static void QuickSortRecursive(int[] arr, int left, int right) { if (left >= right) return; int pivotIndex = Partition(arr, left, right); QuickSortRecursive(arr, left, pivotIndex - 1); QuickSortRecursive(arr, pivotIndex + 1, right); } private static int Partition(int[] arr, int left, int right) { //这里可以选择不同的策略,比如随机数选取或选择中间值 int pivotIndex = ChoosePivot(left, right); int pivotValue = arr[pivotIndex]; Swap(arr, pivotIndex, right); int currentIndex = left; for (int i = left; i < right; i++) { if (arr[i] < pivotValue) { Swap(arr, i, currentIndex); currentIndex++; } } Swap(arr, currentIndex, right); return currentIndex; } private static int ChoosePivot(int left, int right) { //这里选择使用中间值 return (left + right) / 2; } private static void Swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

算法分析

内存消耗

如果不考虑空间消耗的话,那么 partition() 分区函数实现非常简单,直接申请两个临时数组 X 和 Y,遍历目标区间 Arr[p,r] ,小于 pivotpivot 的直接复制到X,大于 pivotpivot 的直接复制到Y,最后按顺序将X,pivotpivot,Y依次复制到目标区间 Arr[p,r]

但是,如果这样实现的话, partition() 执行的过程中将消耗很多额外内存空间,快速排序也就不是原地排序算法了,如果希望快速排序是原地排序算法,该怎么做呢?

这就需要之前文章中提到的通过交换来避免搬移, 具体实现类似选择排序,通过游标 iiArr[p,r-1] 分成两个部分,Arr[p,i-1] 的元素都小于 pivotpivot (也就是Arr[r]),暂且称之为“已处理区间”,对应的,Arr[i,r-1] 是“未处理区间”。每次从未处理区间 Arr[i,r-1] 中取出一个元素Arr[j]pivotpivot 对比,如果小于 pivotpivot ,则将其插入到已处理区间的尾部,也就是下标为 ii 的位置。具体图解可以参考数据结构与算法 --- 排序算法(一)中的选择排序算法图解。

稳定性

理解完了快速排序是原地排序算法,那么分析一下该排序算法是否稳定排序?

其实也很简单,排序算法涉及到了分区,分区的操作实现又是按照选择排序原理实现,选择排序本身就是不稳定排序算法,所以快速排序也是不稳定排序。()

时间复杂度

  1. 最好情况时间复杂度:O(nlogn)O(nlogn)

    在最好的情况下,快速排序的时间复杂度为 O(nlogn)O(n log n)。这种情况发生在每次划分时,待排序数组恰好被平均地分成两个大小相近的子数组。此时,快速排序的递归树的深度较小,每一层的时间复杂度为 O(n)O(n),总的时间复杂度为 O(nlogn)O(n log n)

  2. 最坏情况时间复杂度:O(n2)O(n^2)

    在最坏的情况下,快速排序的时间复杂度为 O(n2)O(n^2)。这种情况发生在每次划分时,待排序数组中的元素都被划分到了同一侧,导致一侧的子数组非常大,另一侧为空。这样就会导致快速排序的递归树非常不平衡,每一层的时间复杂度为 O(n)O(n),而递归的层数为n,因此总的时间复杂度为 O(n2)O(n^2)

  3. 平均情况时间复杂度:O(nlogn)O(n log n)

    在平均情况下,快速排序的时间复杂度为 O(nlogn)O(n log n)。快速排序采用分治策略,在平均情况下,待排序数组会被平均地划分成两个大小相近的子数组,这样递归树会相对平衡,每一层的时间复杂度为 O(nlogn)O(n log n),总的时间复杂度为 O(nlogn)O(n log n)

总结

需要注意的是,快速排序的性能高度依赖于划分元素的选择。在实际实现中,通常会采取一些优化措施,如三数取中法或随机选取划分元素,以尽量避免最坏情况的发生。总体来说,快速排序在大多数情况下表现良好,因为平均时间复杂度为O(nlogn)O(n log n),它是一种快速且高效的排序算法。

参考

[1] 数据结构与算法之美 / 王争 著. --北京:人民邮电出版社,2021.6

本文作者:Peter.Pan

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!