Python 中的 3 种快速排序

Question

我正在尝试在 Python 中实现 3 路分区快速排序代码。

我的代码包含两行：

第一个是要排序的整数个数
第二个是要排序的整数数组

我的代码适用于以下输入：

8, 1 3 5 4 2 6 4 4
5, 2 3 9 2 2

但是，当使用以下输入进行测试时： 10, 10 9 8 7 6 5 4 3 2 1

我的代码没有正确排序整数数组？

我可以知道为什么我的代码不适用于最后一种情况吗？

这是我的代码：

def partition3(a, l, r):
    #write your code here
    pivot = a[r]
    i = l
    j = l - 1
    iterable_length = r 
        
    while i <= iterable_length:
        if a[i] < pivot:
            j += 1
            a[i], a[j] = a[j], a[i]
        
        elif a[i] > pivot:
            a[i], a[iterable_length] = a[iterable_length], a[i]
            iterable_length -= 1
            
        i += 1
        
    return j, iterable_length+1

def randomized_quick_sort(a, l, r):
    if l >= r:
        return
    k = random.randint(l, r)
    a[l], a[k] = a[k], a[l]
    #use partition3
    # m = partition2(a, l, r)
    m1, m2 = partition3(a, l, r)
    randomized_quick_sort(a, l, m1);
    randomized_quick_sort(a, m2, r);


if __name__ == '__main__':
    input = sys.stdin.read()
    n, *a = list(map(int, input.split()))
    randomized_quick_sort(a, 0, n - 1)
    for x in a:
        print(x, end=' ')

Answer 1

欢迎来到 Whosebug。问题似乎出在这里：

k = random.randint(l, r)
a[l], a[k] = a[k], a[l]

您正在获取一个随机索引 k 并使用它随机交换两个元素 a[l] 和 a[k]。 删除这两行 ~~应该给出正确的输出~~只在某些情况下看起来正确。

我假设您要创建一个 随机枢轴点 ，在这种情况下，您应该使用随机索引作为 partition3 函数内的枢轴.

编辑： 问题不在于 processing/skipping 在 a[i] 处交换 a[i] > pivot: 后的新元素。应该是：

elif a[i] > pivot:
  a[i], a[iterable_length] = a[iterable_length], a[i]
  iterable_length -= 1
  # don't forget to process new element at a[i]
  i -= 1

Python 中的 3 种快速排序

3 way Quick Sort in Python

python

sorting

algorithm

quicksort