了解快速排序

Question

我很难理解quicksort，大多数演示和解释都忽略了实际发生的事情（例如http://me.dt.in.th/page/quicksort/）。

维基百科说：

从数组中选择一个称为透视的元素。分区：对数组重新排序，使所有值小于pivot的元素都在pivot之前，而所有值大于pivot的元素都在pivot之后（相等的值可以从任何一个方向走）。分区后，枢轴处于其最终位置。这称为分区操作。将上述步骤递归应用于具有较小值的元素的子数组，并单独应用于具有较大值的元素的子数组。

Answer 1

快速排序步骤如下：

• 从列表中选择一个称为透视的元素。
• 对列表重新排序，使所有值小于透视的元素都在透视之前，而所有值大于透视的元素都在透视之后（相等的值可以从任何一个方向移动）。分区后，枢轴处于其最终位置。这称为分区操作。
• 递归排序较小元素的子列表和较大元素的子列表。递归的基本情况是大小为0或1的列表，它们从不需要排序。

Lomuto分区方案

null

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo        // place for swapping
    for j := lo to hi – 1 do
        if A[j] ≤ pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p – 1)
        quicksort(A, p + 1, hi)

>

使用两个索引，它们从被分区html" target="_blank">数组的末尾开始，然后相互移动，直到它们检测到倒置：一对元素，一个比枢轴大，一个比枢轴小，它们之间的顺序不对。然后交换反转的元素。

该算法有许多变体，例如，从[hi]而不是[lo]中选择pivot

分区算法（使用Hoare分区方案）

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo – 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j – 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

>

算法的执行速度很大程度上取决于这种机制是如何实现的，差的实现可以假设算法以慢的速度运行。

pivot的选择决定了数据列表的分区，因此，这是Quicksort算法实现中最关键的部分。重要的是要尽量使选择的透视左分区和右分区的大小相同。

最佳和最坏情况

形式分析

• 最差情况分析=O(N²)
• 最佳情况分析=O(n)因子
• 平均情况分析=O(n log n)

示例来源

def quicksort(array):
    less = []
    equal = []
    greater = []
    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
        return sort(less)+equal+sort(greater)  
    else: 
        return array

quicksort([12,4,5,6,7,3,1,15])

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot

def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    if begin >= end:
        return
    pivot = partition(array, begin, end)
    quicksort(array, begin, pivot-1)
    quicksort(array, pivot+1, end)

quicksort([97, 200, 100, 101, 211, 107])

null