python-2.7 - 在python中使用合并排序排列给定的整数列表以获得最少的数字

假设我给定的数组是 [9,89,10005,77987] ，我在合并排序算法中使用了自定义比较。我想得到 [10005,77987,89,9] ，以后可以用来得到最少的数字 1000577987899 排列后numbers.I 使用 random.randint(0,100) 生成数组。
我的输入:[70, 73, 85, 60, 76]我的输出:

before: [70, 73, 85, 60, 76]
['70', '73', '85', '60', '76']
splitting the array ['70', '73', '85', '60', '76']
splitting the array ['70', '73']
merging ['70', '73']
splitting the array ['85', '60', '76']
splitting the array ['60', '76']
merging ['60', '76']
Traceback (most recent call last):
File "venture.py", line 66, in <module>
mergeSort(b)
  File "venture.py", line 33, in mergeSort
mergeSort(righthalf) #the recursive call after splitting
  File "venture.py", line 41, in mergeSort
if  int(lefthalf[i])*10**len(righthalf[j])+int(righthalf[j]) < int(righthalf[j])*10**len(lefthalf[i])+int(lefthalf[j]): #custom_comparison
IndexError: list index out of range

我的代码:

import random

def mergeSort(alist):
    if len(alist)>1:
        print "splitting the array",alist
        mid = len(alist)//2  #the floor div
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        mergeSort(lefthalf)  #the recursive call after splitting
        mergeSort(righthalf) #the recursive call after splitting

        i=0
        j=0
        k=0


        while i < len(lefthalf) and j < len(righthalf):
            if  int(lefthalf[i])*10**len(righthalf[j])+int(righthalf[j]) < int(righthalf[j])*10**len(lefthalf[i])+int(lefthalf[j]): #custom comparison
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):  #to be used when index j is out of range of len(righthalf)
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf): #to be used when index i is out of range of len(lefthalf)
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
        print "merging",alist



a = [random.randint(0,100) for c in range(5)]
print "before:",a
b = map(str, a)
print b
mergeSort(b)
print "new :",b

为什么会发生错误？ 相同的代码适用于常规比较 : if lefthalf[i] < righthalf[j]: 。我只是将 如果条件 更改为 if int(lefthalf[i])*10**len(righthalf[j])+int(righthalf[j]) < int(righthalf[j])*10**len(lefthalf[i])+int(lefthalf[j]): #custom comparison 。
我哪里错了？

最佳答案

请记住，如果原始列表 ( righthalf ) 是奇数， lefthalf 和 alist 的长度将不同。

您的 while 条件是 j < len(righthalf) 但您的 if 条件使用 lefthalf[j] 。

当 alist 为奇数且 len(alist) = 2N+1 时，在 j 上升到 len(righthalf)-1 = (N+1)-1 = N 的情况下，您会得到索引超出范围错误，因为 lefthalf[N] 超出范围。

关于python-2.7 - 在python中使用合并排序排列给定的整数列表以获得最少的数字，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32547552/