代码的目的是找出总数。数组的反转。我的代码成功运行。成功测试了 6 个元素(所有元素从最高开始倒序),反转计数 = 15。此外,成功测试了 10 个元素(所有元素从最高倒序开始),反转计数 = 45 但是,对于一个大的包含 100k 个整数的文件,几乎需要 25 秒。这是预期的吗?请建议或我可以进一步缩短执行时间吗?我刚刚对传统的归并排序算法做了一个小的调整(即计算倒置总数的行) 我怎样才能进一步减少整体运行时间?
def mergeSort(final_list):
global total_count
if len(final_list)>1:
mid_no=len(final_list)//2
left_half=final_list[:mid_no]
right_half=final_list[mid_no:]
mergeSort(left_half)
mergeSort(right_half)
'''Below code is for merging the lists'''
i=j=k=0 #i is index for left half, j for the right half and k for the resultant list
while i<len(left_half) and j<len(right_half):
if left_half[i] < right_half[j]:
final_list[k]=left_half[i]
i+=1
k+=1
else:
final_list[k]=right_half[j]
print 'total count is'
print total_count
#total_count+=len(left_half)-i
total_count+=len(left_half[i:])
print 'total_count is '
print total_count
print 'pairs are '
print str(left_half[i:])+' with '+str(right_half[j])
j+=1
k+=1
while i<len(left_half):
final_list[k]=left_half[i]
k+=1
i+=1
while j<len(right_half):
final_list[k]=right_half[j]
j+=1
k+=1
'''Code for list merge ends'''
#temp_list=[45,21,23,4,65]
#temp_list=[1,5,2,3,4,6]
#temp_list=[6,5,4,3,2,1]
#temp_list=[1,2,3,4,5,6]
#temp_list=[10,9,8,7,6,5,4,3,2,1]
#temp_list=[1,22,3,4,66,7]
temp_list=[]
f=open('temp_list.txt','r')
for line in f:
temp_list.append(int(line.strip()))
print 'list is '
print temp_list
print 'list ends'
print temp_list[0]
print temp_list[-1]
'''import time
time.sleep(1000)
print 'hhhhhhhhhh'
'''
total_count=0
mergeSort(temp_list)
print temp_list