Python中使用heapq模块对字符串列表进行堆排序无效

Question

我在阅读Python 2.7的文档时，发现了一个叫heapq的模块。我对里面的heapify()和heappop()这两个方法很感兴趣。所以，我决定写一个简单的整数堆排序程序：

from heapq import heapify, heappop

user_input = raw_input("Enter numbers to be sorted: ")
data = map (int, user_input.split(","))
new_data = []

for i in range(len(data)):
    heapify(data)
    new_data.append(heappop(data))

print new_data

这个程序运行得非常顺利。

为了让事情更有趣，我想去掉整数转换，直接用字符串。理论上，这样做应该没问题，代码应该和处理整数时一样有效：

from heapq import heapify, heappop
user_input = raw_input("Enter numbers to be sorted: ")
data = user_input.split(",")
new_data = []

for i in range(len(data)):
    heapify(data)
    print data
    new_data.append(heappop(data))

print new_data

注意：我在for循环里加了一个打印语句，用来查看堆化后的列表。

运行这个脚本时的输出结果是：

`$ python heapsort.py 
Enter numbers to be sorted: 4, 3, 1, 9, 6, 2
[' 1', ' 3', ' 2', ' 9', ' 6', '4']
[' 2', ' 3', '4', ' 9', ' 6']
[' 3', ' 6', '4', ' 9']
[' 6', ' 9', '4']
[' 9', '4']
['4']
[' 1', ' 2', ' 3', ' 6', ' 9', '4']`

我认为既然是比较字符串，那么如果它们是数字，树的结构应该是一样的。然而，很明显，在第三次迭代后，堆化的结果就不对了。有人能帮我看看我是不是漏掉了什么吗？我在RedHat 3.4.6-9上运行的是Python 2.4.5。

谢谢，
VSN

Answer 1

你应该把空格去掉。这些空格是导致排序奇怪的原因。字符串的排序是一个字符一个字符地进行的，使用的是ASCII码。

所以可以试试：

from heapq import heapify, heappop
user_input = raw_input("Enter numbers to be sorted: ")
data = user_input.split(",")
data = map(str.strip, data)
new_data = []

heapify(data)
for i in range(len(data)):
    print(data)
    new_data.append(heappop(data))

print(new_data)

排序

这个问题主要是关于排序，而不是关于 heapq。在这个上下文中，排序其实就是看 < 和 <= 是怎么工作的。

数字的排序比较直观，但字符串就不一样了。通常情况下，字符串是根据它们的字符逐个进行排序的，排序的依据是它们的二进制模式。这就是下面这种行为的原因：

>>> sorted("abcABC")
['A', 'B', 'C', 'a', 'b', 'c']

字母 A 的ASCII码是65，而 a 的ASCII码是97（可以查看 ASCII表）。

排序是逐个字符进行的。如果字符串 a 是另一个字符串 b 的前缀，那么 a 总是小于 b。

>>> sorted(["123", "1", "2", "3", "12", "15", "20"])
['1', '12', '123', '15', '2', '20', '3']

你想要的排序方式叫做“自然排序”。可以查看 natsort 来实现这个功能。