gpt4 book ai didi

python - Python 中的快速排序实现

转载 作者:太空狗 更新时间:2023-10-30 01:51:06 25 4
gpt4 key购买 nike

我正在尝试在 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]

最佳答案

我对算法与快速排序的联系有点困惑。在快速排序中,您通常将所有条目与一个主元进行比较,因此您会得到一个较低和较高的组; 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

关于python - Python 中的快速排序实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26634593/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com