面向研究生入学考试编程:排序算法 04 快速排序 木灵的炼金工作室

快速排序

归并排序是按照数组下标将数组分为两部分,那么我们换一个角度,我们以数组元素的大小将数组分为两组,再分别对这两组进行排序,这样的算法叫快速排序。如它的名称,这个是我们目前能够想到的对于大量随机输入的最高效的排序算法。

一种直观的快速排序算法是随机抽取一个数组元素作为枢纽,将其余元素根据是否大于这一元素将原数组分为两个数组,然后递归地运行。我们不需要任何的后处理过程,因为这样分好的数组在按顺序合并之后自然就是从小到大的。

一般来讲,我们取的这个用作基准的数应尽量将原数组分为相等的两部分,否则算法的效率就会下降。考虑一种极端情况,如果每一次选择的数都刚好是这个数组的最小者,那么算法退化为$O(n^2)$。

那么如何取这个数呢?一般的做法是:对于长度为n的数组A,取A[0], A[n // 2], A[n - 1]三个元素中的中值作为枢纽,分组。

分组也有技巧。我们维护两个数组下标变量,L初始为0,R初始为n - 1,L向右,R向左。当L遇到比枢纽大的元素时停下来,当R遇到比枢纽元小的元素时停下来,然后若L小于R,交换二者对应的数组值;当L不小于R时,分组结束。

那么我们来写一下代码:

def _quickSort(arr, left, right):
    if left >= right:
        return
    arr[(left + right) // 2], arr[left] = arr[left], arr[(left + right) // 2]
    pivot = arr[left]
    Lpoint, Rpoint = left + 1, right
    while True:
        while Lpoint < right and arr[Lpoint] <= pivot:
            Lpoint += 1
        while Rpoint > left and arr[Rpoint] > pivot:
            Rpoint -= 1
        if Lpoint < Rpoint:
            arr[Lpoint], arr[Rpoint] = arr[Rpoint], arr[Lpoint]
        else:
            break
    arr[left], arr[Rpoint] = arr[Rpoint], arr[left]
    _quickSort(arr, left, Lpoint - 1)
    _quickSort(arr, Rpoint + 1, right)

def quickSort(arr):
    _quickSort(arr, 0, len(arr) - 1)
    return arr

在上述实现中我们使用中间位置的元素作为枢纽元素,是一种简化的写法。
接下来我们来分析一下这个算法的开销:为了分析的便利,我们假设每次枢纽元都将数组分为了两个长度相等的组(当然这是极其特殊的情况)。
我们在每一个迭代中进行了这样的工作:将原规模为$n$的问题化为两个规模为$n/2$的问题,同时引入一个时间开销为$n$的额外过程。与归并排序一模一样,渐近时间复杂度为$O(n\log n)$,我们在递归中引入了$O(\log n)$的栈空间。
很明显,如果两个元素有相同的主键,在后的元素完全有可能被提前换至前方,因此在算法层面的根源上排序是不稳定的。


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn