python - 在python中实现快速排序,最后一个元素作为枢轴
问题描述
我似乎无法正确完成这项工作。我在下面粘贴了我的代码。使用 print 语句,我认为发生的事情是第一遍的结果是作为答案返回的结果,尽管所有递归步骤都通过 print 显示输出它们正在按预期工作,但似乎结果不是被拯救了吗?我试图就地执行此操作,但我尝试执行此操作,但只是修改了数组 [],但我觉得我在这里有一些误解。任何帮助表示赞赏。
键盘:http ://codepad.org/jVMbbJTq
代码:
def quicksort(array):
if len(array) >1:
print "enter array", array
pivot = len(array) - 1
print "pivot", array[pivot]
x = 0
while x < pivot:
if array[x]>array[pivot]:
piv = array[pivot]
xval = array[x]
array[x] = array[pivot-1]
array[pivot] = xval
array[pivot-1] = piv
# temp = array[x]
# array[x] = array[pivot]
# array[pivot] = temp
# array.append(array.pop(x))
pivot -= 1
else:
x += 1
print "pre recur split array", array
print "left", array[:pivot]
print "right", array[pivot+1:]
quicksort(array[:pivot])
quicksort(array[pivot+1:])
print "post recur split array", array
return array
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
#test = [21, 4, 1, 3]
print quicksort(test)
print "answer", test
解决方案
我不确定这是否是您的代码的唯一问题,但您遇到的一个大问题是您的递归不会做任何有用的事情。也就是说,这两行对您没有任何作用:
quicksort(array[:pivot])
quicksort(array[pivot+1:])
他们什么都不做的原因是您所做的切片将数据从输入列表复制array
到一个新列表中。然后递归调用尝试对复制的列表进行排序。递归排序根本不会改变原始列表,所以如果你忽略它们的返回值,调用代码中什么都不会改变。
有几种方法可以解决此问题。一个简单(但效率低下)的解决方法是将每个递归调用返回的值分配回原始列表的一部分:
array[:pivot] = quicksort(array[:pivot])
array[pivot+1:] = quicksort(array[pivot+1:])
但是,如果您要执行类似的操作,则在代码前面的分区步骤中使用临时列表可能会使一切更容易理解(如果您要在期间复制所有数据,则没有理由就地分区递归)。
这是一个非常快速和肮脏的快速排序,可以复制一堆东西(因此效率不高):
def quicksort(array):
if len(array) <= 1:
return array
pivot_val = array[-1]
lower = [x for x in array if x < pivot_val]
upper = [x for x in array if x > pivot_val]
pivot_count = array.count(pivot)
return quicksort(lower) + [pivot_val]*pivot_count + quicksort(upper)
另一种更有效的方法是避免制作数据的任何副本(这意味着没有切片)。只需对所有内容进行就地排序,包括递归部分。为此,您需要能够在递归调用中传递额外的参数来指定需要排序的索引范围。幸运的是,在 Python 中向函数添加可选参数很容易(另一种选择是拥有一个单独的帮助函数来处理所有递归)。
与上面的简单修复相比,这涉及对代码的更多更改,因为您不能再将len(array)
其用作应该在何处找到枢轴的指南(或告诉您何时完成递归)。这是一个快速的尝试,但我可能有一个错误或其他一些您需要调试的错误:
def quicksort(array, low=0, high=None): # add optional arguments
if high == None:
high = len(array) - 1 # set high if it got the default
if high - low > 0:
pivot = high # use high and low to set up pivot and x
x = low
while x < pivot:
if array[x]>array[pivot]: # this part stays the same
piv = array[pivot]
xval = array[x]
array[x] = array[pivot-1]
array[pivot] = xval
array[pivot-1] = piv
pivot -= 1
else:
x += 1
quicksort(array, low, pivot-1) # pass on new high and low values
quicksort(array, pivot+1, high)
return array # you probably don't need this line any more
如果您采用这种就地方法,您可能希望摆脱return array
该功能的一部分。就地操作的 Python 函数的标准是返回None
(如果没有任何return
语句,就会发生这种情况)。您将熟悉的许多方法都是这样工作的。例如,list.append
不返回任何内容,也不list.sort
(“官方”排序功能)。标准库模块中的函数,如修改您传递的列表时random.shuffle
也会返回。None
推荐阅读
- java - 要安装 kudu,我们需要安装 java 吗?
- kubernetes - 本地高可用性 Kubernetes 集群形成中的负载均衡器
- cytoscape.js - 使用 cytoscape.js 如何自动扩展图形容器的高度?
- java - 如何在 Android 中以编程方式创建弹出窗口
- http - Golang *bytes.Buffer nil 导致致命错误
- saml - Shibboleth:具有不同数据类型的 SAML 断言属性
- python - 从在特定列中具有数字或字母数字的原始数据框中获取所有行?
- angular - 如何修复“无法在 ./src/global.scss 中编译”
- javascript - 用参数链接到路由的正确方法是什么?
- python - 在 Pandas 数据框中转置一行的几个元素