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

注: ACM = Association for Computing Machinery,国际计算机学会,世界性的计算机从业员专业组织,创立于1947年,是世界上第一个科学性及教育性计算机学会。

快速排序是对冒泡排序的一种改进,也属于交换类的排序算法。

一、算法介绍

快速排序通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

步骤如下:

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

举一个例子:5 9 1 6 8 14 6 49 25 4 6 3

  1. 一般取第一个数 5 作为基准,从它左边和最后一个数使用[]进行标志,
  2. 如果左边的数比基准数大,那么该数要往右边扔,也就是两个[]数交换,这样大于它的数就在右边了,然后右边[]数左移,否则左边[]数右移。
  3. 5 [9] 1 6 8 14 6 49 25 4 6 [3] 因为 9 > 5,两个[]交换位置后,右边[]左移
  4. 5 [3] 1 6 8 14 6 49 25 4 [6] 9 因为 3 !> 5,两个[]不需要交换,左边[]右移
  5. 5 3 [1] 6 8 14 6 49 25 4 [6] 9 因为 1 !> 5,两个[]不需要交换,左边[]右移
  6. 5 3 1 [6] 8 14 6 49 25 4 [6] 9 因为 6 > 5,两个[]交换位置后,右边[]左移
  7. 5 3 1 [6] 8 14 6 49 25 [4] 6 9 因为 6 > 5,两个[]交换位置后,右边[]左移
  8. 5 3 1 [4] 8 14 6 49 [25] 6 6 9 因为 4 !> 5,两个[]不需要交换,左边[]右移
  9. 5 3 1 4 [8] 14 6 49 [25] 6 6 9 因为 8 > 5,两个[]交换位置后,右边[]左移
  10. 5 3 1 4 [25] 14 6 [49] 8 6 6 9 因为 25 > 5,两个[]交换位置后,右边[]左移
  11. 5 3 1 4 [49] 14 [6] 25 8 6 6 9 因为 49 > 5,两个[]交换位置后,右边[]左移
  12. 5 3 1 4 [6] [14] 49 25 8 6 6 9 因为 6 > 5,两个[]交换位置后,右边[]左移
  13. 5 3 1 4 [14] 6 49 25 8 6 6 9 两个[]已经汇总,因为 14 > 5,所以 5 和[]之前的数 4 交换位置
  14. 第一轮切分结果:4 3 1 5 14 6 49 25 8 6 6 9
  15. 现在第一轮快速排序已经将数列分成两个部分:
  16. 4 3 1 14 6 49 25 8 6 6 9
  17. 左边的数列都小于 5,右边的数列都大于 5
  18. 使用递归分别对两个数列进行快速排序。

快速排序主要靠基准数进行切分,将数列分成两部分,一部分比基准数都小,一部分比基准数都大。

在最好情况下,每一轮都能平均切分,这样遍历元素只要 n/2 次就可以把数列分成两部分,每一轮的时间复杂度都是:O(n)。因为问题规模每次被折半,折半的数列继续递归进行切分,也就是总的时间复杂度计算公式为: T(n) = 2*T(n/2) + O(n)。按照主定理公式计算,我们可以知道时间复杂度为:O(nlogn),当然我们可以来具体计算一下:

  1. 我们来分析最好情况,每次切分遍历元素的次数为 n/2
  2. T(n) = 2*T(n/2) + n/2
  3. T(n/2) = 2*T(n/4) + n/4
  4. T(n/4) = 2*T(n/8) + n/8
  5. T(n/8) = 2*T(n/16) + n/16
  6. ...
  7. T(4) = 2*T(2) + 4
  8. T(2) = 2*T(1) + 2
  9. T(1) = 1
  10. 进行合并也就是:
  11. T(n) = 2*T(n/2) + n/2
  12. = 2^2*T(n/4)+ n/2 + n/2
  13. = 2^3*T(n/8) + n/2 + n/2 + n/2
  14. = 2^4*T(n/16) + n/2 + n/2 + n/2 + n/2
  15. = ...
  16. = 2^logn*T(1) + logn * n/2
  17. = 2^logn + 1/2*nlogn
  18. = n + 1/2*nlogn
  19. 因为当问题规模 n 趋于无穷大时 nlogn n 大,所以 T(n) = O(nlogn)。
  20. 最好时间复杂度为:O(nlogn)。

