(python) 快速排序适用于有序数据，但不适用于无序数据

Question

我正在 python 中实现递归快速排序。我正在处理非常大的数据集（10,000 - 1,000,000 个元素）。当向它提供有序数据时（即更改从最大 -> 最小到最小 -> 最大排序的数组），它工作正常。但是当给它无序数据时，它似乎根本不起作用。

我正在使用 3-way pivot 计算等于 pivot 的元素（荷兰国旗问题），如果数据大于 101（记住它是递归的），它使用 first 的中位数选择枢轴时数组分区中的、中间和最后一个元素。

10,000 个元素的随机集合的输出片段：

如您所见，它似乎具有特定的模式。我增加了递归限制，所以我知道这不是问题所在，但它似乎只是对输入进行了部分排序。就像我提到的，它适用于已经按相反顺序排序的数组，这让我很困惑。

我的代码：

def array_swap(A, i, j):
    temp = A[i]
    A[i] = A[j]
    A[j] = temp


# take median of three elements
def median_three(a, b, c):
    return sorted([a, b, c])[1] 
    


def qs_part(A, lo, hi):
    mid = lo
    p = median_three(A[lo], A[(lo + hi) // 2], A[hi]) # pivot set to median of 3, as described in handout 
    # ('//' must be used for floor division in Python 3 -- it took me longer than I'm willing to admit to figure that out.)
    
    while mid <= lo:
        if A[mid] < p:
            array_swap(A, mid, lo)
            mid += 1
            lo  += 1
        elif A[mid] > p:
            array_swap(A, mid, hi)
            hi  -= 1
        else:
            mid += 1
    return (lo - 1), mid
    

# Quicksort implementation as described in handout.
# A: Array to sort
# write:    name of file to write sorted results to
# out:      name of file to write runtime to
# lo:       start index (1 after pivot in first case)
# hi:       end index
def quick_sort(A,lo, hi):
    if lo >= hi:
        return # if there are 0 or 1 elements in A
    
    if lo - hi == 1:
        if A[lo] < A[hi]: # if 2 elements, sort them
            array_swap(A, lo, hi)
        return
    
    i, j = qs_part(A, lo, hi)
    quick_sort(A, lo, i) # recursively sort partition 1 (elements < pivot)
    quick_sort(A, j, hi) # recursively sort partition 2 (elements > pivot)
    # no need to sort between 'i' and 'j' because those items == pivot

Answer 1

我明白了。这只是 qs_part() 中的一个小错字。 while mid <= lo 应该是 while mid <= hi

(python) 快速排序适用于有序数据，但不适用于无序数据

(python) quicksort working for ordered data, but not for unordered data

python

sorting

recursion

quicksort

bigdata