快速排序基准数字为中间_快速排序之入门到"放弃"

快速排序之入门到"放弃"

摘要

快速排序是一种分治策略的排序算法，是由英国计算机科学家 Tony Hoare 发明的， 该算法被发布在 1961 年的 Communications of the ACM 国际计算机学会月刊。

快速排序是对冒泡排序的一种改进，也属于交换类的排序算法。它也是八大排序算法中最常用的经典排序算法之一。其广泛应用的主要原因是高效，核心算法思想是「分而治之」。快速排序经常会被作为面试题进行考察，通常的考察思路是快排思想、编码实践之手写快排以及进一步对快排的优化。

算法思想

「快速排序的核心思想是分治」：选择数组中某个数作为「基数」，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数都比基数小，另外一部分的所有数都都比基数大，然后再按此方法对这两部分数据分别进行快速排序，循环递归，最终使整个数组变成有序。

步骤如下:

1. 先从数列中取出一个数作为基准数。一般取第一个数。
2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3. 再对左右区间重复第二步，直到各区间只有一个数。

基数选择

由于快速排序需要选定一个基数进行划分排序，关于基数选择有很多方式，「而基数选择直接关系到快排的效率」。事实上，选取基准元素应该遵循平衡子问题的原则：「即使得划分后的两个子序列的长度尽量相同本篇以待排序数组首元素作为基数进行说明」。**本文演示,我们将采用数组的第一个元素作为基准元素进行讲解。 **

基数选择的常见的几种策略如下示:

选择第一个或者最后一个

如果待排序数是随机的，那么选择第一个或者最后一个作基准是没有什么问题的，这也是我们最常见到的选择方案。但如果待排序数据已经排好序的，就会产生一个很糟糕的分割。几乎所有的数据都被分割到一个集合中，而另一个集合没有数据。这样的情况下，时间花费了，却没有做太多实事。而它的时间复杂度就是最差的情况O(N^2)。「因此这种策略是绝对不推荐的。」

随机选择

随机选择基准是一种比较安全的做法。因为它不会总是产生劣质的分割。

选择三数中值

从前面的描述我们知道，如果能够选择到数据的中值，那是最好的，因为它能够将集合近乎等分为二。但是很多时候很难算出中值，并且会耗费计算时间。因此我们随机选取三个元素，并用它们的中值作为整个数据中值的估计值。在这里，我们选择最左端，最右端和中间位置的三个元素的中值作为基准。

假如有以下数组：

1 9 10 3 8 7 6 2 4

左端元素为1，位置为0，右端元素为4，位置为8，则中间位置为[0+8]/2=4，中间元素为8。那么三数中值就为4（1，4，8的中值）。

图解

假如我们有一个数组序列: [30， 40， 60， 10， 20， 50],那么第一轮的快速排序过程将如下示：

文字描述

假设我们有一个数组序列: [6, 1, 2, 7, 9, 3, 4, 5, 10, 8] 需要排序

首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。为了方便，就让第一个数 6 作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在 6的右边，比基准数小的数放在 6的左边，类似下面这种排列。

3 1 2 5 4 6 9 7 10 8

那么怎么开始呢？

方法其实很简单：分别从初始序列两端开始“探测”。先从右往左找一个小于6 的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量 i 和 j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字**“哨兵 i”「和」“哨兵 j”**。刚开始的时候让哨兵 i 指向序列的最左边（即 i=0），指向数字6。让哨兵 j 指向序列的最右边（即 j=9），指向数字8

1. 哨兵j一步步向左移动(即j--),直到找到一个小于6的数停下来，这里我们找到5(j=7)。接下来哨兵i再一步步向右移动,直到找到一个大于6的数,这里我们找到7(i=3)
2. 现在交换哨兵i和哨兵j对应的值。

3. 至此,第一次交换结束。

4. 接下来哨兵j继续向左移动，找到小于6的元素4(j=6),然后哨兵i继续向右移动，找到大于6的元素9(i=4)

5. 现在交换哨兵i和哨兵j对应的值。

6. 至此，第二次交换结束

7. 哨兵j继续向左移动，找到小于6的元素3(j=5),然后哨兵继续向右移动,此时哨兵i和哨兵j相遇了

8. 此时说明探测结束，我们将基准元素6和哨兵3交换

9. 以6为基准元素的排序结束了，此时元素序列为： [3,1,2,5,4,6,9,7,10,8], 比6小的元素都在左边，比6大的元素都在右边

10. 使用递归分别对两个数列[3,1,2,5,4]和[9.7.10.8]再按上述过程进行快速排序。

一个整体的排序过程:

动图演示

维基百科动图:

实现

基础实现

