使用霍尔分区进行快速排序，我选择pivot的方式会影响我的python实现

Question

我试图在python中使用Hoare分区实现快速排序，代码来自https://stackoverflow.com/a/41211360/301513

但是当我把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可以是除[hi]之外的任何元素。对于具有PIVOT＝A[H]的问题的一个例子，考虑LO＝0，HI＝1，和A〔0〕& lt的情况；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，允许枢轴为除[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)

---

在单个功能中，旋转轴=a[lo]的Lomuto。在分区步骤之后，它只在较小的分区上重复，然后更新lo或hi并循环回处理较大的分区。这将堆栈空间复杂度限制为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