Python中的快速排序实现

Question

我正在尝试用python实现快速排序。但是，我的代码不能正确排序(不完全是)。例如，在输入数组5,3,4,2,7,6,1上，我的代码输出1,2,3, 5 ,4,6,7。所以，最终的结果是4和5。我承认我对python有点生疏，因为我一直在学习ML (在此之前，我对python还很陌生)。我知道快速排序的其他python实现，以及关于python和快速排序的Stack Overflow上的其他类似问题，但我正在尝试理解我自己编写的这段代码的错误之处：

#still broken 'quicksort'

def partition(array):
    pivot = array[0]
    i = 1 
    for j in range(i, len(array)):
        if array[j] < array[i]:
            temp = array[i]
            array[i] = array[j]
            array[j] = temp
            i += 1
    array[0] = array[i]
    array[i] = pivot
    return array[0:(i)], pivot, array[(i+1):(len(array))]

def quick_sort(array):
    if len(array) <= 1: #if i change this to if len(array) == 1 i get an index out of bound error
        return array 

    low, pivot, high = partition(array)
    #quick_sort(low)
    #quick_sort(high)

    return quick_sort(low) + [pivot] + quick_sort(high)

array = [5,3,4,2,7,6,1]

print quick_sort(array)
# prints [1,2,3,5,4,6,7]

Answer 1

我对算法与快速排序的关系感到有点困惑。在快速排序中，通常会将所有条目与轴心进行比较，因此会得到一个越来越高的组；quick_sort函数显然希望分区函数能做到这一点。

但是，在分区函数中，您永远不会将任何内容与您命名为pivot的值进行比较。所有比较都是在索引i和j之间进行的，其中j由for循环递增，如果发现某项顺序错误，则i递增。这些比较包括检查项目本身。该算法更像是一种选择排序，其复杂性比冒泡排序略差。所以，只要左边有足够的项目，你就会让项目向左冒泡，第一个项目最终会在最后移动的项目放到哪里后被转储；因为它从未与任何东西进行比较，所以我们知道，如果有剩余的项目，这肯定是无序的，因为它替换了一个正常的项目。

再仔细考虑一下，这些项目只是部分订购的，因为一旦项目被交换到左侧，您就不会返回到项目，并且只检查它所替换的项目(现在发现已经失序)。我认为在没有索引争论的情况下编写预期的函数会更容易：

def partition(inlist):
    i=iter(inlist)
    pivot=i.next()
    low,high=[],[]
    for item in i:
        if item<pivot:
            low.append(item)
        else:
            high.append(item)
    return low,pivot,high

Answer 2

您可能会发现这些参考实现在尝试理解您自己的实现时很有帮助。

返回新列表的：

def qsort(array):
    if len(array) < 2:
        return array
    head, *tail = array
    less = qsort([i for i in tail if i < head])
    more = qsort([i for i in tail if i >= head])
    return less + [head] + more

对列表进行就地排序：

def quicksort(array):
    _quicksort(array, 0, len(array) - 1)

def _quicksort(array, start, stop):
    if stop - start > 0:
        pivot, left, right = array[start], start, stop
        while left <= right:
            while array[left] < pivot:
                left += 1
            while array[right] > pivot:
                right -= 1
            if left <= right:
                array[left], array[right] = array[right], array[left]
                left += 1
                right -= 1
        _quicksort(array, start, right)
        _quicksort(array, left, stop)

从迭代器生成排序项的：

def qsort(sequence):
    iterator = iter(sequence)
    try:
        head = next(iterator)
    except StopIteration:
        pass
    else:
        try:
            tail, more = chain(next(iterator), iterator), []
            yield from qsort(split(head, tail, more))
            yield head
            yield from qsort(more)
        except StopIteration:
            yield head

def chain(head, iterator):
    yield head
    yield from iterator

def split(head, tail, more):
    for item in tail:
        if item < head:
            yield item
        else:
            more.append(item)

Answer 3

如果pivot最终需要保持在初始位置(b/c是最低值)，则无论如何都要将其与其他一些元素交换。