快速排序非递归实现--python

主要思想是：每次把待排序数组分为两部分，左边小于轴右边大于轴，把分开的数组的收尾数组的索引存到辅助栈空间里，替换递归。两种思路：

思路一:严老师数据结构里面的思路

def partition(nums,low,high):
high_flag = True
low_flag = False
pivot = nums[low]
while low < high and low < len(nums) and high < len(nums):
if high_flag:
if nums[high] < pivot:
nums[low] = nums[high]
high_flag = False
low_flag = True
else:
high -= 1
if low_flag:
if nums[low] > pivot:
nums[high] = nums[low]
high_flag = True
low_flag = False
else:
low += 1
nums[low] = pivot
print(low)
return low
def quickSort(nums):
arr = []
low = 0
high = len(nums) -1
if low < high:
mid = partition(nums,low,high)
if low < mid - 1:
arr.append(low)
arr.append(mid-1)
if mid+1 < high:
arr.append(mid+1)
arr.append(high)
while arr:
r = arr.pop()
l = arr.pop()
mid = partition(nums,l,r)
if l < mid -1:
arr.append(l)
arr.append(mid-1)
if mid + 1 < r:
arr.append(mid + 1)
arr.append(r)
print(nums)

思路二：算法导论里面的

def quick_sort_other(array, l, r):
'''
算法导论里的思想
i表示[l,i]都比pivot小
j依次遍历元素
'''
if l >= r:
return
stack = [l,r]
while stack:
low = stack.pop(0)
high = stack.pop(0)
if high <= low:
continue
pivot = array[high]
i = low - 1 ###初始值是-1
for j in range(low,high+1):
###如果小于pivot， 则交换，交换的目的是保证[l,i]都比pivot小
if array[j] <= pivot:
i += 1
t = array[i]
array[i] = array[j]
array[j] = t
stack.extend([low, i-1, i + 1, high])
return arrays

最后

以上就是搞怪眼睛为你收集整理的快速排序非递归实现--python的全部内容，希望文章能够帮你解决快速排序非递归实现--python所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。