算法导论第七章快速排序

快速排序的描述

简介

对于一个包含n个输入数的数组来说,快速排序是一种最坏情况下复杂度高达$Θ(n^2)$的排序算法,虽然最坏情况下复杂度很高,但平均性能很好,而且是通常情况下最优的排序算法,期望复杂度为$Θ(nlgn)$,且常数很小,而且算法可以进行原址排序,甚至在虚存中也表现良好.

描述

快速排序运用了分治思想,主要使用了以下三步主要内容.

1. 分解

数组$A[p..r]$被划分为两个(可能为空)子数组$A[p..q-1]$和$A[q+1..r]$，使得
$A[p..q—1]$中的每一个元素都小于等于$A[q]$，而$A[q]$也小于等于$A[q+1..r]$中的每个元素。

2.解决

通过递归调用快速排序,对$A[p..q-1]$和$A[q+1..r]$进行快速排序

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

当变量初始化时

$j = p,i = p-1,x=a[r]$
故$p>i$,条件1满足
$i+1>j-1$,条件2满足
显然,条件3满足

算法运行过程中

已有$A[i+1..j-1]>X$,当$A[j]>X$时,j++,因此继续满足$A[i+1..j-1]>X$
当$A[j]<=X$时,i++交换$A[i]$和$A[j]$,由上可知$A[i+1]>X$,故交换后$A[j]>X$,j++,故满足$A[i+1..j-1]>X$
当算法运行

终止

交换$A[i+1]$和$A[r],完成划分

快速排序的性能

快速排序的运行时间取决于划分是否平衡,划分平衡时,快速排序性能基本和归并排序一样,否则,性能接近于插入排序.

最坏情况划分

当划分后的两个子问题分别为n-1个元素和0个元素时,就出现了最坏情况.不妨假设每次排序都出现了最坏情况,划分操作的时间复杂度为$Θ(n)$
那么递归表达式为$T(n) = T(n-1)+Θ(n)$
解为$T(n)=Θ(n^2)$
.....未完待续