Python Quicksort函数进入无限循环

Question

我有词典联系人列表。

contacts = [{'first':'asasdasd', 'last':'sddafs','email':'asdsadas'},
{'first':'asasdasd', 'last':'sddafs','email':'asdsadas'}]

我想使用快速排序算法按键'last'对列表中的字典进行排序。

less = []
greater = []

def qsort_last(listD):
    if len(listD) < 2:
        return listD
    else:
        pivot = contacts[0]['last']
        for i in range(len(listD)):
            if listD[i]['last'] <= pivot:
                less.append(listD[i])
            else:
                greater.append(listD[i])
        return qsort_last(less) + [contacts[0]] + qsort_last(greater)

print(qsort_last(contacts))

现在函数进入无限循环。请指教。

Answer 1

问题是您不断向less和greater列表中添加元素，因此它们将不断增长。

此外，由于if子句中的<=，您正在复制数据透视元素。

尝试一下：

def qsort_last(listD):
    less = []
    greater = []

    if len(listD) < 2:
        return listD
    else:
        pivot = listD[0]['last']
        for i in range(len(listD)):
            if listD[i]['last'] < pivot:
                less.append(listD[i])
            elif listD[i]['last'] > pivot:
                greater.append(listD[i])
        return qsort_last(less) + [contacts[0]] + qsort_last(greater)

Answer 2

已更新。现在它可以工作了。谢谢大家的帮助。

def qsort_last(listD):
    less = []
    greater = []
    middle=[]
    if len(listD) < 2:
        return listD
    else:
        pivot = listD[0]['last']
        for i in range(len(listD)):
            if listD[i]['last'] < pivot:
                less.append(listD[i])
            elif listD[i]['last'] > pivot:
                greater.append(listD[i])
            elif listD[i]['last'] == pivot:
                middle.append(listD[i])

        return qsort_last(less) + middle + qsort_last(greater)