python - 在 Python 中实现快速排序

Question

我正在尝试实现快速排序。看起来很简单，实现一个枢轴函数，以便将较小的元素和较大的元素聚集在两个单独的列表中。递归地执行此操作，直到列表小到可以在常数时间内排序。

def pivot(a, pivot_index):
    # I guess you can keep two indexes one greater and one lesser and swap.
    i, j = 0, len(a)-2
    p = a[pivot_index]
    a[pivot_index] = a[len(a)-1]
    a[len(a)-1] = p

    while(i<j):
        if(a[i]<p):
            i = i + 1
        if(a[i]>p):
            temp = a[i]
            a[i] = a[j]
            a[j] = temp
            j = j - 1
        #print(a)
    return a[0:i], a[i:]

def quicksort(a):
    if len(a) <= 1:
        return a
    p = len(a)//2
    l1, l2 = pivot(a, p)
    return quicksort(l1) + quicksort(l2)

if __name__ == "__main__":
    a = [1,-9,288,91,3,4,58,67,8]
    print(quicksort(a))

我得到错误:

Traceback (most recent call last):
  File "11.py", line 79, in <module>
    print(quicksort(a))
  File "11.py", line 73, in quicksort
    return quicksort(l1) + quicksort(l2)
  File "11.py", line 73, in quicksort
    return quicksort(l1) + quicksort(l2)
  File "11.py", line 73, in quicksort
    return quicksort(l1) + quicksort(l2)
  [Previous line repeated 993 more times]

Traceback (most recent call last):
  File "11.py", line 76, in <module>
    print(quicksort(a))
  File "11.py", line 70, in quicksort
    return quicksort(l1) + quicksort(l2)
  File "11.py", line 70, in quicksort
    return quicksort(l1) + quicksort(l2)
  File "11.py", line 70, in quicksort
    return quicksort(l1) + quicksort(l2)
  [Previous line repeated 993 more times]
  File "11.py", line 69, in quicksort
    l1, l2 = pivot(a, p)
  File "11.py", line 54, in pivot
    while(i<j):
RecursionError: maximum recursion depth exceeded in comparison

可能发生的情况是在快速排序中从未调用基本情况。但不确定如何修复它。

Answer 1

The below functionality explains how exactly the quicksort has been implemented by sending the input data as an array to the quicksort function. Here we implemented quicksort using recursion as below:

1. First check whether the array contains more than 1 element or not. If there is less than or equal to one element in the array then return array.(if len(arr) <= 1 then return arr)
2. Now take a pivot element from the middle of the array(Retrieve element from half the size of array) and then calculate the pivot element in the first iteration (pivot = arr[len(arr)//2])

3. If elements in array are less than pivot element then create a left array using list comprehension in python(left = [x for x in arr if x < pivot])

4. If elements in the array is equal to pivot element then create a middle array (middle = [x for x in arr if x == pivot])

5. If elements in the array are more than pivot element then create a right array (right = [x for x in arr if x > pivot])

6. Send the left array, right array to the quicksort function and repeat them recursively until all the elements in the array are sorted.

 def quicksort(arr):
          if len(arr) <= 1:
             return arr
          pivot = arr[len(arr)//2]
          left = [x for x in arr if x < pivot]
          middle = [x for x in arr if x == pivot]
          right = [x for x in arr if x > pivot]
          return quicksort(left) + middle + quicksort(right)