最差的情况下,每次都不能平均地切分,每次切分都因为基准数是最大的或者最小的,不能分成两个数列,这样时间复杂度变为了 T(n) = T(n-1) + O(n),按照主定理计算可以知道时间复杂度为:O(n^2),我们可以来实际计算一下:

  1. 我们来分析最差情况,每次切分遍历元素的次数为 n
  2. T(n) = T(n-1) + n
  3. = T(n-2) + n-1 + n
  4. = T(n-3) + n-2 + n-1 + n
  5. = ...
  6. = T(1) + 2 +3 + ... + n-2 + n-1 + n
  7. = O(n^2)
  8. 最差时间复杂度为:O(n^2)。

根据熵的概念,数量越大,随机性越高,越自发无序,所以待排序数据规模非常大时,出现最差情况的情形较少。在综合情况下,快速排序的平均时间复杂度为:O(nlogn)。对比之前介绍的排序算法,快速排序比那些动不动就是平方级别的初级排序算法更佳。

切分的结果极大地影响快速排序的性能,为了避免切分不均匀情况的发生,有几种方法改进:

  1. 每次进行快速排序切分时,先将数列随机打乱,再进行切分,这样随机加了个震荡,减少不均匀的情况。当然,也可以随机选择一个基准数,而不是选第一个数。
  2. 每次取数列头部,中部,尾部三个数,取三个数的中位数为基准数进行切分。

方法 1 相对好,而方法 2 引入了额外的比较操作,一般情况下我们可以随机选择一个基准数。

快速排序使用原地排序,存储空间复杂度为:O(1)。而因为递归栈的影响,递归的程序栈开辟的层数范围在 logn~n,所以递归栈的空间复杂度为:O(logn)~log(n),最坏为:log(n),当元素较多时,程序栈可能溢出。通过改进算法,使用伪尾递归进行优化,递归栈的空间复杂度可以减小到 O(logn),可以见下面算法优化。

快速排序是不稳定的,因为切分过程中进行了交换,相同值的元素可能发生位置变化。

二、算法实现

  1. package main
  2. import "fmt"
  3. // 普通快速排序
  4. func QuickSort(array []int, begin, end int) {
  5. if begin < end {
  6. // 进行切分
  7. loc := partition(array, begin, end)
  8. // 对左部分进行快排
  9. QuickSort(array, begin, loc-1)
  10. // 对右部分进行快排
  11. QuickSort(array, loc+1, end)
  12. }
  13. }
  14. // 切分函数,并返回切分元素的下标
  15. func partition(array []int, begin, end int) int {
  16. i := begin + 1 // 将array[begin]作为基准数,因此从array[begin+1]开始与基准数比较!
  17. j := end // array[end]是数组的最后一位
  18. // 没重合之前
  19. for i < j {
  20. if array[i] > array[begin] {
  21. array[i], array[j] = array[j], array[i] // 交换
  22. j--
  23. } else {
  24. i++
  25. }
  26. }
  27. /* 跳出while循环后,i = j。
  28. * 此时数组被分割成两个部分 --> array[begin+1] ~ array[i-1] < array[begin]
  29. * --> array[i+1] ~ array[end] > array[begin]
  30. * 这个时候将数组array分成两个部分,再将array[i]与array[begin]进行比较,决定array[i]的位置。
  31. * 最后将array[i]与array[begin]交换,进行两个分割部分的排序!以此类推,直到最后i = j不满足条件就退出!
  32. */
  33. if array[i] >= array[begin] { // 这里必须要取等“>=”,否则数组元素由相同的值组成时,会出现错误!
  34. i--
  35. }
  36. array[begin], array[i] = array[i], array[begin]
  37. return i
  38. }
  39. func main() {
  40. list := []int{5}
  41. QuickSort(list, 0, len(list)-1)
  42. fmt.Println(list)
  43. list1 := []int{5, 9}
  44. QuickSort(list1, 0, len(list1)-1)
  45. fmt.Println(list1)
  46. list2 := []int{5, 9, 1}
  47. QuickSort(list2, 0, len(list2)-1)
  48. fmt.Println(list2)
  49. list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
  50. QuickSort(list3, 0, len(list3)-1)
  51. fmt.Println(list3)
  52. }

