迭代快速排序的 Python 程序
pythonserver side programmingprogramming更新于 2024/1/22 23:11:00
在本文中，我们将了解下面给出的问题陈述的解决方案。
问题陈述− 我们有一个数组，我们需要使用迭代方式的快速排序概念对其进行排序
在这里，我们首先对数组进行分区，然后对单独的分区进行排序以获得排序后的数组。
现在让我们观察下面实现中的解决方案−
示例
# 迭代方式
def partion(arr,l,h):
i = ( l - 1 )
x = arr[h]
for j in range(l , h):
if arr[j] <= x:
# 增量
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[h] = arr[h],arr[i+1]
return (i+1)
# 排序
def quickSortIterative(arr,l,h):
# 创建堆栈
size = h - l + 1
stack = [0] * (size)
# 初始化
top = -1
# 推送初始值
top = top + 1
stack[top] = l
top = top + 1
stack[top] = h
# 从堆栈弹出
while top >= 0:
# 弹出
h = stack[top]
top = top - 1
l = stack[top]
top = top - 1
# 将枢轴元素设置在正确位置
p = partion( arr, l, h )
# 左侧元素
if p-1 > l:
top = top + 1
stack[top] = l
top = top + 1
stack[top] = p - 1
# 右侧元素
if p+1 < h:
top = top + 1
stack[top] = p + 1
top = top + 1
stack[top] = h
# main
arr = [2,5,3,8,6,5,4,7]
n = len(arr)
quickSortIterative(arr, 0, n-1)
print ("Sorted array is:")
for i in range(n):
print (arr[i],end=" ")
输出
Sorted array is 2 3 4 5 5 6 7 8
所有变量均在本地范围内声明，其引用如上图所示。
结论
在本文中，我们了解了如何编写用于迭代快速排序的 Python 程序。
