快排笔记：递归和非递归快排实现

84 阅读 0 评论 56 点赞

我是靠谱客的博主谨慎外套，最近开发中收集的这篇文章主要介绍快排笔记：递归和非递归快排实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

快排笔记：递归和非递归快排实现

快速排序和归并排序一样，也是基于分治思想，通过递归地调用快速排序实现数组的排序。

递归快排

快排的基本思路就是在待排序的数组A[1,…n]中选择一个数m（一般选择A[n]）,通过和数组中其他数比较（通过移动数组元素将大于m的数放在m的后面）确定m在这个数组中的位置p，并得到两个子数组A[1,…p-1]（小于等于m）和A[p+1,n]（大于m）（注：子数组可以为空数组）。然后，递归地对两个子数组进行上述操作，最后当数组中所有的元素都确定在数组中的位置时，排序完成。
代码可以写成：

def quickSort(A,start,end):
'''
数组为空（end < start）
数组长度为1（end == start）
表明数组已经是有序的了，就直接返回
'''
if start<end:
# 找到m的位置pos，并且移动数组元素
pos = findPos(A,start,end)
# 递归地对两个子数组执行quickSort()
quickSort(A,start,pos-1)
quickSort(A,pos+1,end)

递归算法具体python代码：

def reQuickSort(nums,start = 0,end = -1):
if end == -1:
end = len(nums)-1
#递归结束判断
if start >= end:
return
#找到nums[end]的应在的位置，并且移动数组
i = start
j = end
while i<j:
if nums[i]>nums[j]:
nums[i],nums[j-1],nums[j] = nums[j-1],nums[j],nums[i]
j-=1
else:
i+=1
#递归调用quickSort()
reQuickSort(nums,start,i-1)
reQuickSort(nums,i+1,end)

但是通过递归实现的快排在输入个数 n 较大时（如n>1000000）或者数组有序时，可能会出现栈溢出。这个通过非递归快排解决。

非递归快排

非递归的思路是：

通过两个栈 startStack 和 endStack 来记录需要排序的子数组的起始下表start和终止下表end。
初始化两个栈，向startStack中push 0，向endStack中push len(nums)-1.
while循环，终止条件为两个栈为空（排序完成）
在循环中从两个栈中pop出这次循环的start和end，如果start>=end continue循环, 否则完成findPos(A,start,end) 操作后得到两个待处理的子数组，将两个数组的start和end push进栈。

非递归算法具体python代码：

def quickSort(nums):
#初始化两个栈
startStack = [0,]
endStack = [len(nums)-1,]
#进入循环，两个栈均为空时，排序结束
while startStack and endStack:
#得到本次循环的start 和 end
start = startStack.pop()
end = endStack.pop()
#判断子数组是否有序
if start>end:
continue
i = start
j = end
while i<j:
if nums[i]>nums[j]:
nums[i],nums[j-1],nums[j] = nums[j-1],nums[j],nums[i]
j-=1
else:
i+=1
#将两个子数组的开始和结尾push进栈中
startStack.append(start)
endStack.append(i-1)
startStack.append(i+1)
endStack.append(end)