python 快速排序使用递归

Question

我知道它可能会重复，但还没有弄清楚我的代码的哪一部分导致了递归错误。它应该使用少于 1000 个堆栈，这是 Python 中的递归限制。

import random

def quick_sort(arr):
    # if array is empty or has only 1 element
    # it means the array is already sorted, so return it.
    if len(arr) < 2:
        return arr
    else:
        rand_index = random.randint(0,len(arr)-1)
        pivot = arr[rand_index]
        less = []
        greater = []

        # create less and greater array comparing with pivot
        for i in arr:
            if i <= pivot:
                less.append(i)
            else:
                greater.append(i)

        return quick_sort(less) + [pivot] + quick_sort(greater)

if __name__ == "__main__":
    sample_array = [6,3,7,2,7,4,7,3,21,54,0,6,5,3,1,3]
    sorted_array = quick_sort(sample_array)
    print(sorted_array)

错误代码如下:

  File "quick_sort.py", line 24, in <module>
    sorted_array = quick_sort(sample_array)
  File "quick_sort.py", line 20, in quick_sort
    return quick_sort(less) + [pivot] + quick_sort(greater)
  File "quick_sort.py", line 20, in quick_sort
    return quick_sort(less) + [pivot] + quick_sort(greater)
  File "quick_sort.py", line 20, in quick_sort
    return quick_sort(less) + [pivot] + quick_sort(greater)
  [Previous line repeated 991 more times]
  File "quick_sort.py", line 9, in quick_sort
    rand_index = random.randint(0,len(arr)-1)
  File "C:\Program Files (x86)\Python36-32\lib\random.py", line 221, in randint
    return self.randrange(a, b+1)
  File "C:\Program Files (x86)\Python36-32\lib\random.py", line 197, in randrange
    return istart + self._randbelow(width)
  File "C:\Program Files (x86)\Python36-32\lib\random.py", line 231, in _randbelow
    if type(random) is BuiltinMethod or type(getrandbits) is Method:
RecursionError: maximum recursion depth exceeded while calling a Python object

非常感谢您的帮助。谢谢!

Answer 1

您不需要将相同的数字添加到less。将它添加到新数组并将其放在 return 语句的中间。试试这个:

def quick_sort(arr):
    # if array is empty or has only 1 element
    # it means the array is already sorted, so return it.
    if len(arr) < 2:
        return arr
    else:
        rand_index = random.randint(0,len(arr)-1)
        pivot = arr[rand_index]
        less = []
        equal_nums = []
        greater = []

        # create less and greater array comparing with pivot
        for i in arr:
            if i < pivot:
                less.append(i)
            if i > pivot:
                greater.append(i)
            if i == pivot:
                equal_nums.append(i)

        return quick_sort(less) + equal_nums + quick_sort(greater)

或者尝试使用(和理解)更多 pythonic 解决方案:

def qsort(L):
    if L: return qsort([x for x in L if x<L[0]]) + [x for x in L if x==L[0]] + qsort([x for x in L if x>L[0]])
    return []