Python快速排序与自定义停止条件

Question

基于这个答案，我想使用带有自定义停止条件的快速排序，以便在Python中从未排序的数组生成k排序的数组。我假设len(array) = m*k，因此将有m子数组(不一定排序)，并且子数组i的元素低于或等于子数组j的元素与i<j。

def partition(array, left, right):
    pivot = array[right]
    i = left - 1
    for j in range(left, right):
        if array[j] <= pivot:
            i += 1
            temp = array[i]
            array[i] = array[j]
            array[j] = temp
    temp = array[right]
    array[right] = array[i + 1]
    array[i + 1] = temp
    return i + 1
def k_quicksort(array, left, right, k):
    if right - left > k:
        p = partition(array, left, right)
        k_quicksort(array, p + 1, right, k)
        k_quicksort(array, left, p - 1, k)

我在链接中引用的答案建议我应该改变停止条件，检查开始(left)和结束(right)索引是否大于k，如果不是，则不要再出现。我用

测试这个算法

x = [scipy.random.randint(1,100) for i in range(16)]
k_quicksort(x,0,len(x)-1,4)

And i get

x = [19, 13, 1, 28, 42, 49, 73, 59, 62, 56, 74, 89, 78, 90, 91, 98]

这是非常错误的。是我没有理解好习惯的停止条件，还是其他的bug??如有任何帮助，不胜感激

Answer 1

要限制为k-sorted数组，您需要跳过数组末尾的递归:

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
def partition(array, left, right):
    pivot = array[right - 1]
    i = left
    for j in range(left, right - 1):
        if array[j] <= pivot:
            swap(array, i, j)
            i += 1
    swap(array, right - 1, i)
    return i
def k_quicksort(array, left, right, k):
    if left == right:
        return
    p = partition(array, left, right)
    k_quicksort(array, left, p, k)
    if k > p + 1:
        k_quicksort(array, p + 1, right, k)

您需要分区来确保您排序的是正确的值。但是您可以跳过对k右边的所有值的递归(因此也可以跳过排序)。

编辑:修复你的快速排序