本文用 python 实现快速排序。
思路
- 假如有一个序列 [4, 6, 1, 14, 8]，首先要把第一个数找到它正确的位置，即它左边都小于它，右边均大于它。
1、取出第一个值 赋值给临时变量 target，target = 4 ，取出变量left 记录左边下标，变量 right 记录右边下标。
1
2、把 target 与 right 下标的值进行比较，如果 target 小， 则 right += 1，再重复 2 的操作。反之将 right 下标的值赋值给 left 的值，sort_list[left] = sort_list[right]，然后left += 1 ，执行3。
2
3、把 target 与 right 下标的值进行比较，如果 target 小， 则 right += 1，再重复 3 的操作。反之将 right 下标的值赋值给 left 的值，sort_list[left] = sort_list[right]
3
4、直到 left == right，把 target 赋值给 sort_list[left] ，这时左边的数小于 target ，右边的数大于 target。
4
- 然后把 target 左边的序列和右边的序列递归执行上述操作，直到最后，排序完成
代码
如下：
def quick_sort(sort_list, start, end):
if start >= end:
return
# 记录两端下标
left = start
right = end
# 取第一个作为目标
target = sort_list[left]
while left < right:
while left < right and target <= sort_list[right]:
right -= 1
sort_list[left] = sort_list[right]
while left < right and sort_list[left] < target:
left += 1
sort_list[right] = sort_list[left]
sort_list[left] = target
# 把target两边的序列递归执行
quick_sort(sort_list, start, left-1)
quick_sort(sort_list, left+1, end)
if __name__ == '__main__':
sort_list = [4, 6, 1, 14, 8]
quick_sort(sort_list, 0, len(sort_list) - 1)
print(sort_list)
快速排序是不稳定的，平均时间复杂度是 O(nlog2n)，最差时间复杂度 O(n2)。
----END----
