快速排序的非递归写法
时间: 2023-06-21 11:18:16 浏览: 51
快速排序的非递归写法可以使用栈来实现。具体步骤如下:
1. 定义一个栈,将整个序列的起始和结束位置入栈。
2. 从栈中取出一个区间,将区间分为左右两部分,选取一个基准值将左右两部分分别进行排序。
3. 将排序后的左右两部分的区间起始和结束位置依次入栈。
4. 重复第2、3步,直到栈为空。
下面是 Python 实现代码:
```python
def quick_sort_no_recursion(arr):
stack = [(0, len(arr) - 1)]
while stack:
left, right = stack.pop()
if left >= right:
continue
pivot = partition(arr, left, right)
stack.append((left, pivot - 1))
stack.append((pivot + 1, right))
def partition(arr, left, right):
pivot = arr[right]
i = left - 1
for j in range(left, right):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[right] = arr[right], arr[i+1]
return i+1
```
其中 partition 函数是快速排序的核心,用于将序列分成左右两部分并返回基准值的位置。快速排序的时间复杂度为 O(nlogn)。