如何使用递归实现快速排序 [英] How to implement quicksort using recursion

问题描述

我正在练习使用递归来实现快速排序算法.我收到错误:

I am practicing using recursion to implement the quicksort algorithm. I am getting the error:

RecursionError: 比较时超出了最大递归深度

RecursionError: maximum recursion depth exceeded in comparison

这里是错误:

In [2]: run quicksort.py
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
~/Desktop/algo/quicksort.py in <module>()
     27 
     28 test = QuickSort()
---> 29 print(test.partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7))

~/Desktop/algo/quicksort.py in partition(array, start, end)
     20     def partition(array, start, end):
     21         if start < end:                       # this is enough to end recursion
---> 22             pos = QuickSort.partition(array, start, end)
     23             QuickSort.quickSort(array, start, pos - 1)
     24             QuickSort.quickSort(array, pos + 1, end)

... last 1 frames repeated, from the frame below ...

~/Desktop/algo/quicksort.py in partition(array, start, end)
     20     def partition(array, start, end):
     21         if start < end:                       # this is enough to end recursion
---> 22             pos = QuickSort.partition(array, start, end)
     23             QuickSort.quickSort(array, start, pos - 1)
     24             QuickSort.quickSort(array, pos + 1, end)

RecursionError: maximum recursion depth exceeded in comparison

这是我当前的代码(我使用一个类以便其他人可以知道我正在实现什么算法):

Here is my current code (I use a class so other people can know what algorithm I am implementing):

class QuickSort:
    def __init__(self):
        self.name = "Quick Sort"
    @staticmethod
    def quickSort(arr, start, end):
        pivot = arr[end]
        i = start-1
        for x in range(start, end):
            if arr[x] > pivot:
                continue
            else:
                i += 1
                arr[i],arr[x] = arr[x],arr[i]
        for y in range(end, i + 1, -1):
            arr[y] = arr[y-1]
        arr[i + 1] = pivot
        return arr.index(pivot)
    @staticmethod
    def partition(array, start, end):
        if start < end:  # this is enough to end recursion
            pos = QuickSort.partition(array, start, end)
            QuickSort.quickSort(array, start, pos - 1)
            QuickSort.quickSort(array, pos + 1, end)

test = QuickSort()
print(test.partition([7, 2, 1, 8, 6, 3, 5, 4], 0, 7))

所以这里的quickSort"基本上是执行第一个操作.之后，分区"将使用递归来解决问题.

So here "quickSort" basically performs the first operation. After that, "partition" will use recursion to solve the problem.

推荐答案

quickSort 应该调用分区(而不是分区调用快速排序).示例单一功能代码，快速排序功能中包含分区代码.此示例还通过仅对较小部分使用递归和对较大部分使用迭代(循环)将堆栈空间限制为 O(log(n)).最坏情况的时间复杂度仍然是 O(n^2).

quickSort should be calling partition (versus partition calling quicksort). Example single function code, with partition code included in quicksort function. This example also limits stack space to O(log(n)) by only using recursion for the smaller part, and iteration (loop) for the larger part. Worst case time complexity is still O(n^2).

class QuickSort:
    def __init__(self):
        self.name = "Quick Sort"
    @staticmethod
    def quickSort(a, lo, hi):
        while(lo < hi):
            pivot = a[hi]             # Lomuto partition
            i = lo
            for j in range(lo, hi):
                if a[j] < pivot:
                    a[i],a[j] = a[j],a[i]
                    i += 1
            a[i],a[hi] = a[hi],a[i]   # swap pivot to a[i]
            # recurse on smaller part, iterate on larger part
            if(i - lo <= hi - i):
                QuickSort.quickSort(a, lo, i-1)
                lo = i+1
            else:
                QuickSort.quickSort(a, i+1, hi)
                hi = i-1

test = QuickSort()
a = [7, 2, 1, 8, 6, 3, 5, 4]
test.quickSort(a, 0, len(a)-1)
print(a)

这篇关于如何使用递归实现快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！