Python QuickSort上半场仅分类

Question

我正在参加普林斯顿的算法 - 访问课程 - 第三周，并尝试实现QuickSort。

这是我当前的实施，并准备运行一些测试：

import unittest
def quicksort(x):
    if len(x) <= 1:
        return x
    pivot = x[0]
    xLeft, xRight = partition(x)
    print(xLeft, xRight)
    quicksort(xLeft)
    quicksort(xRight)
    return x

def partition(x):
    j = 0
    print('partition', x)
    for i in range(0, len(x)):
        if x[i] < x[0]:
            n = x[j + 1]
            x[j + 1] = x[i]
            x[i] = n
            j += 1
    p = x[0]
    x[0] = x[j]
    x[j] = p
    return x[:j + 1], x[j + 1:]

class Test(unittest.TestCase):
    def test_partition_pivot_first(self):
        arrays = [
            [3, 1, 2, 5],
            [3, 8, 2, 5, 1, 4, 7, 6],
            [10, 100, 3, 4, 2, 101]
        ]
        expected = [
            [[2, 1, 3], [5]],
            [[1, 2, 3], [5, 8, 4, 7, 6]],
            [[2, 3, 4, 10], [100, 101]]
        ]
        for i in range(0, len(arrays)):
            xLeft, xRight = partition(arrays[i])
            self.assertEqual(xLeft, expected[i][0])
            self.assertEqual(xRight, expected[i][1])
    def test_quicksort(self):
        arrays = [
            [1, 2, 3, 4, 5, 6],
            [3, 5, 6, 10, 2, 4]
        ]
        expected = [
            [1, 2, 3, 4, 5, 6],
            [1, 2, 3, 4, 6, 10]
        ]
        for i in range(0, len(arrays)):
            arr = arrays[i]
            quicksort(arr)
            self.assertEqual(arr, expected[i])

if __name__ == "__main__":
    unittest.main()

因此，对于array = [3, 5, 6, 10, 2, 4]，我得到了[2, 3, 6, 10, 5, 4] ...我无法弄清楚我的代码有什么问题。它可以分区，但是结果不在...

有人可以进去吗？:)谢谢！

Answer 1

实际上是如此小的问题，你会笑问题与QuickSort函数存在正确的是：

def quicksort(x):
 if len(x) <= 1:
    return x
 pivot = x[0]
 xLeft, xRight = partition(x)
 print(xLeft, xRight)
 quicksort(xLeft)
 quicksort(xRight)
 x=xLeft+xRight #this one!
 return x

发生的事情是python创建了一个新对象，从这些Xleft和Xright创建了它们从来都不是一个位置

所以这是一种解决方案(未使用(另一个是通过列表，start_index，end_index并在适当的位置

好事做得好！编辑：实际上，如果您要打印Xleft和Xright，您会看到它的性能完美：(