在 Python 中实现快速排序 - 列出 index/infinite 循环错误

Question

我正在尝试在 Python 中实现快速排序。我使用在维基百科 here 上找到的伪代码作为基础。里面有 do...while 循环，所以我使用了

while True:
    # code
    if condition:
        break

构建模拟它。

我已经尝试了很多不同的方法，例如 incrementing/decrementing 或添加索引越界检查（伪代码没有，因为使用 Hoare 算法应该没有必要，至少我也这样觉得...）。我总是遇到 IndexError 或无限循环。

有人可以告诉我我在实施算法时哪里出错了吗？

class QuickSort:

    def sort(self, data):
        if data is None:
            raise TypeError()
        n = len(data)
        if n < 2:
            return data
        self._sort(data, 0, len(data) - 1)
    
    def _sort(self, A, lo, hi):
        if lo >= 0 and hi >= 0:
            if lo < hi:
                p = self._partition(A, lo, hi)
                self._sort(A, lo, p)
                self._sort(A, p + 1, hi)

    def _partition(self, A, lo, hi):
        pivot = A[(hi + lo) // 2]
        i = lo - 1
        j = hi + 1
        while True:
            while True:
                i += 1
                if A[i] < pivot:
                    break
            while True:
                j -= 1
                if A[j] > pivot:
                    break
            if i >= j:
                return j
            A[i], A[j] = A[j], A[i]

编辑：原因很简单，当使用 do...while 的 python 版本时，您必须反转条件！

Answer 1

需要将循环中的<和>改为>=和<=:

class QuickSort:
    def sort(self, data):
        if data is None:
            raise TypeError()
        n = len(data)
        if n < 2:
            return data
        self._sort(data, 0, len(data) - 1)

    def _sort(self, A, lo, hi):
        if lo >= 0 and hi >= 0:
            if lo < hi:
                p = self._partition(A, lo, hi)
                self._sort(A, lo, p)
                self._sort(A, p + 1, hi)

    def _partition(self, A, lo, hi):
        pivot = A[(hi + lo) // 2]
        i = lo - 1
        j = hi + 1
        while True:
            while True:
                i += 1
                if A[i] >= pivot:  # >= instead of <
                    break
            while True:
                j -= 1
                if A[j] <= pivot:  # <= instead of >
                    break
            if i >= j:
                return j
            A[i], A[j] = A[j], A[i]


lst = [9, 8, 7, 6, 5, 4, 1, 2]
QuickSort().sort(lst)
print(lst) # [1, 2, 4, 5, 6, 7, 8, 9]

在 Python 中实现快速排序 - 列出 index/infinite 循环错误

Implementing quick sort in Python - list index/infinite loop bugs

python

quicksort

infinite-loop

index-error