Python 中的快速排序实现

我正在尝试在 python 中实现快速排序。但是，我的代码没有正确排序（不完全）。例如，在输入数组 [5,3,4,2,7,6,1] 上，我的代码输出 [1,2,3,5,4,6,7]。所以，最终结果插入了 4 和 5。我承认我对 python 有点生疏，因为我一直在研究 ML（并且在此之前对 python 相当陌生）。我知道快速排序的其他 python 实现，以及 Stack Overflow 上有关 python 和快速排序的其他类似问题，但我试图理解我自己编写的这段代码有什么问题：

#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]

我对算法与快速排序的联系有点困惑。在快速排序中，您通常将所有条目与主元进行比较，因此您会得到较低和较高的组； fast_sort 函数显然希望您的分区函数执行此操作。

但是，在分区函数中，您永远不会将任何内容与您命名的数据透视值进行比较。所有比较都在索引 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