输出:

  1. [5]
  2. [5 9]
  3. [1 5 9]
  4. [1 3 4 5 6 6 6 8 9 14 25 49]

示例图:

快速排序 - 图1

快速排序,每一次切分都维护两个下标,进行推进,最后将数列分成两部分。

[三、算法改进

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

  1. 在小规模数组的情况下,直接插入排序的效率最好,当快速排序递归部分进入小数组范围,可以切换成直接插入排序。
  2. 排序数列可能存在大量重复值,使用三向切分快速排序,将数组分成三部分,大于基准数,等于基准数,小于基准数,这个时候需要维护三个下标。
  3. 使用伪尾递归减少程序栈空间占用,使得栈空间复杂度从 O(logn)~log(n) 变为:O(logn)

3.1 改进:小规模数组使用直接插入排序

  1. func QuickSort1(array []int, begin, end int) {
  2. if begin < end {
  3. // 当数组小于 4 时使用直接插入排序
  4. if end-begin <= 4 {
  5. InsertSort(array[begin : end+1])
  6. return
  7. }
  8. // 进行切分
  9. loc := partition(array, begin, end)
  10. // 对左部分进行快排
  11. QuickSort1(array, begin, loc-1)
  12. // 对右部分进行快排
  13. QuickSort1(array, loc+1, end)
  14. }
  15. }

直接插入排序在小规模数组下效率极好,我们只需将 end-begin <= 4 的递归部分换成直接插入排序,这部分表示小数组排序。

3.2 改进:三向切分

  1. package main
  2. import "fmt"
  3. // 三切分的快速排序
  4. func QuickSort2(array []int, begin, end int) {
  5. if begin < end {
  6. // 三向切分函数,返回左边和右边下标
  7. lt, gt := partition3(array, begin, end)
  8. // 从lt到gt的部分是三切分的中间数列
  9. // 左边三向快排
  10. QuickSort2(array, begin, lt-1)
  11. // 右边三向快排
  12. QuickSort2(array, gt+1, end)
  13. }
  14. }
  15. // 切分函数,并返回切分元素的下标
  16. func partition3(array []int, begin, end int) (int, int) {
  17. lt := begin // 左下标从第一位开始
  18. gt := end // 右下标是数组的最后一位
  19. i := begin + 1 // 中间下标,从第二位开始
  20. v := array[begin] // 基准数
  21. // 以中间坐标为准
  22. for i <= gt {
  23. if array[i] > v { // 大于基准数,那么交换,右指针左移
  24. array[i], array[gt] = array[gt], array[i]
  25. gt--
  26. } else if array[i] < v { // 小于基准数,那么交换,左指针右移
  27. array[i], array[lt] = array[lt], array[i]
  28. lt++
  29. i++
  30. } else {
  31. i++
  32. }
  33. }
  34. return lt, gt
  35. }

演示:

  1. 数列:4 8 2 4 4 4 7 9,基准数为 4
  2. [4] [8] 2 4 4 4 7 [9] 从中间[]开始:8 > 4,中右[]进行交换,右边[]左移
  3. [4] [9] 2 4 4 4 [7] 8 从中间[]开始:9 > 4,中右[]进行交换,右边[]左移
  4. [4] [7] 2 4 4 [4] 9 8 从中间[]开始:7 > 4,中右[]进行交换,右边[]左移
  5. [4] [4] 2 4 [4] 7 9 8 从中间[]开始:4 == 4,不需要交换,中间[]右移
  6. [4] 4 [2] 4 [4] 7 9 8 从中间[]开始:2 < 4,中左[]需要交换,中间和左边[]右移
  7. 2 [4] 4 [4] [4] 7 9 8 从中间[]开始:4 == 4,不需要交换,中间[]右移
  8. 2 [4] 4 4 [[4]] 7 9 8 从中间[]开始:4 == 4,不需要交换,中间[]右移,因为已经重叠了
  9. 第一轮结果:2 4 4 4 4 7 9 8
  10. 分成三个数列:
  11. 2
  12. 4 4 4 4 (元素相同的会聚集在中间数列)
  13. 7 9 8
  14. 接着对第一个和最后一个数列进行递归即可。

示例图:

快速排序 - 图2

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

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

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

快速排序 - 图3

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

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

注:艾兹格·W·迪科斯彻(Edsger Wybe Dijkstra,1930年5月11日~2002年8月6日),荷兰人,计算机科学家,曾获图灵奖。

3.3 改进:伪尾递归优化

  1. // 伪尾递归快速排序
  2. func QuickSort3(array []int, begin, end int) {
  3. for begin < end {
  4. // 进行切分
  5. loc := partition(array, begin, end)
  6. // 那边元素少先排哪边
  7. if loc-begin < end-loc {
  8. // 先排左边
  9. QuickSort3(array, begin, loc-1)
  10. begin = loc + 1
  11. } else {
  12. // 先排右边
  13. QuickSort3(array, loc+1, end)
  14. end = loc - 1
  15. }
  16. }
  17. }

很多人以为这样子是尾递归。其实这样的快排写法是伪装的尾递归,不是真正的尾递归,因为有 for 循环,不是直接 return QuickSort,递归还是不断地压栈,栈的层次仍然不断地增长。

但是,因为先让规模小的部分排序,栈的深度大大减少,程序栈最深不会超过 logn 层,这样堆栈最坏空间复杂度从 O(n) 降为 O(logn)

这种优化也是一种很好的优化,因为栈的层数减少了,对于排序十亿个整数,也只要:log(100 0000 0000)=29.897,占用的堆栈层数最多 30 层,比不进行优化,可能出现的 O(n) 常数层好很多。

四、补充:非递归写法

非递归写法仅仅是将之前的递归栈转化为自己维持的手工栈。

  1. // 非递归快速排序
  2. func QuickSort5(array []int) {
  3. // 人工栈
  4. helpStack := new(LinkStack)
  5. // 第一次初始化栈,推入下标0,len(array)-1,表示第一次对全数组范围切分
  6. helpStack.Push(len(array) - 1)
  7. helpStack.Push(0)
  8. // 栈非空证明存在未排序的部分
  9. for !helpStack.IsEmpty() {
  10. // 出栈,对begin-end范围进行切分排序
  11. begin := helpStack.Pop() // 范围区间左边
  12. end := helpStack.Pop() // 范围
  13. // 进行切分
  14. loc := partition(array, begin, end)
  15. // 右边范围入栈
  16. if loc+1 < end {
  17. helpStack.Push(end)
  18. helpStack.Push(loc + 1)
  19. }
  20. // 左边返回入栈
  21. if begin < loc-1 {
  22. helpStack.Push(loc - 1)
  23. helpStack.Push(begin)
  24. }
  25. }
  26. }

本来需要进行递归的数组范围 begin,end,不使用递归,依次推入自己的人工栈,然后循环对人工栈进行处理。

我们可以看到没有递归,程序栈空间复杂度变为了:O(1),但额外的存储空间产生了。

辅助人工栈结构 helpStack 占用了额外的空间,存储空间由原地排序的 O(1) 变成了 O(logn)~log(n)

我们可以参考上面的伪尾递归版本,继续优化非递归版本,先让短一点的范围入栈,这样存储复杂度可以变为:O(logn)。如:

  1. // 非递归快速排序优化
  2. func QuickSort6(array []int) {
  3. // 人工栈
  4. helpStack := new(LinkStack)
  5. // 第一次初始化栈,推入下标0,len(array)-1,表示第一次对全数组范围切分
  6. helpStack.Push(len(array) - 1)
  7. helpStack.Push(0)
  8. // 栈非空证明存在未排序的部分
  9. for !helpStack.IsEmpty() {
  10. // 出栈,对begin-end范围进行切分排序
  11. begin := helpStack.Pop() // 范围区间左边
  12. end := helpStack.Pop() // 范围
  13. // 进行切分
  14. loc := partition(array, begin, end)
  15. // 切分后右边范围大小
  16. rSize := -1
  17. // 切分后左边范围大小
  18. lSize := -1
  19. // 右边范围入栈
  20. if loc+1 < end {
  21. rSize = end - (loc + 1)
  22. }
  23. // 左边返回入栈
  24. if begin < loc-1 {
  25. lSize = loc - 1 - begin
  26. }
  27. // 两个范围,让范围小的先入栈,减少人工栈空间
  28. if rSize != -1 && lSize != -1 {
  29. if lSize > rSize {
  30. helpStack.Push(end)
  31. helpStack.Push(loc + 1)
  32. helpStack.Push(loc - 1)
  33. helpStack.Push(begin)
  34. } else {
  35. helpStack.Push(loc - 1)
  36. helpStack.Push(begin)
  37. helpStack.Push(end)
  38. helpStack.Push(loc + 1)
  39. }
  40. } else {
  41. if rSize != -1 {
  42. helpStack.Push(end)
  43. helpStack.Push(loc + 1)
  44. }
  45. if lSize != -1 {
  46. helpStack.Push(loc - 1)
  47. helpStack.Push(begin)
  48. }
  49. }
  50. }
  51. }

完整的程序如下:

  1. package main
  2. import (
  3. "fmt"
  4. "sync"
  5. )
  6. // 链表栈,后进先出
  7. type LinkStack struct {
  8. root *LinkNode // 链表起点
  9. size int // 栈的元素数量
  10. lock sync.Mutex // 为了并发安全使用的锁
  11. }
  12. // 链表节点
  13. type LinkNode struct {
  14. Next *LinkNode
  15. Value int
  16. }
  17. // 入栈
  18. func (stack *LinkStack) Push(v int) {
  19. stack.lock.Lock()
  20. defer stack.lock.Unlock()
  21. // 如果栈顶为空,那么增加节点
  22. if stack.root == nil {
  23. stack.root = new(LinkNode)
  24. stack.root.Value = v
  25. } else {
  26. // 否则新元素插入链表的头部
  27. // 原来的链表
  28. preNode := stack.root
  29. // 新节点
  30. newNode := new(LinkNode)
  31. newNode.Value = v
  32. // 原来的链表链接到新元素后面
  33. newNode.Next = preNode
  34. // 将新节点放在头部
  35. stack.root = newNode
  36. }
  37. // 栈中元素数量+1
  38. stack.size = stack.size + 1
  39. }
  40. // 出栈
  41. func (stack *LinkStack) Pop() int {
  42. stack.lock.Lock()
  43. defer stack.lock.Unlock()
  44. // 栈中元素已空
  45. if stack.size == 0 {
  46. panic("empty")
  47. }
  48. // 顶部元素要出栈
  49. topNode := stack.root
  50. v := topNode.Value
  51. // 将顶部元素的后继链接链上
  52. stack.root = topNode.Next
  53. // 栈中元素数量-1
  54. stack.size = stack.size - 1
  55. return v
  56. }
  57. // 栈是否为空
  58. func (stack *LinkStack) IsEmpty() bool {
  59. return stack.size == 0
  60. }
  61. // 非递归快速排序
  62. func QuickSort5(array []int) {
  63. // 人工栈
  64. helpStack := new(LinkStack)
  65. // 第一次初始化栈,推入下标0,len(array)-1,表示第一次对全数组范围切分
  66. helpStack.Push(len(array) - 1)
  67. helpStack.Push(0)
  68. // 栈非空证明存在未排序的部分
  69. for !helpStack.IsEmpty() {
  70. // 出栈,对begin-end范围进行切分排序
  71. begin := helpStack.Pop() // 范围区间左边
  72. end := helpStack.Pop() // 范围
  73. // 进行切分
  74. loc := partition(array, begin, end)
  75. // 右边范围入栈
  76. if loc+1 < end {
  77. helpStack.Push(end)
  78. helpStack.Push(loc + 1)
  79. }
  80. // 左边返回入栈
  81. if begin < loc-1 {
  82. helpStack.Push(loc - 1)
  83. helpStack.Push(begin)
  84. }
  85. }
  86. }
  87. // 非递归快速排序优化
  88. func QuickSort6(array []int) {
  89. // 人工栈
  90. helpStack := new(LinkStack)
  91. // 第一次初始化栈,推入下标0,len(array)-1,表示第一次对全数组范围切分
  92. helpStack.Push(len(array) - 1)
  93. helpStack.Push(0)
  94. // 栈非空证明存在未排序的部分
  95. for !helpStack.IsEmpty() {
  96. // 出栈,对begin-end范围进行切分排序
  97. begin := helpStack.Pop() // 范围区间左边
  98. end := helpStack.Pop() // 范围
  99. // 进行切分
  100. loc := partition(array, begin, end)
  101. // 切分后右边范围大小
  102. rSize := -1
  103. // 切分后左边范围大小
  104. lSize := -1
  105. // 右边范围入栈
  106. if loc+1 < end {
  107. rSize = end - (loc + 1)
  108. }
  109. // 左边返回入栈
  110. if begin < loc-1 {
  111. lSize = loc - 1 - begin
  112. }
  113. // 两个范围,让范围小的先入栈,减少人工栈空间
  114. if rSize != -1 && lSize != -1 {
  115. if lSize > rSize {
  116. helpStack.Push(end)
  117. helpStack.Push(loc + 1)
  118. helpStack.Push(loc - 1)
  119. helpStack.Push(begin)
  120. } else {
  121. helpStack.Push(loc - 1)
  122. helpStack.Push(begin)
  123. helpStack.Push(end)
  124. helpStack.Push(loc + 1)
  125. }
  126. } else {
  127. if rSize != -1 {
  128. helpStack.Push(end)
  129. helpStack.Push(loc + 1)
  130. }
  131. if lSize != -1 {
  132. helpStack.Push(loc - 1)
  133. helpStack.Push(begin)
  134. }
  135. }
  136. }
  137. }
  138. // 切分函数,并返回切分元素的下标
  139. func partition(array []int, begin, end int) int {
  140. i := begin + 1 // 将array[begin]作为基准数,因此从array[begin+1]开始与基准数比较!
  141. j := end // array[end]是数组的最后一位
  142. // 没重合之前
  143. for i < j {
  144. if array[i] > array[begin] {
  145. array[i], array[j] = array[j], array[i] // 交换
  146. j--
  147. } else {
  148. i++
  149. }
  150. }
  151. /* 跳出while循环后,i = j。
  152. * 此时数组被分割成两个部分 --> array[begin+1] ~ array[i-1] < array[begin]
  153. * --> array[i+1] ~ array[end] > array[begin]
  154. * 这个时候将数组array分成两个部分,再将array[i]与array[begin]进行比较,决定array[i]的位置。
  155. * 最后将array[i]与array[begin]交换,进行两个分割部分的排序!以此类推,直到最后i = j不满足条件就退出!
  156. */
  157. if array[i] >= array[begin] { // 这里必须要取等“>=”,否则数组元素由相同的值组成时,会出现错误!
  158. i--
  159. }
  160. array[begin], array[i] = array[i], array[begin]
  161. return i
  162. }
  163. func main() {
  164. list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
  165. QuickSort5(list3)
  166. fmt.Println(list3)
  167. list4 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
  168. QuickSort6(list4)
  169. fmt.Println(list4)
  170. }

输出:

  1. [1 3 4 5 6 6 6 8 9 14 25 49]
  2. [1 3 4 5 6 6 6 8 9 14 25 49]

使用人工栈替代递归的程序栈,换汤不换药,速度并没有什么变化,但是代码可读性降低。

五、补充:内置库使用快速排序的原因

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

  1. 这个问题有偏颇,选择排序算法要看具体的场景,Linux 内核用的排序算法就是堆排序,而 Java 对于数量比较多的复杂对象排序,内置排序使用的是归并排序,只是一般情况下,快速排序更快。
  2. 归并排序有两个稳定,第一个稳定是排序前后相同的元素位置不变,第二个稳定是,每次都是很平均地进行排序,读取数据也是顺序读取,能够利用存储器缓存的特征,比如从磁盘读取数据进行排序。因为排序过程需要占用额外的辅助数组空间,所以这部分有代价损耗,但是原地手摇的归并排序克服了这个缺陷。
  3. 复杂度中,大 O 有一个常数项被省略了,堆排序每次取最大的值之后,都需要进行节点翻转,重新恢复堆的特征,做了大量无用功,常数项比快速排序大,大部分情况下比快速排序慢很多。但是堆排序时间较稳定,不会出现快排最坏 O(n^2) 的情况,且省空间,不需要额外的存储空间和栈空间。
  4. 当待排序数量大于16000个元素时,使用自底向上的堆排序比快速排序还快,可见此:https://core.ac.uk/download/pdf/82350265.pdf (opens new window)
  5. 快速排序最坏情况下复杂度高,主要在于切分不像归并排序一样平均,而是很依赖基准数的现在,我们通过改进,比如随机数,三切分等,这种最坏情况的概率极大的降低。大多数情况下,它并不会那么地坏,大多数快才是真的块。
  6. 归并排序和快速排序都是分治法,排序的数据都是相邻的,而堆排序比较的数可能跨越很大的范围,导致局部性命中率降低,不能利用现代存储器缓存的特征,加载数据过程会损失性能。

对稳定性有要求的,要求排序前后相同元素位置不变,可以使用归并排序,Java 中的复杂对象类型,要求排序前后位置不能发生变化,所以小规模数据下使用了直接插入排序,大规模数据下使用了归并排序。

对栈,存储空间有要求的可以使用堆排序,比如 Linux 内核栈小,快速排序占用程序栈太大了,使用快速排序可能栈溢出,所以使用了堆排序。

Golang 中,标准库 sort 中对切片进行稳定排序:

  1. func SliceStable(slice interface{}, less func(i, j int) bool) {
  2. rv := reflectValueOf(slice)
  3. swap := reflectSwapper(slice)
  4. stable_func(lessSwap{less, swap}, rv.Len())
  5. }
  6. func stable_func(data lessSwap, n int) {
  7. blockSize := 20
  8. a, b := 0, blockSize
  9. for b <= n {
  10. insertionSort_func(data, a, b)
  11. a = b
  12. b += blockSize
  13. }
  14. insertionSort_func(data, a, n)
  15. for blockSize < n {
  16. a, b = 0, 2*blockSize
  17. for b <= n {
  18. symMerge_func(data, a, a+blockSize, b)
  19. a = b
  20. b += 2 * blockSize
  21. }
  22. if m := a + blockSize; m < n {
  23. symMerge_func(data, a, m, n)
  24. }
  25. blockSize *= 2
  26. }
  27. }

会先按照 20 个元素的范围,对整个切片分段进行插入排序,因为小数组插入排序效率高,然后再对这些已排好序的小数组进行归并排序。其中归并排序还使用了原地排序,节约了辅助空间。

而一般的排序:

  1. func Slice(slice interface{}, less func(i, j int) bool) {
  2. rv := reflectValueOf(slice)
  3. swap := reflectSwapper(slice)
  4. length := rv.Len()
  5. quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
  6. }
  7. func quickSort_func(data lessSwap, a, b, maxDepth int) {
  8. for b-a > 12 {
  9. if maxDepth == 0 {
  10. heapSort_func(data, a, b)
  11. return
  12. }
  13. maxDepth--
  14. mlo, mhi := doPivot_func(data, a, b)
  15. if mlo-a < b-mhi {
  16. quickSort_func(data, a, mlo, maxDepth)
  17. a = mhi
  18. } else {
  19. quickSort_func(data, mhi, b, maxDepth)
  20. b = mlo
  21. }
  22. }
  23. if b-a > 1 {
  24. for i := a + 6; i < b; i++ {
  25. if data.Less(i, i-6) {
  26. data.Swap(i, i-6)
  27. }
  28. }
  29. insertionSort_func(data, a, b)
  30. }
  31. }
  32. func doPivot_func(data lessSwap, lo, hi int) (midlo, midhi int) {
  33. m := int(uint(lo+hi) >> 1)
  34. if hi-lo > 40 {
  35. s := (hi - lo) / 8
  36. medianOfThree_func(data, lo, lo+s, lo+2*s)
  37. medianOfThree_func(data, m, m-s, m+s)
  38. medianOfThree_func(data, hi-1, hi-1-s, hi-1-2*s)
  39. }
  40. medianOfThree_func(data, lo, m, hi-1)
  41. pivot := lo
  42. a, c := lo+1, hi-1
  43. for ; a < c && data.Less(a, pivot); a++ {
  44. }
  45. b := a
  46. for {
  47. for ; b < c && !data.Less(pivot, b); b++ {
  48. }
  49. for ; b < c && data.Less(pivot, c-1); c-- {
  50. }
  51. if b >= c {
  52. break
  53. }
  54. data.Swap(b, c-1)
  55. b++
  56. c--
  57. }
  58. protect := hi-c < 5
  59. if !protect && hi-c < (hi-lo)/4 {
  60. dups := 0
  61. if !data.Less(pivot, hi-1) {
  62. data.Swap(c, hi-1)
  63. c++
  64. dups++
  65. }
  66. if !data.Less(b-1, pivot) {
  67. b--
  68. dups++
  69. }
  70. if !data.Less(m, pivot) {
  71. data.Swap(m, b-1)
  72. b--
  73. dups++
  74. }
  75. protect = dups > 1
  76. }
  77. if protect {
  78. for {
  79. for ; a < b && !data.Less(b-1, pivot); b-- {
  80. }
  81. for ; a < b && data.Less(a, pivot); a++ {
  82. }
  83. if a >= b {
  84. break
  85. }
  86. data.Swap(a, b-1)
  87. a++
  88. b--
  89. }
  90. }
  91. data.Swap(pivot, b-1)
  92. return b - 1, c
  93. }

快速排序限制程序栈的层数为: 2*ceil(log(n+1)),当递归超过该层时表示程序栈过深,那么转为堆排序。

上述快速排序还使用了三种优化,第一种是递归时小数组转为插入排序,第二种是使用了中位数基准数,第三种使用了三切分。