Quick Sort

最后更新于:2022-04-02 01:06:51

# Quick Sort - 快速排序 核心:快排是一种采用分治思想的排序算法,大致分为三个步骤。 1. 定基准——首先随机选择一个元素最为基准 1. 划分区——所有比基准小的元素置于基准左侧,比基准大的元素置于右侧 1. 递归调用——递归地调用此切分过程 ### out-in-place - 非原地快排 容易实现和理解的一个方法是采用递归,使用 Python 的 list comprehension 实现如下所示: ~~~ #!/usr/bin/env python def qsort1(alist): print(alist) if len(alist) <= 1: return alist else: pivot = alist[0] return qsort1([x for x in alist[1:] if x < pivot]) + \ [pivot] + \ qsort1([x for x in alist[1:] if x >= pivot]) unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4] print(qsort1(unsortedArray)) ~~~ 输出如下所示: ~~~ [6, 5, 3, 1, 8, 7, 2, 4] [5, 3, 1, 2, 4] [3, 1, 2, 4] [1, 2] [] [2] [4] [] [8, 7] [7] [] [1, 2, 3, 4, 5, 6, 7, 8] ~~~ 『递归 + 非原地排序』的实现虽然简单易懂,但是如此一来『快速排序』便不再是最快的通用排序算法了,因为递归调用过程中非原地排序需要生成新数组,空间复杂度颇高。list comprehension 大法虽然好写,但是用在『快速排序』算法上就不是那么可取了。 ### 复杂度分析 在最好情况下,快速排序的基准元素正好是整个数组的中位数,可以近似为二分,那么最好情况下递归的层数为 logn\log nlogn, 咋看一下每一层的元素个数都是 nnn, 那么空间复杂度为 O(n)O(n)O(n) 无疑了,不过这只答对了一半,从结论上来看是对的,但分析方法是错的。 首先来看看什么叫空间复杂度——简单来讲可以认为是程序在运行过程中所占用的存储空间大小。那么对于递归的 out-in-place 调用而言,排除函数调用等栈空间,**最好情况下,每往下递归调用一层,所需要的存储空间是上一层中的一半。完成最底层的调用后即向上返回执行出栈操作,故并不需要保存每层所有元素的值。**所以需要的总的存储空间就是∑i=0n2i=2n\sum _{i=0} ^{} \frac {n}{2^i} = 2n∑i=02in=2n 不是特别理解的可以结合下图的非严格分析和上面 Python 的代码,递归调用的第一层保存8个元素的值,那么第二层调用时实际需要保存的其实仅为4个元素,逐层往下递归,而不是自左向右保存每一层的所有元素。 那么在最坏情况下 out-in-place 需要耗费多少额外空间呢?最坏情况下第 iii 层需要 i−1i - 1i−1 次交换,故总的空间复杂度: ∑i=0n(n−i+1)=O(n2)\sum_{i=0}^n (n-i+1) = O(n^2)∑i=0n(n−i+1)=O(n2) ![Quicksort Recursive](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2015-10-24_562b1f33724b2.png) ### in-place - 原地快排 ### one index for partition 先来看一种简单的 in-place 实现,仍然以`[6, 5, 3, 1, 8, 7, 2, 4]`为例,结合下图进行分析。以下标 lll 和 uuu 表示数组待排序部分的下界(lower bound)和上界(upper bound),下标 mmm 表示遍历到数组第 iii 个元素时当前 partition 的索引,基准元素为 ttt, 即图中的 target. ![Quick Sort one index for partition](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2015-10-24_562b1f3390888.png) 在遍历到第 iii 个元素时,x[i]x[i]x[i] 有两种可能,第一种是 x[i]≥tx[i] \geq tx[i]≥t, iii 自增往后遍历;第二种是 x[i]= u`, 即索引相等或者交叉时退出。使用 Python 的实现如下所示: ### Python ~~~ #!/usr/bin/env python def qsort2(alist, l, u): print(alist) if l >= u: return m = l for i in xrange(l + 1, u + 1): if alist[i] < alist[l]: m += 1 alist[m], alist[i] = alist[i], alist[m] # swap between m and l after partition, important! alist[m], alist[l] = alist[l], alist[m] qsort2(alist, l, m - 1) qsort2(alist, m + 1, u) unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4] print(qsort2(unsortedArray, 0, len(unsortedArray) - 1)) ~~~ ### Java ~~~ public class Sort { public static void main(String[] args) { int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4}; quickSort(unsortedArray); System.out.println("After sort: "); for (int item : unsortedArray) { System.out.print(item + " "); } } public static void quickSort1(int[] array, int l, int u) { for (int item : array) { System.out.print(item + " "); } System.out.println(); if (l >= u) return; int m = l; for (int i = l + 1; i <= u; i++) { if (array[i] < array[l]) { m += 1; int temp = array[m]; array[m] = array[i]; array[i] = temp; } } // swap between array[m] and array[l] // put pivot in the mid int temp = array[m]; array[m] = array[l]; array[l] = temp; quickSort1(array, l, m - 1); quickSort1(array, m + 1, u); } public static void quickSort(int[] array) { quickSort1(array, 0, array.length - 1); } } ~~~ 容易出错的地方在于当前 partition 结束时未将 iii 和 mmm 交换。比较`alist[i]`和`alist[l]`时只能使用`<`而不是`<=`! 因为只有取`<`才能进入收敛条件,`<=`则可能会出现死循环,因为在`=`时第一个元素可能保持不变进而产生死循环。 相应的结果输出为: ~~~ [6, 5, 3, 1, 8, 7, 2, 4] [4, 5, 3, 1, 2, 6, 8, 7] [2, 3, 1, 4, 5, 6, 8, 7] [1, 2, 3, 4, 5, 6, 8, 7] [1, 2, 3, 4, 5, 6, 8, 7] [1, 2, 3, 4, 5, 6, 8, 7] [1, 2, 3, 4, 5, 6, 8, 7] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] ~~~ ### Two-way partitioning 对于仅使用一个索引进行 partition 操作的快排对于随机分布数列的效果还是不错的,但若数组本身就已经有序或者相等的情况下,每次划分仅能确定一个元素的最终位置,故最坏情况下的时间复杂度变为 O(n2)O(n^2)O(n2). 那么有什么办法尽可能避免这种最坏情况吗?聪明的人类总是能找到更好地解决办法——使用两个索引分别向右向左进行 partition. 先来一张动图看看使用两个索引进行 partition 的过程。 ![Quick Sort two index for partition](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2015-10-24_562b1f33d5bc4.gif) 1. 选中`3`作为基准 1. `lo`指针指向元素`6`, `hi`指针指向`4`, 移动`lo`直至其指向的元素大于等于`3`, 移动`hi`直至其指向的元素小于`3`。找到后交换`lo`和`hi`指向的元素——交换元素`6`和`2`。 1. `lo`递增,`hi`递减,重复步骤2,此时`lo`指向元素为`5`, `hi`指向元素为`1`. 交换元素。 1. `lo`递增,`hi`递减,发现其指向元素相同,此轮划分结束。递归排序元素`3`左右两边的元素。 对上述过程进行适当的抽象: 1. 下标 iii 和 jjj 初始化为待排序数组的两端。 1. 基准元素设置为数组的第一个元素。 1. 执行 partition 操作,大循环内包含两个内循环: - 左侧内循环自增 iii, 直到遇到**不小于**基准元素的值为止。 - 右侧内循环自减 jjj, 直到遇到**小于**基准元素的值为止。 1. 大循环测试两个下标是否相等或交叉,交换其值。 这样一来对于数组元素均相等的情形下,每次 partition 恰好在中间元素,故共递归调用 logn\log nlogn 次,每层递归调用进行 partition 操作的比较次数总和近似为 nnn. 故总计需 nlognn \log nnlogn 次比较。[programming_pearls](#) ### Python ~~~ #!/usr/bin/env python def qsort3(alist, l, u): print(alist) if l >= u: return t = alist[l] i = l + 1 j = u while True: while i <= u and alist[i] < t: i += 1 while alist[j] > t: j -= 1 if i > j: break # swap after make sure i > j alist[i], alist[j] = alist[j], alist[i] # do not forget swap l and j alist[l], alist[j] = alist[j], alist[l] qsort3(alist, l, j - 1) qsort3(alist, j + 1, u) unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4] print(qsort3(unsortedArray, 0, len(unsortedArray) - 1)) ~~~ ### Java ~~~ public class Sort { public static void main(String[] args) { int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4}; quickSort(unsortedArray); System.out.println("After sort: "); for (int item : unsortedArray) { System.out.print(item + " "); } } public static void quickSort2(int[] array, int l, int u) { for (int item : array) { System.out.print(item + " "); } System.out.println(); if (l >= u) return; int pivot = array[l]; int left = l + 1; int right = u; while (left <= right) { while (left <= right && array[left] < pivot) { left++; } while (left <= right && array[right] >= pivot) { right--; } if (left > right) break; // swap array[left] with array[right] while left <= right int temp = array[left]; array[left] = array[right]; array[right] = temp; } /* swap the smaller with pivot */ int temp = array[right]; array[right] = array[l]; array[l] = temp; quickSort2(array, l, right - 1); quickSort2(array, right + 1, u); } public static void quickSort(int[] array) { quickSort2(array, 0, array.length - 1); } } ~~~ 相应的输出为: ~~~ [6, 5, 3, 1, 8, 7, 2, 4] [2, 5, 3, 1, 4, 6, 7, 8] [1, 2, 3, 5, 4, 6, 7, 8] [1, 2, 3, 5, 4, 6, 7, 8] [1, 2, 3, 5, 4, 6, 7, 8] [1, 2, 3, 5, 4, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4, 5, 6, 7, 8] ~~~ 从以上3种快排的实现我们可以发现其与『归并排序』的区别主要有如下两点: 1. 归并排序将数组分成两个子数组分别排序,并将有序的子数组归并以将整个数组排序。递归调用发生在处理整个数组之前。 1. 快速排序将一个数组分成两个子数组并对这两个子数组独立地排序,两个子数组有序时整个数组也就有序了。递归调用发生在处理整个数组之后。 Robert Sedgewick 在其网站上对 [Quicksort](http://algs4.cs.princeton.edu/23quicksort/) 做了较为完整的介绍,建议去围观下。 ### Reference - [快速排序 - 维基百科,自由的百科全书](http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F) - [Quicksort | Robert Sedgewick](http://algs4.cs.princeton.edu/23quicksort/) - Programming Pearls Column 11 Sorting - 深入探讨了插入排序和快速排序 - [Quicksort Analysis](#) - programming_pearls > . Programming Pearls(第二版修订版) 一书中第11章排序中注明需要 nlog2nn\log2nnlog2n > 次比较,翻译有误? [ ↩](# "Jump back to footnote [programming_pearls] in the text.")
';