Python中的快速排序实现 [英] Quicksort implementation in Python

问题描述

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

I'm trying to implement quicksort in python. However, my code doesn't properly sort (not quite). For example, on the input array [5,3,4,2,7,6,1], my code outputs [1,2,3,5,4,6,7]. So, the end result interposes the 4 and 5. I admit I am a bit rusty on python as I've been studying ML (and was fairly new to python before that). I'm aware of other python implementations of quicksort, and other similar questions on Stack Overflow about python and quicksort, but I am trying to understand what is wrong with this chunk of code that I wrote myself:

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

推荐答案

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

I'm a little confused about what the algorithm's connection to quicksort is. In quicksort, you typically compare all entries against a pivot, so you get a lower and higher group; the quick_sort function clearly expects your partition function to do this.

但是，在分区函数中，您永远不会将任何内容与您命名为枢轴的值进行比较.所有比较都在索引 i 和 j 之间进行，其中 j 由 for 循环递增，如果发现项目无序则 i 递增.这些比较包括对照自身检查项目.该算法更像是一种选择排序，其复杂性比冒泡排序稍差.因此，只要项目左侧有足够的项目，您就会得到冒泡的项目，第一个项目最终会在最后一个移动的项目到达的位置后倾倒；因为它从来没有与任何东西进行比较，我们知道如果它有剩余的项目，这肯定是乱序的，仅仅因为它替换了一个有序的项目.

However, in the partition function, you never compare anything against the value you name pivot. All comparisons are between index i and j, where j is incremented by the for loop and i is incremented if an item was found out of order. Those comparisons include checking an item against itself. That algorithm is more like a selection sort with a complexity slightly worse than a bubble sort. So you get items bubbling left as long as there are enough items to the left of them, with the first item finally dumped after where the last moved item went; since it was never compared against anything, we know this must be out of order if there are items left of it, simply because it replaced an item that was in order.

再想一想，这些物品只是部分订购的，因为一旦它被交换到左边，你就不会返回到它，并且它只是根据它替换的物品进行检查(现在发现已经被乱序).我认为在没有索引争吵的情况下编写预期的函数更容易:

Thinking a little more about it, the items are only partially ordered, since you do not return to an item once it has been swapped to the left, and it was only checked against the item it replaced (now found to have been out of order). I think it is easier to write the intended function without index wrangling:

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

这篇关于Python中的快速排序实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！