双路快速排序学习笔记
原理简介
双路快速排序是一种常见的排序算法，其基本思想是通过分治法将待排序的序列分成两部分，然后对这两部分再分别进行排序，最终将整个序列排序。
具体而言，快速排序先选定一个枢轴值，然后将序列中小于枢轴值的元素放在枢轴值的左侧，大于枢轴值的元素放在右侧。接着对左右两侧的子序列分别进行递归排序，直到整个序列都有序。
与传统的快速排序不同的是，在双路快速排序中，我们选取了两个指针i和j分别从序列的左右两端开始扫描，并且保证左边的指针i所指向的元素小于等于枢轴值，右边的指针j所指向的元素大于等于枢轴值，然后交换i和j指向的元素。当i和j相遇时，遍历完成，此时i左侧的元素均小于等于枢轴值，右侧的元素均大于等于枢轴值。然后将枢轴值与i指向的元素交换，此时枢轴值就位于数组的中间位置，左侧的元素均小于等于枢轴值，右侧的元素均大于等于枢轴值。接下来递归处理左半部分和右半部分即可。
算法流程
- 选定枢轴值pivot，从左端l开始和右端r开始各设置一个指针i和j。
- 一直移动i，直到找到一个元素大于等于枢轴值pivot为止。
- 一直移动j，直到找到一个元素小于等于枢轴值pivot为止。
- 如果此时i<=j，则交换a[i]和a[j]的值，然后i向右移动一位，j向左移动一位。
- 重复步骤2~4，直到i>j。最后再将pivot与a[j]交换，完成一次排序。
- 对左右两个子序列分别重复步骤1~5，直到所有子序列都有序。
Python 代码实现
pythonCopy Codedef quick_sort(nums, left, right):
if left >= right:
return
pivot = nums[left]
i = left + 1
j = right
while True:
while i <= j and nums[i] < pivot:
i += 1
while i <= j and nums[j] > pivot:
j -= 1
if i > j:
break
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
nums[left], nums[j] = nums[j], nums[left]
quick_sort(nums, left, j-1)
quick_sort(nums, j+1, right)
nums = [3, 6, 2, 8, 4, 1, 5, 7]
quick_sort(nums, 0, len(nums)-1)
print(nums)
实例演示
我们用下面的例子来演示双路快速排序的过程：
Copy Code[3, 6, 2, 8, 4, 1, 5, 7]
首先以3为枢轴值，左指针i从索引1开始扫描，右指针j从索引6倒着扫描：
Copy Codei pivot j
↓ ↓ ↓
[3, 6, 2, 8, 4, 1, 5, 7]
移动i，找到第一个大于等于3的元素6，移动j，找到第一个小于等于3的元素1，然后交换i和j指向的元素：
Copy Code i pivot j
↓ ↓ ↓
[1, 6, 2, 8, 4, 3, 5, 7]
接着继续移动i和j，直到i>j，此时交换pivot和aj：
Copy Code pivot
↓
[1, 2, 3, 8, 4, 6, 5, 7]
现在我们已经完成了第一次排序，接下来对左右两边的子序列分别进行排序。左半部分是[1,2]和右半部分是[8,4,6,5,7]。以左半部分为例，以2为枢轴值，继续进行双路快速排序：
Copy Code pivot
↓
[1, 2, 3, 8, 4, 6, 5, 7]
移动i和j，交换i和j指向的元素：
Copy Code pivot
↓
[1, 2, 3, 8, 4, 6, 5, 7]
i j
↓ ↓
再移动i和j，直到i>j，最终交换pivot和a[j]：
Copy Code pivot
↓
[1, 2, 3, 8, 4, 6, 5, 7]
i/j
↓
[1, 2, 3, 5, 4, 6, 8, 7]
左半部分已经排好序了，右半部分依次执行相同的操作即可。最终得到有序序列：
Copy Code[1, 2, 3, 4, 5, 6, 7, 8]