使用 Hoare 分区的快速排序，我如何选择主元会影响我的 python 实现

Question

我正在尝试在 python 中使用 Hoare 分区实现快速排序，使用

中的代码

但是当我将 pivot = a_list[low] 更改为 pivot = a_list[high] 时，我就是无法正常工作！

有人可以帮忙吗？

def quicksort(a_list):
    """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
    def _quicksort(a_list, low, high):
        # must run partition on sections with 2 elements or more
        if low < high: 
            p = partition(a_list, low, high)
            _quicksort(a_list, low, p)
            _quicksort(a_list, p+1, high)
    def partition(a_list, low, high):
        pivot = a_list[low] # changing to pivot = a_list[high] breaks the program
        while True:
            while a_list[low] < pivot:
                low += 1
            while a_list[high] > pivot:
                high -= 1
            if low >= high:
                return high
            a_list[low], a_list[high] = a_list[high], a_list[low]
            low += 1
            high -= 1
    _quicksort(a_list, 0, len(a_list)-1)
    return a_list

----更新----

为了确保我真正理解快速排序，我还尝试了 pivot = array[low] 的 lomuto 分区。结果是另一个挑战，所以也请检查@rcgldr 更新的答案。

Answer 1

看来还可以补一下：

    _quicksort(a_list, low, p-1)
    _quicksort(a_list, p+1, high)

Answer 2

正在将名称更改为 a[]、lo、hi、p（枢轴）

对于题中的代码，pivot可以是除a[hi]以外的任意元素。对于 pivot = a[hi] 的问题示例，请考虑 lo = 0、hi = 1 且 a[0] < a[1].

的情况

a[] = {2,3}
partition:
    p = a[1] = 3
    since a[lo]  < p, lo += 1 = 1
    since a[hi] == p, hi      = 1
    return hi = 1
_quicksort(a, lo, p) == _quicksort(a, 0, 1) (infinite recursion)

切换到返回 lo、p-1、p，允许主元是除 a[lo] 之外的任何元素：

a[] = {2,3}
partition:
    p = a[1] = 3
    since a[lo]  < p, lo += 1 = 1
    since a[hi] == p, hi      = 1
    return lo = 1
_quicksort(a, lo, p-1) == _quicksort(a, 0, 0) (ok)
_quicksort(a,  p,  hi) == _quicksort(a, 1, 1) (ok)

a[] = {3,3}
partition:
    p = a[1] = 3
    since a[lo] == p, lo      = 0
    since a[hi] == p, hi      = 1
    swap(a[lo], a[hi]) a = {3,3}
    lo += 1 = 1
    hi -= 1 = 0
    since a[lo] == p, lo      = 1
    since a[hi] == p, hi      = 0
    return lo = 1
_quicksort(a, lo, p-1) == _quicksort(a, 0, 0) (ok)
_quicksort(a,  p,  hi) == _quicksort(a, 1, 1) (ok)

a[] = {4,3}
partition:
    p = a[1] = 3
    since a[lo]  > p, lo      = 0
    since a[hi] == p, hi      = 1
    swap(a[lo], a[hi]) a = {3,4}
    lo += 1 = 1
    hi -= 1 = 0
    since a[lo]  > p, lo      = 1
    since a[hi] == p, hi      = 0
    return lo = 1
_quicksort(a, lo, p-1) == _quicksort(a, 0, 0) (ok)
_quicksort(a,  p,  hi) == _quicksort(a, 1, 1) (ok)

Lomuto with pivot = a[lo]，在单个函数中。在一个分区步骤之后，它仅在较小的分区上进行 recuse，然后更新 lo 或 hi 并循环返回以处理较大的分区。这将堆栈 space 的复杂度限制为 O(log(n))，但最坏情况下的时间复杂度仍然是 O(n^2)。

def quicksort(a, lo, hi):
    while(lo < hi):
        pivot = a[lo]
        i = lo+1
        for j in range(lo+1, hi+1):
            if a[j] < pivot:
                a[i],a[j] = a[j],a[i]
                i += 1
        i -= 1
        a[i],a[lo] = a[lo],a[i]
        if(i - lo <= hi - i):
            quicksort(a, lo, i-1)
            lo = i+1
        else:
            quicksort(a, i+1, hi)
            hi = i-1

使用 Hoare 分区的快速排序，我如何选择主元会影响我的 python 实现

Quicksort using Hoare Partitioning, how I chose pivot affects my python implement

python

algorithm

quicksort