快速排序

今天我们来聊一聊无论是在笔试还是面试中常常考到的，也是最经典和最高效的快速排序算法。它的平均时间复杂度为 O(NlogN)O(NlogN)，空间复杂度为 O(1)O(1)。

1. 快速排序算法原理

快速排序算法是基于这样的思想：从待排序的列表选择一个基准数，然后将列表中比该基准数大的放到该数的右边，比该基准数小的值放到该基准数的左边；接下来执行递归操作，对基准数左边的待排序列表执行前面同样的操作，直到左边的列表有序，对于基准数右边的待排序列表也执行前面同样的操作，直到右边的列表有序。此时，整个列表有序。即对于输入的数组 nums[left:right]：

  • 分解：以 nums[p] 为基准将 nums[left: right] 划分为三部分: nums[left:p-1]，nums[p] 和 a[p+1:right]，使得 nums[left:p-1] 中任何一个元素小于等于 nums[p]， 而 nums[p+1:right] 中任何一个元素大于等于 nums[p]；
  • 递归求解：通过递归调用快速排序算法分别对 nums[left:p -1] 和 nums[p+1:right] 进行排序；
  • 合并：由于对 nums[left:p-1] 和 nums[p+1:right] 的排序是就地进行的，所以在 nums[left:p-1] 和 nums[p+1:right] 都已排好序后，不需要执行任何计算，nums[left:right] 就已经排好序了；

下面是算法示意图：
快速排序 - 图1
快速排序算法示意图

2. 快速排序空间复杂度优化

可以看到，上述快速排序算法的一个核心步骤是：将列表中的比基准数小的全部移动到基准数的左边，其余数移动到基准数的右边，且整个算法的过程不能使用额外的空间。这样的算法才比较高效，空间复杂度为 O(1)。那么怎么做到不使用额外空间达到这一目的呢？请看下面的示意图进行理解。
快速排序 - 图2
快速排序核心步骤
可以看下快速排序动态图的演示：
快速排序 - 图3
快速排序原理动态图演示
接下来，我们就要使用 Python 实现上面的核心步骤以及最后的快排算法。

3. 快速排序算法的 Python 实现

首先我们实现上面的核心步骤，代码如下：

  1. # 代码位置：sort_algorithms.py
  2. def get_num_position(nums, left, right):
  3.     # 默认基准值为第一个
  4.     base = nums[left]
  5.     while left < right:
  6.         # 从最右边向左直到找到小于基准值的数
  7.         while left < right and nums[right] >= base:
  8.             right -= 1
  9.         # 将小于基准数的值放到右边，left原来位置放的是基准值(base)
  10.         nums[left] = nums[right]
  11.         # 然后从左边往右遍历，直到找到大于基准值的数
  12.         while left < right and nums[left] <= base:
  13.             left += 1
  14.         # 然后将left位置上的值放到right位置上，right位置上的值原本为base值
  15.         nums[right] = nums[left]
  16.     # left=right的位置上就是基准值
  17.     nums[left] = base
  18.     return left
  19. 代码块
  20. • 1
  21. • 2
  22. • 3
  23. • 4
  24. • 5
  25. • 6
  26. • 7
  27. • 8
  28. • 9
  29. • 10
  30. • 11
  31. • 12
  32. • 13
  33. • 14
  34. • 15
  35. • 16
  36. • 17
  37. • 18
  38. • 19

4. 实例测试快速排序代码

上面的函数中我们已经做了详细的注释，和前面第二张图描述的过程是一致的。接下来我们来对该方法进行测试：

  1. PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> python
  2. Python 3.8.2 (tags/v3.8.2:7b3ab59, Feb 25 2020, 22:45:29) [MSC v.1916 32 bit (Intel)] on win32
  3. Type "help", "copyright", "credits" or "license" for more information.
  4. >>> from sort_algorithms import get_num_position
  5. >>> nums = [10, 2, 16, 8, 4, 17, 12, 11]
  6. >>> get_num_position(nums, 0, len(nums) - 1)        
  7. 3
  8. >>> nums      
  9. [4, 2, 8, 10, 16, 17, 12, 11]
  10. 代码块
  11. • 1
  12. • 2
  13. • 3
  14. • 4
  15. • 5
  16. • 6
  17. • 7
  18. • 8
  19. • 9

