快速排序 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

您 return 排序数组，但从未使用 return 值：

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

Answer 2

您混合了两种实现递归函数的方式：

递归函数接收一个数组和returns一个排序的新数组
递归函数接收一个数组并修改同一个数组，returns什么都没有。

1) 已损坏，因为您在 len(array) <= 1 时未返回任何内容，并且您对 quicksort(left_array).

的结果不执行任何操作

2) 已损坏，因为您仅对输入 array 本身进行初始排序，而 left_array + pivot + right_array 的结果未应用 到原始数组.

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

Answer 3

问题就在这里：

   quick_sort(left_array)
   quick_sort(right_array)

我看到了递归调用，但是你丢弃了结果。

应该是

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

你还忘记了数组长度为1的情况下的return

快速排序 Python 算法

QuickSort Python Algorithm

python

sorting

algorithm

recursion

quicksort