QuickSort Python算法

Question

我对算法很陌生，我为家庭作业写了一个快速排序算法，但是有些地方不对劲。我找了几个小时，在任何可能的地方，我都找不到为什么它不工作！

def quick_sort(array):

    if len(array) > 1:

       pivot = array[0]
       index_lower = 1

       for index in range(len(array)):

            if array[index] < pivot:
                array[index_lower], array[index] = array[index], array[index_lower]
                index_lower += 1

       array[index_lower-1], array[0] = array[0], array[index_lower-1]

       left_array = array[:index_lower]
       pivot = array[index_lower:index_lower+1]
       right_array = array[index_lower+1:]

       quick_sort(left_array)
       quick_sort(right_array)

       sorted_array = left_array + pivot + right_array

       return sorted_array

array = [78, 45, 2, 111, 49, 44, 98, 777, 345, 6548, 4954654, 123, 1, 3, 5]

x = quick_sort(array)
print x

我在这段代码上得到的输出是：

3，2，1，5，44，45，49，78,345,777,123,111，98,6548,4954654

Answer 1

您正在混合两种实现递归函数的样式：

1. 递归函数接收数组并返回排序的新数组。
2. 递归函数接收数组并修改相同的数组，而不返回任何内容。

因为您在len(array) <= 1时没有返回任何内容，并且您对quicksort(left_array)的结果不做任何操作，所以会出现故障。

( 2)由于只对输入array本身执行初始排序，而left_array + pivot + right_array的结果没有将应用于原始数组，因此出现故障。

最简单的方法可能是只使用第一种样式编写函数，因为第二种样式需要很好地了解python变量是如何就地修改和在函数之间传递的。

Answer 2

返回排序后的数组，但不要使用返回值：

   left_array = quick_sort(left_array)
   right_array = quick_sort(right_array)

Answer 3

问题就在这里：

   quick_sort(left_array)
   quick_sort(right_array)

我看到了递归调用，但是您放弃了结果。

它应该是

   left_array = quick_sort(left_array)
   richt_array = quick_sort(right_array)

您还忘记了数组长度为1的情况下的返回。