算法导论第七章--快速排序

快速排序的描述

简介

对于一个包含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$
当算法运行