使用插入排序对字典列表排序

Question

这个排序是为了学习目的，不允许使用内置的排序方法。

如果你觉得我的问题和回答对你有帮助，请给我和第一个回答的人投票：@J.F. Sebastian

我在StackOverflow上找到了这个内容—— "如何在Python中对字典列表进行插入排序？"

但是那个回答似乎不太对。

使用上面问题的回答代码时，出现了这个错误：

类型错误：列表索引必须是整数，而不是字典

举个例子：

lst = [{'a':20, 'b':30, 'c':25, 'd': 600},{'a':60, 'b':10, 'c':43, 'd': 20}]`

要使用插入排序，比如对b进行排序，我们应该得到

[{'a':60, 'b':10, 'c':43, 'd': 20},{'a':20, 'b':30, 'c':25, 'd': 600}]

但我的代码得到的是

[{'b': 10, 'c': 25, 'a': 20, 'd': 600}, {'b': 30, 'c': 43, 'a': 60, 'd': 20}]

他在字典列表中替换了键和值

这是我的代码：

def insertionSort(allData, key):

    for i in range(len(allData)):
        temp = allData[i][key]
        j = i
        while j > 0 and temp < allData[j - 1][key]:
               allData[j][key] = allData[j - 1][key]
               j = j - 1
        allData[j][key] = temp

我的作业排序结果：

{'snow': 19.2, 'minT': -10.8, 'month': 12, 'maxT': 9.0, 'rain': 45.0, 'year': 2003, 'meanT': -0.1, 'yearmonth': 193801}
{'snow': 35.6, 'minT': -20.0, 'month': 1, 'maxT': 8.9, 'rain': 34.3, 'year': 1974, 'meanT': -5.9, 'yearmonth': 193802}
{'snow': 0.0, 'minT': 9.7, 'month': 8, 'maxT': 34.8, 'rain': 20.8, 'year': 2007, 'meanT': 22.4, 'yearmonth': 193803}`

在对yearmonth进行排序后，他们把yearmonth从小到大替换了，但没有改变字典。

为什么会这样，应该怎么改呢？

==================================

回答：

在对'J.F. Sebastian'的代码进行了一些基本的复制后，我发现我不能直接使用这段代码

sort(a,b)

输出：

类型错误：'str'对象不可调用

我应该使用 sort(a,b=lambda x: x['thekey']) 然后，JFS创建了一个新函数来让它工作。

我还发现了另一种方法： 只需更改JFS代码的第5行：

从

    if key(L[j]) <= key(d):

到

    if L[j][key] <= d[key]:

然后一切都正常了！ 希望这也能帮助其他人，尤其是那些使用谷歌并做和我一样作业的人。

Answer 1

试着写一个插入排序的程序，专门用来处理整数列表。然后，你可以很容易地修改这个程序，让它接受一个 key 参数，这样就可以进行任意的比较了：

def insertion_sort_impl(L, *, key):
    for i in range(1, len(L)): # loop-invariant: `L[:i]` is sorted
        d = L[i]
        for j in range(i - 1, -1, -1): 
            if key(L[j]) <= key(d): 
               break
            L[j + 1] = L[j]
        else: # `key(L[j]) > key(d)` for all `j`
            j -= 1
        L[j + 1] = d

示例：

lst = [{'a':20, 'b':30, 'c':25, 'd': 600},{'a':60, 'b':10, 'c':43, 'd': 20}]
insertion_sort_impl(lst, key=lambda x: x['d']) # sort by `d` key
print(lst)

输出

[{'a': 60, 'c': 43, 'b': 10, 'd': 20}, {'a': 20, 'c': 25, 'b': 30, 'd': 600}]

注意：字典中的键的顺序可以忽略。它可能在每次运行时都不同，但值较小的字典 d 总是会在左边。

这里的 key 是 insertion_sort_impl() 函数的一个名字，它和字典的键没有关系。这是很多内置函数使用的命名方式；key 用来获取一个值，以便进行比较：

>>> max([1, 2], key=lambda x: -x)
1
>>> min([1, -2], key=lambda x: x*x)
1
>>> sorted([-1, 0, 1], key=lambda x: x*x-x)
[0, 1, -1]

如果你想了解为什么循环是从 1 开始的，可以看看关于 插入排序 的一般描述。

如果 insertion_sort 函数的接口是固定的，那么你可以根据 insertion_sort_impl 来定义它：

from operator import itemgetter

def insertion_sort(L, key):
    return insertion_sort_impl(L, key=itemgetter(key))