Python中的Quicksort实现

Question

我正在尝试在python中实现quicksort.但是,我的代码没有正确排序(不完全).例如,在输入数组[5,3,4,2,7,6,1]上,我的代码输出[1,2,3,5,4,6,7].因此,最终结果介于4和5.我承认我在python上有点生疏,因为我一直在研究ML(在此之前它对python来说还是比较新的).我知道quicksort的其他python实现,以及关于python和quicksort的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

关于算法与quicksort的连接是什么,我有点困惑.在快速排序中,您通常会将所有条目与数据透视表进行比较,因此您可以获得越来越高的组; 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