我已经成功测试了我的代码。它以最后一个元素作为关键点。 但是,当我尝试数总数没有。所做的比较,它显示不正确的计数。 我在计算通过全局变量tot_comparisons。以最后一个元素为转轴快速排序python
建议,我哪里错了? 我正在做一些愚蠢的错误吗?
def swap(A,i,k):
temp=A[i]
print "temp is "
print temp
A[i]=A[k]
A[k]=temp
def partition(A,start,end):
pivot=A[end]
pivot_index=start
#pivot=A[end]
for i in range(start,end):
#if A[i]<=pivot:
if A[i]<pivot:
print 'HHHHHHHHHHHHHhh'
swap(A,i,pivot_index)
pivot_index+=1
#swap(A,pivot_index,end)
swap(A,pivot_index,end)
return pivot_index
def quicksort(A,start,end):
global tot_comparisons
if start<end:
pivot_index=partition(A,start,end)
tot_comparisons+=end-start
print "pivot_index"
print pivot_index
print "ENDS"
quicksort(A, start,pivot_index-1)
#tot_comparisons+=end-pivot_index
#quicksort(A, pivot_index, end)
quicksort(A, pivot_index+1, end)
#A=[45,21,23,4,65]
#A=[21,23,19,22,1,3,7,88,110]
#A=[1,22,3,4,66,7]
#A=[1, 3, 7, 19, 21, 22, 23, 88, 110]
#A=[7,2,1,6,8,5,3,4]
temp_list=[]
f=open('temp_list.txt','r')
for line in f:
temp_list.append(int(line.strip()))
f.close()
print 'list is '
#print temp_list
print 'list ends'
tot_comparisons=0
#quicksort(A, 0, 7)
quicksort(temp_list, 0, 9999)
#quicksort(temp_list, 0, len(temp_list))
print 'hhh'
print temp_list
print tot_comparisons
#print A
只是想你的代码,不工作,'指数超出范围exception' – Netwave
工作成功地在我结束.. 160361是tot_comparisons输出使用我的代码以上 – fsociety