快速排序

在理解了归并排序之后， 有一种更优秀的排序算法, 看看快速排序吧

前言

在理解了归并排序之后， 有一种更优秀的排序算法。上一次的简书中已经介绍了归并排序， 我们已经有了分治思想。快速排序在切分的时候不是采用对半分， 而是根据内容划分。思想是如果每一个元素在序列中， 左边序列元素 < 该元素 < 右边序列元素。 那么这个序列就是有序的序列。这就是基本思想。

主要解决的问题有两个

• 把一个序列按照一个算法， 使 左边序列元素 < 该元素 < 右边序列元素。
• 如何继续划分下去。

给个例子说明一下吧

一、快速排序的切分(partition)

如何让一个元素找到合适的位置呢？

code

def partion(alist, left, right):
    temp = alist[left]
    while left < right:
        while left < right and alist[right] >= temp:
            right -= 1

        alist[left] = alist[right]

        while left < right and alist[left] <= temp:
            left += 1
        alist[right] = alist[left]
    alist[left] = temp
    return left

二、快速排序分治

上面已经有了单次的切分， 只要按照这样， 把序列分割切分部分有序下去， 就会有序了。当然递归方式很简单。

code

def quickSort(alist, low, high):

    if low < high:
        pos = partion(alist, low, high)
        quickSort(alist, low, pos - 1)
        quickSort(alist, pos + 1, high)

三、关于优化

小的范围插入排序表现更加优秀， 所以代码可以适当调节。
在重复元素较多的情况下， 切分任然过于繁琐， 可以采用三向切分的快速排序。