快速排序非递归 python
时间: 2023-11-16 08:00:52 浏览: 44
快速排序是一种常用的排序算法,它的递归实现已经在上一期中介绍过了。而非递归实现快速排序的方法也是存在的,可以通过使用堆栈来模拟递归的过程。下面是Python的非递归快排实现代码:
```python
def QuickSort_No_Stack(nums:list,left:int,right:int) -> list:
temp = [left,right]
while temp:
j = temp.pop() # j = right
i = temp.pop() # i = left
index = getIndex(nums,i,j)
if i < index-1: # 压入堆栈 注意左右边界的顺序
temp.append(i)
temp.append(index-1)
if j > index+1:
temp.append(index+1)
temp.append(j)
return nums
```
其中,getIndex函数是快速排序中的一个关键步骤,用于获取基准值的位置。具体实现可以参考上一期的递归实现。
相关问题
快速排序非递归python
快速排序是一种常用的排序算法,它的主要思想是通过一趟排序将待排序列分割成独立的两部分,其中一部分的所有元素都比另一部分的所有元素小,然后再按此方法对这两部分分别进行快速排序,整个排序过程可以递归进行,也可以使用非递归的方式实现。
以下是使用非递归方式实现快速排序的Python代码:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
stack = [(0, len(arr) - 1)]
while stack:
left, right = stack.pop()
if left >= right:
continue
pivot = arr[left]
i, j = left, right
while i < j:
while i < j and arr[j] >= pivot:
j -= 1
arr[i] = arr[j]
while i < j and arr[i] <= pivot:
i += 1
arr[j] = arr[i]
arr[i] = pivot
stack.append((left, i - 1))
stack.append((i + 1, right))
return arr
```
该代码使用了栈来模拟递归过程,每次取出栈顶的左右边界,进行一次快速排序,然后将左右子序列的左右边界入栈,直到栈为空。
快速排序的非递归算法
快速排序是一种常用的排序算法,其非递归实现可以使用栈来模拟递归调用的过程。具体实现步骤如下:
1. 定义一个栈,将数组的起始位置和终止位置入栈。
2. 以栈空为条件开始进行循环,取出栈中的两个元素作为区间进行一次快排调用。
3. 函数会返回一个标准值所在的位置,以其左侧的起点和终点、右侧的起点和终点进行判断,在起点小于终点的情况下分别对其进行入栈。
4. 继续循环直到栈空为止。
下面是快速排序的非递归算法的Python实现:
```python
def quicksort(arr):
if len(arr) <= 1:
return arr
stack = [(0, len(arr) - 1)]
while stack:
low, high = stack.pop()
if low < high:
pivot = partition(arr, low, high)
stack.append((low, pivot - 1))
stack.append((pivot + 1, high))
return arr
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
```