python快速排序递归与⾮递归
快速排序递归与⾮递归python
写在前⾯
众所周知，快速排序相对于选择排序，插⼊排序，冒泡排序等初级排序有着天然的优势。这是因为快排在交换元素的过程中，两个发⽣交换的元素，距离较远。⽐如插⼊排序，新的元素要在已经有序的序列中，⼀次⼜⼀次地到它应该处于的位置，交换的次数远远⾼于快排。但是，使⽤快排时，要特别的⼩⼼，尤其是它的边界条件设置，还有就是重复元素⽐较多的情况。
快速排序的递归函数
这⾥我们使⽤快排的最常见的递归函数，这⾥要注意⼀下，要先写退出递归的条件，⼀些⼩细节还是要注意⼀下的。
def QuickSort(lo,hi):
if lo >= hi:
return
j = partition(lo,hi)
QuickSort(lo,j-1)
QuickSort(j+1,hi)
快排的切分函数
切分函数很重要，是快速排序的精髓。以下是python实现。
由于python⾥没有java,C++中a[++i]这种骚操作，因此不能照着Algorithm那本书那么写，要稍微做⼀些改动，其实主要就是边界条件。特殊情况下，如果切分元素是数组中最⼤或者最⼩的那个元素，就要⼩⼼别让扫描指针跑出数组的边界。实际上，第⼆个内循环边界条件（j>lo）是多余的，因为j递减到lo+1，若继续进⼊循环，再减到lo时，已经不满⾜进⼊循环的条件了，此时a[j]=v，循环⾃动退出，因此这个边界条件冗余。这都是在后期发现的，刚开始学习的话以防万⼀可以加上，熟练之后就可以去掉了。Algorithm中的java实现请点击
def partition(lo,hi):
i = lo+1
j = hi
v = a[lo]
while1:
while(i<hi)and(a[i]<=v):#使⽤i++必须要及时使⽤哨兵，使⽤<=跳过重复元素，防⽌重复元素之间交换形成死循环
i +=1
while(j>lo)and(a[j]>v):
j -=1
if i >= j:
break
a[i],a[j]= a[j],a[i]
a[lo],a[j]=a[j],a[lo]
return j
快速排序python实现快排的⾮递归函数
这⾥⼿动维护⼀个下压栈来存储待排序数组的切分指针以及头尾指针
def QuickSort(lo,hi):
stack =[]
stack.insert(0,lo)#头指针⼊栈
stack.insert(0,hi)#尾指针⼊栈
while(len(stack)!=0):#若栈不为空
hi= stack.pop(0)#头指针出栈
lo = stack.pop(0)#尾指针出栈
j = partition(lo,hi)#当返回切分指针，发现⼦数组长度为1，则⽆法⼊栈if lo<j-1:
stack.insert(0,lo)
stack.insert(0,j-1)
elif j+1<hi:
stack.insert(0,j+1)
stack.insert(0,hi)
以下是⾮递归的⼊栈出栈图
图1中lo和hi指针⼊栈，然后出栈
图2中切分指针两边的左右⼦数组分别⼊栈，然后释放右⼦数组的头尾指针
图3中接着⼊栈4个指针，j’是下⼀次切分的指针。持续的出栈，⼊栈过程，意味着右⼦数组不断细化，不断被切⼩，⽽切分指针不断⼊栈。当⼦数组长度为1时，栈容纳的指针数量达到了最⼤，partition函数返回的切分指针j已经不能⼊栈了，所以下压栈开始了释放过程，⼀旦⼦数组长度不是1，那么意味着还有切分指针⼊栈的余地，于是切分指针继续⼊栈。不断重复这个过程。
完整的源代码
import random
import datetime
#切分函数
def partition(lo,hi):
i = lo+1
j = hi
v = a[lo]
while1:
while(i<hi)and(a[i]<=v):#使⽤i++必须要及时使⽤哨兵，使⽤<=跳过重复元素，防⽌重复元素之间交换形成死循环
i +=1
while(j>lo)and(a[j]>=v):
j -=1
if i >= j:
break
a[i],a[j]= a[j],a[i]
a[lo],a[j]=a[j],a[lo]
return j
#递归
def QuickSort(lo,hi):
if lo >= hi:
return
j = partition(lo,hi)
QuickSort(lo,j-1)
QuickSort(j+1,hi)
#⾮递归
def QuickSort(lo,hi):
stack =[]
stack.insert(0,lo)#头指针⼊栈
stack.insert(0,hi)#尾指针⼊栈
while(len(stack)!=0):#若栈不为空
hi= stack.pop(0)#头指针出栈
lo = stack.pop(0)#尾指针出栈
j = partition(lo,hi)#当返回切分指针，发现⼦数组长度为1，则⽆法⼊栈
if lo<j-1:
stack.insert(0,lo)
stack.insert(0,j-1)
elif j+1<hi:
stack.insert(0,j+1)
stack.insert(0,hi)
if __name__ =='__main__':
a =[]
#    random.seed(12345)
for i in range(10):
a.append(random.randint(0,10))
random.shuffle(a)
lo =0
hi =len(a)-1
print(a)
time1 = w()
QuickSort(lo,hi)
time2 = w()
duration = time2-time1
print(duration)
print(a)
快排很容易出错，在单元测试的时候，⼤家不妨⽤random函数多试⼏次，来验证⾃⼰写的快排是否正确，尤其是切分元素在数组中还有重复的元素，以及⼀些边界条件，有没有等于之类的情况

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。