本文用 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----