参照上述讲解的思想和排序过程演示,我们还是可以很容易写出实现代码的。

这里我们先选择第一个元素作为基准元素，下面是我实现的代码:

package sort

func QuickSort(array []int) {
 arrLen := len(array)
 if arrLen < 1 {
  panic("array len is less than 1")
 }
 seperatorSort(array, 0, arrLen-1)
 return
}

func seperatorSort(array []int, start int, end int) {
 if start >= end {
  return
 }
 // 找到分区索引,将该区间分为两段
 pos := patition(array, start, end)
 // 左分区排序
 seperatorSort(array, start, pos-1)
 // 右分区排序
 seperatorSort(array, pos+1, end)
 return
}

func patition(array []int, start int, end int) (pos int) {
 priv := array[start]
 i := start //哨兵i
 j := end   //哨兵j
 for i < j {
  // 从右往左扫描,找到小于基准元素的值
  for array[j] >= priv && i < j {
   j--
  }
  // 从左往右扫描,找到大于基准元素的值
  for array[i] <= priv && i < j {
   i++
  }
  if i < j {
   //哨兵相遇
   array[i], array[j] = array[j], array[i]
  }
 }
 // 交换基准元素和哨兵,使得交换后基准元素左边的都比它小,右边都比它大
 array[i], array[start] = array[start], array[i]
 return i
}

优化

快速排序可以继续进行算法改进:

• 在小规模数组的情况下（N<=20），直接插入排序的效率最好，当快速排序递归部分进入小数组范围，可以切换成直接插入排序 「(因为快速排序有递归开销，并且插入排序是稳定排序)」。
• 排序数列可能存在大量重复值，使用三向切分快速排序，将数组分成三部分，大于基准数，等于基准数，小于基准数，这个时候需要维护三个下标。
• 使用伪尾递归减少程序栈空间占用，使得栈空间复杂度从 O(logn)~log(n) 变为：O(logn)

改进小数组使用直接插入排序

我们直接在分区前判断下区间长度,然后小于指定值使用插入排序即可。实现代码如下示:

package sort
// 小数组序列使用插入排序优化版
func QuickSortOpt1(array []int) {
 arrLen := len(array)
 if arrLen < 1 {
  panic("array len is less than 1")
 }
 seperatorSortOpt1(array, 0, arrLen-1)
 return
}

func seperatorSortOpt1(array []int, start int, end int) {
 if start >= end {
  return
 }
 // 这里当序列<=5时使用插入排序
 if end-start <= 5 {
  InsertSort(array[start : end+1])
  return
 }
 // 找到分区索引,将该区间分为两段
 pos := patition(array, start, end)
 // 左分区排序
 seperatorSortOpt1(array, start, pos-1)
 // 右分区排序
 seperatorSortOpt1(array, pos+1, end)
 return
}

func patition(array []int, start int, end int) (pos int) {
 priv := array[start]
 i := start //哨兵i
 j := end   //哨兵j
 for i < j {
  // 从右往左扫描,找到小于基准元素的值
  for array[j] >= priv && i < j {
   j--
  }
  // 从左往右扫描,找到大于基准元素的值
  for array[i] <= priv && i < j {
   i++
  }
  if i < j {
   //哨兵相遇
   array[i], array[j] = array[j], array[i]
  }
 }
 // 交换基准元素和哨兵,使得交换后基准元素左边的都比它小,右边都比它大
 array[i], array[start] = array[start], array[i]
 return i
}

三向切分

快速排序什么时候不适用？元素重复率特别高的时候。

如何优化？三向切分。前后各俩指针，总共四个指针。俩额外的指针指向跟待选元素相同的元素，最后全部置换到中间。

三向切分的好处？重复率高的时候，避免相同元素来回交换，节省交换次数。对于包含大量重复元素的数组，这个算法将排序时间从线性对数级降到了线性级别。

「三切分，把小于基准数的扔到左边，大于基准数的扔到右边，相同的元素会进行聚集。」

「如果存在大量重复元素，排序速度将极大提高，将会是线性时间，因为相同的元素将会聚集在中间，这些元素不再进入下一个递归迭代。」

三向切分主要来自荷兰国旗三色问题，该问题由 Dijkstra 提出。

假设有一条绳子，上面有红、白、蓝三种颜色的旗子，起初绳子上的旗子颜色并没有顺序，您希望将之分类，并排列为蓝、白、红的顺序，要如何移动次数才会最少，注意您只能在绳子上进行这个动作，而且一次只能调换两个旗子。

可以看到，上面的解答相当于使用三向切分一次，只要我们将白色旗子的值设置为 100，蓝色的旗子值设置为 0，红色旗子值设置为 200，以 100 作为基准数，第一次三向切分后三种颜色的旗就排好了，因为 蓝(0)白(100)红(200)。

