了解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

快速排序

在快速排序的步骤是:

• 从列表中选择一个名为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分区方案与Lomuto分区方案

枢轴选择

• 算法的执行速度在很大程度上取决于如何实现这种机制,不良的实现可以假设算法以低速运行.

• pivot的选择决定了数据列表的分区,因此,这是Quicksort算法实现中最关键的部分.重要的是尝试选择枢轴左和右分区尽可能相同的大小.

最好和最坏的情况

最糟糕的情况

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

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

正式分析

• 最坏情况分析= 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])

在你的例子中

调试Lomuto分区

参考文献:

• http://www.cs.bilkent.edu.tr/~atat/473/lecture05.pdf
• http://codefap.com/2012/08/the-quick-sort-algorithm/
• http://visualgo.net/sorting
• https://en.wikipedia.org/wiki/Quicksort