时间戳

首页 > 解决方案 > 这种快速排序算法的实现有什么问题？错误是 RecursionError

python-3.x - 这种快速排序算法的实现有什么问题？错误是 RecursionError

问题描述

def quicksort(array):
    print(array)
    n = 0
    pivot = len(array) - 1
    while n < pivot:
        if array[pivot] > array[n]:
            n+=1
        elif array[pivot] <= array[n]:
            array[n],array[pivot-1] = array[pivot-1], array[n]
            array[pivot],array[pivot-1] = array[pivot-1], array[pivot]
            pivot -= 1
    if len(array[:pivot]) >1:
        array[:pivot] = quicksort(array[:pivot])
    if len(array[pivot+1:])> 1:
        array[pivot+1:] = quicksort(array[pivot+1:])
    return array

test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print(quicksort(test))

引发以下错误：

Error: Traceback (most recent call last):
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 18, in <module>
    print(quicksort(test))
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 14, in quicksort
    array[pivot:] = quicksort(array[pivot:])
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 14, in quicksort
    array[pivot:] = quicksort(array[pivot:])
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 12, in quicksort
    array[:pivot] = quicksort(array[:pivot])
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 14, in quicksort
    array[pivot:] = quicksort(array[pivot:])
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 14, in quicksort
    array[pivot:] = quicksort(array[pivot:])
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 14, in quicksort
    array[pivot:] = quicksort(array[pivot:])
  [Previous line repeated 987 more times]
  File "C:\Users\admin\AppData\Local\Programs\Python\Python37-32\idle.py", line 3, in quicksort
    pivot = len(array) - 1
RecursionError: maximum recursion depth exceeded while calling a Python object

标签： python-3.xalgorithmsortingquicksort

解决方案

def quicksort(array):
print(array)
n = 0
pivot = len(array) - 1
while n < pivot:
    if array[pivot] > array[n]:
        n+=1
    elif array[pivot] <= array[n]:
        array[n],array[pivot-1] = array[pivot-1], array[n]
        array[pivot],array[pivot-1] = array[pivot-1], array[pivot]
        pivot -= 1
if len(array[:pivot]) >1:
    array[:pivot] = quicksort(array[:pivot])
if len(array[pivot:])> 1:
    array[pivot:] = quicksort(array[pivot:])
return array

test = [19, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print(quicksort(test))

M Oehm 是正确的！我尝试了这个修改后的代码，它适用于具有不同元素的数组。输出是：

[19, 4, 1, 3, 9, 20, 25, 6, 21, 14]
[6, 4, 1, 3, 9]
[6, 4, 1, 3]
[3, 4, 6]
[3, 4]
[14, 25, 20, 21, 19]
[19, 20, 21, 25]
[19, 20, 21]
[19, 20]
[1, 3, 4, 6, 9, 14, 19, 20, 21, 25]
  • 如果您需要对具有重复元素的数组进行快速排序，则必须将其划分为 3 个（而不是 2 个）子数组{{Xi}, {Xk}, {Xj}}，其中{Xi}小于枢轴{xk}=pivot和{Xj} > pivot。

推荐阅读