可以看到，代码确实实现了我们想要的结果，将比 10 小的全部移动到了左边，比 10 大的全部移动到了右边。接下来就是实现快速排序算法。从第一张图中很明显可以看到快排算法是一个递归的过程，因此我们用递归完成快排算法，代码如下：

  1. # 代码位置：sort_algorithms.py
  2. def quick_sort(nums, start, end):
  3.     """
  4.     快速排序算法
  5.     """
  6.     if start >= end:
  7.         return 
  8.     pos = get_num_position(nums, start, end)
  9.     # 左边递归下去，直到排好序
  10.     quick_sort(nums, start, pos - 1)
  11.     # 右边递归下去，直到排好序
  12.     quick_sort(nums, pos + 1, end)
  13. 代码块
  14. • 1
  15. • 2
  16. • 3
  17. • 4
  18. • 5
  19. • 6
  20. • 7
  21. • 8
  22. • 9
  23. • 10
  24. • 11
  25. • 12
  26. • 13

对于递归方法，后面会详细介绍到。这里一定要注意，使用递归过程一定要先写终止条件，不然函数无穷递归下去，就会导致堆栈溢出错误。接下来我们测试这个快排算法：

  1. >>> from sort_algorithms import quick_sort
  2. >>> nums = [8, 7, 9, 6, 11, 3, 12, 20, 9, 5, 1, 10]
  3. >>> quick_sort(nums, 0, len(nums) - 1)
  4. >>> nums
  5. [1, 3, 5, 6, 7, 8, 9, 9, 10, 11, 12, 20] 
  6. 代码块
  7. • 1
  8. • 2
  9. • 3
  10. • 4
  11. • 5

可以看到上面的代码实现了我们想要的排序效果。接下来我们分析下快排算法，它被人们研究的最多，提出了许多改进和优化的方案，我们简单聊一下快排算法的优化方案。

5. 优化快速排序算法

对于优化快速排序，在这里我们只考虑最简单的一种优化思路，就是基准数的选择。前面的快排算法中，我们都是选择列表的第一个元素作为基准数，这在列表随机的情况下是没有什么问题的，但对本身有序的列表进行排序时，时间复杂度就会退化到 O(n^2)O(_n_2)。我们来进行相关测试：

  1. # 冒泡排序算法
  2. import datetime
  3. import random
  4. from sort_algorithms import get_num_position, quick_sort
  5. # python默认递归次数有限制，如果不进行设置，会导致超出递归最大次数
  6. import sys   
  7. sys.setrecursionlimit(1000000)
  8. if __name__ == '__main__':
  9.     # 对于设置10000，本人电脑会出现栈溢出错误
  10.     # nums = [random.randint(10, 10000) for i in range(6000)] 
  11.     nums = [i for i in range(6000)] 
  12.     start = datetime.datetime.now()
  13.     quick_sort(nums, 0, len(nums) - 1)
  14.     end = datetime.datetime.now()
  15.     print('Running time: %s Seconds' % (end-start))
  16. 代码块
  17. • 1
  18. • 2
  19. • 3
  20. • 4
  21. • 5
  22. • 6
  23. • 7
  24. • 8
  25. • 9
  26. • 10
  27. • 11
  28. • 12
  29. • 13
  30. • 14
  31. • 15
  32. • 16
  33. • 17

