python - 如何使用递归实现快速排序
问题描述
我正在练习使用递归来实现快速排序算法。我收到错误消息:
RecursionError:比较超过最大递归深度
这是错误:
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
这是我当前的代码(我使用一个类,以便其他人可以知道我正在实现什么算法):
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”基本上执行了第一个操作。之后,“分区”将使用递归来解决问题。
解决方案
quickSort 应该调用分区(而不是分区调用快速排序)。示例单个函数代码,分区代码包含在快速排序函数中。此示例还通过仅对较小部分使用递归和对较大部分使用迭代(循环)将堆栈空间限制为 O(log(n))。最坏情况的时间复杂度仍然是 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)
推荐阅读
- java - 如何激活 Java 类资源查找缓存?
- c# - 如何在 mvc 中使用 ViewModel 从视图获取多个列表到控制器
- python - 使用python将(理想情况下)doc转换为pdf或将docx转换为pdf,但出现错误
- c++ - C++ Winmm PlaySound API 返回 False 且不播放声音
- c# - 使用堆栈面板内的按钮导航到页面的框架
- python - 试图制作一个函数来调用石头剪刀布游戏但显示错误无效命令名称“.!button8”
- testing - 如何将功能文件关键字连接到空手道中的 java 代码?
- php - 在 php 中使用多重选择需要数据库中的多行
- javascript - 在电子应用程序中如何在 Mac OS 和 Windows 的侧边栏视图中显示给定目录
- eslint - 如何使用 Vue 3 和 Prettier 自定义 HTML 格式?