快速排序中间列表打印 Python

Question

this HackerRank 问题的提示让我很困惑。它本质上是一个快速排序实现，但作为例外，您需要在每次迭代时完整打印中间（或半排序）"original" 数组。

我的工作代码没有打印中间体。它按预期工作。

def quicksort(array):

    if len(array) > 1:
        left = 0
        right = len(array)-2
        pivot = len(array)-1
        while left <= right:
            while array[left] < array[pivot]:
                left +=1
            while array[right] > array[pivot]:
                right -= 1
            if left <= right:
                array[left], array[right] = array[right], array[left]
                left += 1
                right -=1
        array[left], array[pivot] = array[pivot], array[left]

        return quicksort(array[0:left]) + quicksort(array[left::])
    else:
        # return single element arrays
        return array

下面是我尝试实现一种打印中间体的方法。 IE。我试图将索引分开，而不是像上面的例子那样只传递拼接列表，这样我将始终可以访问第一个函数参数中的完整数组。

def quicksort2(array, start=0, end=None):
    size = len(array[start:end])


    if size > 1:
        left = start
        right = len(array[start:end])-2
        pivot = len(array[start:end])-1
        print("Print")
        print("left: {}\nright: {}\npivot: {}".format(left, right, pivot))
        while left <= right:
            while array[left] < array[pivot]:
                left +=1
            while array[right] > array[pivot]:
                right -= 1
            if left <= right:
                array[left], array[right] = array[right], array[left]
                left += 1
                right -=1
        array[left], array[pivot] = array[pivot], array[left]
        print(array)
        print("the end is {}".format(end))

        size = len(array[0:left]) # 3

        return quicksort2(array, start=0, end=left) + quicksort2(array, start=left, end=left+(size-len(array)))
    else:
        # return single element arrays
        return array



if __name__ == '__main__':
    size = int(input()) # size is 7
    arr = [int(i) for i in input().split()]
    print(quicksort2(arr, start=0, end=size))

但是，现在列表在输入列表的后半部分没有完全排序，所以我确信它与在 quicksort2 定义底部传递的 end 关键字参数有关。

Answer 1

弄清楚我做错了什么。我真的需要使用 Lomuto Partitioning method 来满足打印语句的要求。

供以后搜索此内容的任何人使用的代码

def partition(array, lo, hi):
    pivot_index = hi
    pivot_value = array[pivot_index]
    store_index = lo

    for i in range(lo, hi):
        if array[i] <= pivot_value:
            array[i], array[store_index] = array[store_index], array[i]
            store_index += 1
    array[pivot_index], array[store_index] = array[store_index], array[pivot_index]
    return store_index 


def quicksort(array, lo, hi):
    if lo < hi:
        p = partition(array, lo, hi)
        print(' '.join([str(i) for i in array]))
        quicksort(array, lo, p-1)
        quicksort(array, p+1, hi)

if __name__ == '__main__':
    size = int(input())
    ar = [int(i) for i in input().split()]
    quicksort(ar, 0, size-1)

快速排序中间列表打印 Python

Quicksort intermediate list printing Python

python

quicksort

in-place