第一个注释的语言是对 nums 列表随机生成，而第二个直接情况是直接生成有序的列表。我们分别看执行结果：

  1. # 随机列表快排
  2. PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/学习教程/慕课网教程/算法慕课教程/code/test_algorithms.py
  3. Running time: 0:00:00.027907 Seconds
  4. 代码块
  5. • 1
  6. • 2
  7. • 3
  1. # 有序列表快排
  2. PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/学习教程/慕课网教程/算法慕课教程/code/test_algorithms.py
  3. Running time: 0:00:02.159677 Seconds
  4. 代码块
  5. • 1
  6. • 2
  7. • 3

可以看到明显的差别，差不多差了 80 倍，这确实是纯快排算法存在的一个问题。如果我们往这个有序列表中插入少量随机数，打破有序的情况，会看到性能会有较大提升。这个问题的根源在于基准数目的选择，对于有序的列表排序时每次都是选择的最小或者最大的值，这就是最坏的情况。一个显而易见的改进策略就是随机选择列表中的值作为基准数，另一种是从头 (left)、中 ([left + right] // 2) 和尾 (right) 这三个元素中取中间值作为基准数。我们分别进行测试：

  1. import random
  2. def get_base(nums, left, right):
  3.     index = random.randint(left, right)
  4.     if index != left:
  5.         nums[left], nums[index] = nums[index], nums[left]
  6.     return nums[left]
  7. def get_base_middle(nums, left, right):
  8.     if left == right:
  9.         return nums[left]
  10.     mid = (left + right) >> 1
  11.     if nums[mid] > nums[right]:
  12.         nums[mid], nums[right] = nums[right], nums[mid]
  13.     if nums[left] > nums[right]:
  14.         # nums[left]最大，nums[right]中间，所以交换
  15.         nums[left], nums[right] = nums[left], nums[mid]
  16.     if nums[mid] > nums[left]:
  17.         # 说明nums[left]最小, nums[mid]为中间值
  18.         nums[left], nums[mid] = nums[mid], nums[left]
  19.     return nums[left]
  20. def get_num_position(nums, left, right):
  21.     # base = nums[left]
  22.     # 随机基准数
  23.     base = get_base(nums, left, right)
  24.     # base = get_base_middle(nums, left, right)
  25.     while left < right:
  26.         # 和前面相同，以下两个while语句用于将基准数放到对应位置，使得基准数左边的元素都小于它，右边的数都大于它
  27.         while left < right and nums[right] >= base:
  28.             right -= 1
  29.         nums[left] = nums[right]
  30.         while left < right and nums[left] <= base:
  31.             left += 1
  32.         nums[right] = nums[left]
  33.     # 基准数的位置，并返回该位置值
  34.     nums[left] = base
  35.     return left
  36. 代码块
  37. • 1
  38. • 2
  39. • 3
  40. • 4
  41. • 5
  42. • 6
  43. • 7
  44. • 8
  45. • 9
  46. • 10
  47. • 11
  48. • 12
  49. • 13
  50. • 14
  51. • 15
  52. • 16
  53. • 17
  54. • 18
  55. • 19
  56. • 20
  57. • 21
  58. • 22
  59. • 23
  60. • 24
  61. • 25
  62. • 26
  63. • 27
  64. • 28
  65. • 29
  66. • 30
  67. • 31
  68. • 32
  69. • 33
  70. • 34
  71. • 35
  72. • 36
  73. • 37
  74. • 38
  75. • 39
  76. • 40
  77. • 41
  78. • 42
  79. • 43

改进后的测试结果如下：

  1. # 有序列表-随机基准值
  2. PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/学习教程/慕课网教程/算法慕课教程/code/test_algorithms.py
  3. Running time: 0:00:00.021890 Seconds
  4. # 随机列表-随机基准值
  5. PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/学习教程/慕课网教程/算法慕课教程/code/test_algorithms.py
  6. Running time: 0:00:00.026948 Seconds
  7. 代码块
  8. • 1
  9. • 2
  10. • 3
  11. • 4
  12. • 5
  13. • 6
  14. • 7
  1. # 有序列表-中位数基准值
  2. PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/学习教程/慕课网教程/算法慕课教程/code/test_algorithms.py
  3. Running time: 0:00:00.012944 Seconds
  4. # 随机列表-中位数基准值         
  5. PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/学习教程/慕课网教程/算法慕课教程/code/test_algorithms.py
  6. Running time: 0:00:00.020933 Seconds
  7. 代码块
  8. • 1
  9. • 2
  10. • 3
  11. • 4
  12. • 5
  13. • 6
  14. • 7

可以看到使用中位数基准值在有序列表情况下排序速度更快。最后还有一个简单的常用优化方案，就是当序列长度达到一定大小时，使用插入排序。

  1. # 改造前面的插入排序算法
  2. def insert_sort(nums, start, end):
  3.     """
  4.     插入排序
  5.     """
  6.     if not nums:
  7.         return False
  8.     for i in range(start + 1, end + 1):
  9.         t = nums[i]
  10.         for j in range(i - 1, start - 1, -1):
  11.             k = j
  12.             if nums[j] <= t:
  13.                 k = k + 1
  14.                 break
  15.             nums[j + 1] = nums[j]
  16.         nums[k] = t
  17.     return True 
  18. # ...
  19. def quick_sort(nums, start, end):
  20.     """
  21.     快速排序算法
  22.     """
  23.     if (end - start + 1 < 10):
  24.         # 在排序的数组小到一定程度时，使用插入排序
  25.         insert_sort(nums, start, end)
  26.         return
  27.     # 找到基准数位置，同时调整好数组，使得基准数的左边小于它，基准数的右边都是大于它
  28.     pos = get_num_position(nums, start, end)
  29.     # 递归使用快排，对左边使用快排算法
  30.     quick_sort(nums, start, pos - 1)
  31.     # 对右边元素使用快排算法
  32.     quick_sort(nums, pos + 1, end)
  33. 代码块
  34. • 1
  35. • 2
  36. • 3
  37. • 4
  38. • 5
  39. • 6
  40. • 7
  41. • 8
  42. • 9
  43. • 10
  44. • 11
  45. • 12
  46. • 13
  47. • 14
  48. • 15
  49. • 16
  50. • 17
  51. • 18
  52. • 19
  53. • 20
  54. • 21
  55. • 22
  56. • 23
  57. • 24
  58. • 25
  59. • 26
  60. • 27
  61. • 28
  62. • 29
  63. • 30
  64. • 31
  65. • 32
  66. • 33
  67. • 34

下面是使用【随机基准+插入排序优化】的测试结果如下：

  1. # 有序列表-[随机基准+使用插入排序优化]
  2. PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/学习教程/慕课网教程/算法慕课教程/code/test_algorithms.py
  3. Running time: 0:00:00.010962 Seconds
  4. # 无序列表-[随机基准+使用插入排序优化]
  5. PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> & "D:/Program Files (x86)/python3/python.exe" c:/Users/spyinx/Desktop/学习教程/慕课网教程/算法慕课教程/code/test_algorithms.py
  6. Running time: 0:00:00.018935 Seconds
  7. 代码块
  8. • 1
  9. • 2
  10. • 3
  11. • 4
  12. • 5
  13. • 6
  14. • 7

可以看到这些小技巧在真正大规模数据排序时会有非常明显的效果。更多的优化方法以及测试，读者可以自行去实验和测试，这里就不再继续讲解了。

6. 小结

本小节我们介绍了快速排序算法以及相关的优化策略，并完成了简单的实验测试，方便大家理解改进的效果。至此，排序算法介绍到此就要结束了。当然高效的排序算法并不止快排算法，海域堆排序、归并排序、桶排序以及基数排序等等，这些读者可以自行学习并实现相关代码，打好算法基础。

Tips：文中动图制作参考：https://visualgo.net/zh/sorting。