经典算法之快速排序详解（图文）

前言

日常开发中用到的排序其实很少，不过不代表我们不需要了解。今天就来分享一个非常经典的排序算法-快速排序。

快速排序

样例：对数据 arr=[3，2，1，5，0，4]使用快排进行排序

排序逻辑：

• 从 arr 中随机选取一个数定义为 pvoite(假定选择左端点得值 arr[0])

第一种方法小放左 大放右：

• 将 arr 中小于 pivote 的数放在 pivote 的左边，大于 pivote 的数放在 pivote 的右边
• 对于左边的数组重新选取 pivote 并小放左、大放右(递归)
• 对于右边的数组重新选取 pivote 并小放左、大放右(递归)

第二种方法：排序样例-双指针法

指针初始化：left 指针为当前 arr 开始位置，right 指针为当前 arr 的末尾位置；

• 从 right 指针位置开始判断：
  如果 arr[right] >= pivote && left < right, 则 right-- 如果 arr[right] < pivote && left < right, 则 arr[left] = arr[right], left++
• 然后从 left 指针处开始判断：
  如果 arr[left] <= pivote && left < right, 则 left++；如果 arr[left] > pivote && left < right, 则 arr[right] = arr[left], right++
• 然后再从 right 指针处开始判断，左右指针交替进行；
• 终止条件：不满足 left < right 时 结束，arr[left] = pivote, （此时：pivote 左边都是小于 pivote
  的数，右边都是大于 pivote 的
• 第一次快排结束，然后对左右两边递归进行上述过程完成整体排序。

上述过程图示如下：

整体排序过程如下：

代码样例：

1. # 指针 left：左=>右找大于 pivote 的值
2. # 指针 right：右=>左找小于 pivote 的值
3. def getPartitionIndex(arr, left, right)：
4. pivote = arr[left]
5. while left < right：
6. while arr[right] >= pivote and right > left：
7. right -= 1
8. arr[left] = arr[right]
9. while arr[left] <= pivote and right > left：
10. left += 1
11. arr[right] = arr[left]
12. arr[left] = pivote
13. return left
14. def quickSort(arr, left=None, right=None)：
15. # print(arr)
16. left = 0 if not isinstance(left, (int, float)) else left
17. right = len(arr)-1 if not isinstance(right, (int, float)) else right
18.
19. if left < right：
20. partitionIndex = getPartitionIndex(arr, left, right)
21. quickSort(arr, left, partitionIndex)
22. quickSort(arr, partitionIndex+1, right)
23. return arr
24.
25. if __name__ == '__main__'：
26. arr = [3, 2, 1, 5, 0, 4]
27. print(quickSort(arr))

算法讲解结束。