Python 上的合并排序：获得的结果模式异常

Question

我有一个未排序的数组，其中包含从 0 到 9,999 的 10,000 个整数。我想对这个未排序的数组应用合并排序，我写了下面的代码-

import sys
def merge_sort(data):
    result = []
    if len(data) <= 1:
        return data
    else:
        mid = int(len(data)/2)
        left = data[:mid]
        right = data[mid:]
        sorted_left = merge_sort(left)
        sorted_right = merge_sort(right)
        i = j = k = 0
        total_len = len(sorted_left) + len(sorted_right)
        for k in range(0, total_len):
            if i < len(sorted_left) and j < len(sorted_right):
                if sorted_left[i] < sorted_right[j]:
                    result.append(sorted_left[i])
                    i = i+1
                    k = k+1
                elif sorted_left[i] > sorted_right[j]:
                    result.append(sorted_right[j])
                    j = j+1
                    k = k+1
            elif i < len(sorted_left):
                result.append(sorted_left[i])
                i = i+1
                k = k+1
            elif j < len(sorted_right):
                result.append(sorted_right[j])
                j = j+1
                k = k+1
            else:
                sys.exit("There is some issue with the code")
        return result
print merge_sort(data)

因此，当我对这些数据进行排序时，除了少数条目外，我得到了正确的排序顺序。例如-最后我得到这种结果-

[...'9989', '999', '9990', '9991', '9992', '9993', '9994', '9995', '9996', '9997', ' 9998', '9999']

如您所见，数字“999”放错了地方。不仅在这个片段中，它也发生在其他地方，比如“995”出现在“9949”和“9950”之间。所以有人知道为什么会这样吗？ P.S.- 我运行此代码用于调试，它运行没有错误产生这些结果

Answer 1

您正在订购字符串：'9989' < '999' < '9990'。如果您想订购整数，则必须将输入列表转换为整数。

Answer 2

您的数据是以字符串还是整数的形式传入的？根据您的示例输出，它们是字符串。

在这种情况下，“1”会出现在“10”之前。如果您需要整数，则可以转换为 int 来进行排序。

Answer 3

你的 data 是字符串，不是数字。要转换为整数，请使用：

data = [int(x) for x in data]

Python 会 "compare" 各种各样的对象。例如：

>>> "a" < "ab"
True
>>> None < "a"
True
>>> 1 < "a"
True

如果你比较这样的项目，python不会反对。

比较python

对于整数和字符串，python 有内置的比较方法。对于您创建的对象，您可以定义自己的比较方法。您可以为 python 将用于比较的对象定义的方法 include:

object.__lt__(self, other)
object.__le__(self, other)
object.__eq__(self, other)
object.__ne__(self, other)
object.__gt__(self, other)
object.__ge__(self, other)

通过为对象定义自己的方法，具有很大的灵活性。

Python 上的合并排序：获得的结果模式异常

Merge Sort on Python: Unusual pattern of result obtained

python

python-2.7

mergesort

比较python