演示过程

数列：4 8 2 4 4 4 7 9，基准数为 4

[4] [8] 2 4 4 4 7 [9]  从中间[]开始：8 > 4，中右[]进行交换，右边[]左移
[4] [9] 2 4 4 4 [7] 8  从中间[]开始：9 > 4，中右[]进行交换，右边[]左移
[4] [7] 2 4 4 [4] 9 8  从中间[]开始：7 > 4，中右[]进行交换，右边[]左移
[4] [4] 2 4 [4] 7 9 8  从中间[]开始：4 == 4，不需要交换，中间[]右移
[4] 4 [2] 4 [4] 7 9 8  从中间[]开始：2 < 4，中左[]需要交换，中间和左边[]右移
2 [4] 4 [4] [4] 7 9 8  从中间[]开始：4 == 4，不需要交换，中间[]右移
2 [4] 4 4 [[4]] 7 9 8  从中间[]开始：4 == 4，不需要交换，中间[]右移，因为已经重叠了
第一轮结果：2 4 4 4 4 7 9 8

分成三个数列：

2
4 4 4 4 (元素相同的会聚集在中间数列)
7 9 8

接着对第一个和最后一个数列进行递归即可。

实现代码

基于上述原理,我们也可以写出相应的实现代码。 我实现的代码如下所示:

package sort


// 三向切分法优化版
func QuickSortOpt2(array []int) {
 arrLen := len(array)
 if arrLen < 1 {
  panic("array len is less than 1")
 }
 seperatorSortOpt2(array, 0, arrLen-1)
 return
}

//在lt之前的(start~lt-1)都小于中间值
//在gt之前的(gt+1~end)都大于中间值
//在lt~i-1的都等于中间值
func seperatorSortOpt2(array []int, start int, end int) {
 if start >= end {
  return
 }
 priv := array[start]
 lt := start
 i := start + 1
 gt := end
 for i <= gt {
  if array[i] < priv {
   array[i], array[lt] = array[lt], array[i]
   i++
   lt++
  } else if array[i] > priv {
   array[i], array[gt] = array[gt], array[i]
   gt--
  } else {
   i++
  }
 }
 seperatorSortOpt2(array, start, lt-1)
 seperatorSortOpt2(array, gt+1, end)
 return
}

复杂度

时间复杂度

• 最坏时间复杂度：即元素都分到一个子序列，另一个子序列为空的情况，时间复杂度为O(N2)。
• 最好时间复杂度：即序列是均分为两个子序列，时间复杂度是O(NlogN)，分析与归并排序差不多。
• 平均时间复杂度：O(NlogN)。

空间复杂度

空间复杂度：O(logN)

稳定性

首先给出我们的结论: 快速排序是不稳定的。下面借用一个网上的实例:

假设待排序数组: a = [ 1, 2, 2, 3, 4, 5, 6 ];

在快速排序的随机选择比较子(即pivot)阶段：

若选择a[2]（即数组中的第二个2）为比较子，而把大于等于比较子的数均放置在大数数组中，则a[1]（即数组中的第一个2）会到pivot的右边， 那么数组中的两个2非原序（这就是“不稳定”）。

若选择 a[1] 为比较子，而把小于等于比较子的数均放置在小数数组中，则数组中的两个 2 顺序也非原序 。

这就说明，quick sort是不稳定的。

总结

首先堆排序，归并排序最好最坏时间复杂度都是：O(nlogn)，而快速排序最坏的时间复杂度是：O(n^2)，但是很多编程语言内置的排序算法使用的仍然是快速排序，这是为什么？

• 选择排序算法要看具体的场景，Linux 内核用的排序算法就是堆排序，而 Java 对于数量比较多的复杂对象排序，内置排序使用的是归并排序，只是一般情况下，快速排序更快。
• 归并排序有两个稳定，第一个稳定是排序前后相同的元素位置不变，第二个稳定是，每次都是很平均地进行排序，读取数据也是顺序读取，能够利用存储器缓存的特征，比如从磁盘读取数据进行排序。因为排序过程需要占用额外的辅助数组空间，所以这部分有代价损耗，但是原地手摇的归并排序克服了这个缺陷。
• 快速排序最坏情况下复杂度高，主要在于切分不像归并排序一样平均，而是很依赖基准数的现在，我们通过改进，比如随机数，三切分等，这种最坏情况的概率极大的降低。大多数情况下，它并不会那么地坏，大多数快才是真的块。

总的来说, 快速排序你值得拥有。

参阅

算法 3：最常用的排序——快速排序

快速排序