蟒蛇中的快速排序3.最后一个数据透视

Question

感谢您花时间阅读这篇文章：）我正在python中实现我自己版本的快速排序，我正试图在以前学校作业的一些限制范围内实现它。请注意，我之所以避免使用IN，是因为在我工作的项目中不允许使用IN（不确定原因：3）。

它对整数和字符串运行良好，但我无法将其适用于我的CounterList（），这是一个节点列表，每个节点中都包含一个任意整数和字符串，尽管我只是根据这些节点中包含的整数进行排序。

粘贴：

• 我的快速排序：http://pastebin.com/mhAm3YYp.
• CounterList和CounterNode，代码。http://pastebin.com/myn5xuv6.

---

from classes_1 import CounterNode, CounterList
def bulk_append(array1, array2):
    # takes all the items in array2 and appends them to array1
    itr = 0
    array = array1
    while itr < len(array2):
        array.append(array2[itr])
        itr += 1
    return array

def quickSort(array):
    lss = CounterList()
    eql = CounterList()
    mre = CounterList()
    if len(array) <= 1:
        return array # Base case.
    else:
        pivot = array[len(array)-1].count # Pivoting on the last item.
        itr = 0
        while itr < len(array)-1: 
        # Essentially editing "for i in array:" to handle CounterLists
            if array[itr].count < pivot:
                lss.append(array[itr])
            elif array[itr].count > pivot:
                mre.append(array[itr])
            else:
                eql.append(array[itr])
            itr += 1
        # Recursive step and combining seperate lists.    
        lss = quickSort(lss)
        eql = quickSort(eql)
        mre = quickSort(mre)
        fnl = bulk_append(lss, eql)
        fnl = bulk_append(fnl, mre)
        return fnl

---

我知道这可能很简单，但我似乎看不出这个问题。（以最后一项为中心）

以下是我使用的测试：

a = CounterList()
a.append(CounterNode("ack", 11))
a.append(CounterNode("Boo", 12))
a.append(CounterNode("Cah", 9))
a.append(CounterNode("Doh", 7))
a.append(CounterNode("Eek", 5))
a.append(CounterNode("Fuu", 3))
a.append(CounterNode("qck", 1))
a.append(CounterNode("roo", 2))
a.append(CounterNode("sah", 4))
a.append(CounterNode("toh", 6))
a.append(CounterNode("yek", 8))
a.append(CounterNode("vuu", 10))
x = quickSort(a)
print("nFinal List: n", x)

以及由此产生的CounterList:

['qck': 1, 'Fuu': 3, 'Eek': 5, 'Doh': 7, 'Cah': 9, 'ack': 11]

正如你所知，哪个缺少多个值？不管怎样，谢谢你的建议和时间。

Answer 1

代码中有两个错误：

1. 您不需要"eql=quickSort（eql）"行，因为它包含所有相等的值，所以不需要排序。

2. 在每次递归调用中，由于没有将pivot附加到任何列表中，因此会丢失pivot（缺少条目的原因）。您需要将其附加到eql中。所以下面显示的代码行之后：

   pivot=array[len（array）-1].count

插入此行：

eql.append(array[len(array)-1])

此外，从代码中删除以下行，因为它有时可能会导致递归深度（仅适用于具有一些重复值的数组，如果任何重复值被选为枢轴）：

eql = quickSort(eql)