Python 排序方法5: 快速排序(1)

qiuyouzhi

Python 排序方法5: 快速排序(1)

初识快速排序


快速排序为什么快？

因为快排用了分治法，在每一轮挑选一个基准元素，
并让比基准点大的元素移动到数列一边，比基准点小
的元素就移动到基准点的另一边。

基准元素的选择
如何选择基准元素呢？
1，第一个
2，随机一个
如果是方法一的话，那么每次选出来的要么是最小值，要么是最大值，
根本无法发挥分治法的优势。
如果选择第二个的话，我们只需要随机选一个元素作为基准元素，
并且让基准元素和第一个元素交换位置就好了。
按照这个思路，我们可以写出代码：

def test(list1):
    pivot = (len(list1)-1) // 2
    list1[0], list1[pivot] = list1[pivot], list1[0]
    return list1


print(test([8, 7, 6, 5, 4, 3, 2, 1]))

[8, 7, 6, 5, 4(pivot), 3, 2, 1]
[4(pivot), 7, 6, 5, 8, 3, 2, 1]

这样的话，即使是在数列完全逆序的情况下，也可以有效的将数列分成两部分。
当然，随机选也有可能会选到最小值或者最大值，同样会影响分治的效果。

在下一节，我们会把快排的思路和代码写出来！