快速排序的描述
简介
对于一个包含n个输入数的数组来说,快速排序是一种最坏情况下复杂度高达的排序算法,虽然最坏情况下复杂度很高,但平均性能很好,而且是通常情况下最优的排序算法,期望复杂度为
,且常数很小,而且算法可以进行原址排序,甚至在虚存中也表现良好.
描述
快速排序运用了分治思想,主要使用了以下三步主要内容.
1. 分解
数组被划分为两个(可能为空)子数组
和
，使得
中的每一个元素都小于等于
，而
也小于等于
中的每个元素。
2.解决
通过递归调用快速排序,对和
进行快速排序
3.合并
因为子数组都是原址操作,所以不需要合并,分解后自然有序
数组的划分
python描述
def partition(A,p,r):#为数组A[p..r]
x = A[r]#选末尾为pivot
i = p-1
for j in range(p,r):
if A[j]<=x:
i+=1#将i的区域向后延申,并于j交换
A[i],A[j] = A[j],A[i]
A[i+1],A[r] = A[r],A[i+1]
划分实例
证明
即数组永远满足以下三个条件
- A[p...i]中的数据≤X
- A[i+1..j-1]中的数据＞X
- A[r]=x
当变量初始化时
故,条件1满足
,条件2满足
显然,条件3满足
算法运行过程中
已有,当
时,j++,因此继续满足
当时,i++交换
和
,由上可知
,故交换后
,j++,故满足
当算法运行
终止
交换和$A[r],完成划分
快速排序的性能
快速排序的运行时间取决于划分是否平衡,划分平衡时,快速排序性能基本和归并排序一样,否则,性能接近于插入排序.
最坏情况划分
当划分后的两个子问题分别为n-1个元素和0个元素时,就出现了最坏情况.不妨假设每次排序都出现了最坏情况,划分操作的时间复杂度为
那么递归表达式为
解为
.....未完待续
