了解quicksort

Question

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

维基百科说：

从数组中选择一个称为pivot的元素。分区：对数组进行重新排序，使得值小于枢轴的所有元素都在枢轴之前，而所有值大于枢轴的元素都在它之后（相等的值可以是任意一种）。在此分区之后，枢轴处于其最终位置。这称为分区操作。递归地将上述步骤应用于具有较小值的元素的子数组，并分别应用于具有较大值的元素的子数组。

如何使用9,1,7,8,8的数组，例如以7为枢轴？ 9需要移动到枢轴的右侧，所有快速排序实现都是现场操作，所以我们不能在8,8之后添加它，所以唯一的选择是将9与7交换。

现在阵列是7,1,9,8,8。 quicksort背后的想法是，现在我们必须递归地将部件分类到枢轴的左侧和右侧。枢轴现在位于数组的位置0，这意味着没有左侧部分，因此我们只能对正确的部分进行排序。这是没有用的7> 1所以枢轴最终在错误的地方。

在这个图像4是枢轴，那么为什么5几乎一直向左？它大于4！经过大量的交换后，它最终被排序，但我不明白这是怎么回事。

Answer 1

快速排序

Quicksort步骤是：

从列表中选择一个名为pivot的元素。
对列表重新排序，使得值小于枢轴的所有元素都在枢轴之前，而值大于枢轴的所有元素都在它之后（相同的值可以是任意一种）。在此分区之后，枢轴处于其最终位置。这称为分区操作。
递归地排序较小元素的子列表和较大元素的子列表。递归的基本情况是大小为零或一的列表，从不需要对其进行排序。

Lomuto分区方案

此方案选择一个pivot，它通常是数组中的最后一个元素。
该算法维护索引以将枢轴放在变量i中，并且每次找到小于或等于pivot的元素时，此索引都会递增，并且该元素将放置在pivot之前。
由于该方案更紧凑且易于理解，因此常用于介绍材料。
效率低于Hoare的原始方案。

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

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

Quicksort算法（使用Lomuto分区方案）

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)

Hoare分区方案

使用从被分区的数组末端开始的两个索引，然后相互移动，直到它们检测到反转：一对元素，一个大于枢轴，一个小，相对于彼此的顺序错误。然后交换倒置的元素。
该算法有许多变体，例如，从A [hi]而不是A [lo]中选择枢轴

分区算法（使用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]

快速排序算法（使用Hoare分区方案）

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

Hoare partition scheme vs Lomuto partition scheme

枢轴选择

算法的执行速度在很大程度上取决于如何实现这种机制，不良的实现可以假设算法以低速运行。
pivot的选择决定了数据列表的分区，因此，这是Quicksort算法实现中最关键的部分。重要的是尝试选择枢轴左和右分区尽可能相同的大小。

最好和最坏的情况

最糟糕的情况

最不平衡的分区发生在数据透视表将列表分成两个大小为_0和n-1的子列表时。如果数组恰好是列表中的最小或最大元素，或者在某些实现中所有元素相等时，可能会发生这种情况。。

最佳案例在最平衡的情况下，每次执行分区时，我们将列表分成两个几乎相等的部分。这意味着每个递归调用都会处理一半大小的列表。

正式分析

最坏情况分析= O（n²）
最佳案例分析= O（n）因子
平均案例分析= O（n log n）

例子source

使用额外的内存

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])

在你的例子中

调试Lomuto分区

References:

Answer 2

有一天，我发现了这个宝石，它激发了不同的Sorting Algorhitms，帮助我理解它们！但这只是一个图解说明，我之前的海报（@Hydex），已经以学术方式回答;-)

了解quicksort

问题描述投票：7回答：2

2个回答

快速排序

最新问题

了解quicksort

问题描述 投票：7回答：2

2个回答

快速排序

最新问题

问题描述投票：7回答：2