计算机算法基础 第2版 课件 第3章　基于比较的排序算法

第3

章

基于比较的排序算法1什么是基于比较的排序

2插入排序 3合并排序

7堆排序

15快排序

282什么是基于比较的排序排序是把输入的n个数，A[1],A[2],…,A[n]，重排为一个递增序列或递减序列。因为对称性，只考虑排序为递增序列，A[1]

A[2]

…

A[n]。基于比较是指，用比较输入数字之间大小的方法来决定它们的大小顺序。不允许用数字的其它结构性特征来帮助排序，例如数字A[i](1

i

n)有几位，每一位的数值是多少，等等。32. 插入排序

这是一个简单的用贪心法的算法。思路是：初始： 把一个数，A[1]，排好序，(不需操作)第1步： 把两个数，

A[1]，

A[2]，排好序，第2步： 把三个数，A[1]，A[2]，A[3]，排好序，……例如: (方框是下一步要插入的数)初始： 5 3 4 2 1第1步后:

3 5 4 1 2第2步后:

3 4 5 1 2第3步后: 1 3 4 5 2第4步后:

1 2 3 4 54插入排序伪码Insertion-sort(A[1..n])ifn=1 thenexitendiffor

k←2to

n

x←A[k] j←k–1 while

j>0and

A[j]>x A[j+1]←A[j] //A[j]比x

大，向后挪一位 j←j-1 endwhile //如果j=0，则有x<A[1] A[j+1]←x //把x插入到A[j+1]。如j=0，也正确

endfor End5

6插入排序的优缺点缺点：复杂度较高，后面会介绍

(nlgn)的算法。优点：算法简单，实现容易。是稳定(stable)排序，即序列中任意两个相等的数在排序后不改变它们的相对位置。是就地操作的算法，即只需要使用常数个除输入数据所占空间以外的存储单元。除数组A[1..n]以外，插入排序只需要指针k、指针j和临时工作单元x。7用分治法把序列一分为二递归地将两子序列排序用合并算法把排好序的两个子序列合并为一个单一序列先讨论合并算法，再讨论排序算法。假设A[1..n1]和B[1..n2]分别为两个递增序列,即 A[1]

A[2]

A[3]

…

A[n1] B[1]

B[2]

B[3]

…

B[n2]合并算法把它们合并为一个排好序的单一序列。

合并后的序列存入数组C[1..n1+n2]，并有： C[1]

C[2]

C[3]

…

C[n1+n2](伪码见下页)3. 合并排序8Merge(A[1..n1],B[1..n2],C[1..n1+n2])i

←

j

←k←1while

i

n1

and

j

n25

ifA[i]

B[j]6

then

C[k]←A[i]，i

←i+18 else

C[k]←B[j]，j

←j+110

endif11

k

←k+112 endwhileifi>n1 //说明序列A里的数已全部放入序列C中

then

C[k..n1+n2]←B[j..n2] //B中剰余数放入C中15

elseC[k..n1+n2]←A[i..n1]

//否则，A中剰余数放入C中16 endifEnd合并算法复杂度(最坏情况)：

T(n)=n–1=n1+

n2

–1次比较。9合并排序：Mergesort(A[p..r]) //如果p=r，则是底的情况，不需任何操作1 if

p<r2

then

mid

←

(p+r)/2

3

Mergesort(A[p..mid])4

Mergesort(A[mid

+1..r])5

Merge(A[p..mid],A[mid+1..r],C[p..r])6

A[p..r]←C[p..r])7 endifEnd//调用

Mergesort(A[1..n])后可排序A[1..n]显然，前面的合并算法Merge(A[1..n1],B[1..n2],C[1..n1+n2])需要稍加修改。主要是各数组两端的序号必须是变量，不能总是从1开始。但这种修改极为容易，不在此赘述了。当我们需要将数组A[1..n]排序时，只需调用Mergesort(A[1..n])即可。10二叉树表示合并排序合并排序的递归过程可以用一棵二叉树来表示。其划分的顺序是从根开始，自上而下，与树的前向遍历一致，而合并的顺序是从叶子(底)开始，自下而上，与树的后序遍历顺序一致。例子：A[1..8]A[1..4]A[5..8]A[1..2]A[3..4]A[5..6]A[7..8]9624153811合并排序复杂度最坏情况下，复杂度T(n)有递推关系： T(1)=0 T(n)=T(

n/2

)+T(

n/2

)+(n-1)

（3.1）定理3.1设T(n)为，最坏情况下，合并排序数组A[1..n](n>0)需要的数字之间的比较次数，那么，T(n)满足不等式

T(n)

n

lgn

–(n-1)。证明：我们用归纳法证明。归纳基础：由(3.1)式，直接验证n=1,2,3,4。T(1)=0

1

lg1

–(1-1)，T(2)=T(1)+T(1)+(2-1)=1

2

lg2

–(2-1)，T(3)=T(2)+T(1)+(3-1)=3

3

lg3

–(3-1)，T(4)=T(2)+T(2)+(4-1)=5

4

lg4

–(4-1)。

定理正确。归纳步骤:(接下页)12定理3.1(证明继续1)归纳步骤：假设当

n

=1,2,3,…,k-1(k

5)时，有T(n)

n

lgn

–(n-1)。下面证明，当n=k

时，仍然有T(n)

n

lgn

–(n-1)。我们注意到；

当k是偶数时，

lg

k/2

=

lg(k/2)

=

lgk-1

=

lgk

-1。当k是奇数时，

lg

k/2

=

lg((k+1)/2)

=

lg(k+1)-1

=

lg(k+1)

-1=

lgk

-1。 (因为k是奇数)所以，由归纳假设，我们有：T(

k/2

)

k/2

lg

k/2

–(

k/2

-1)

k/2

(

lgk

-1)–

k/2

+1 (3.2)T(

k/2

)

k/2

lg

k/2

–(

k/2

-1)

k/2

(

lgk

-1)–

k/2

+1 (3.3)(接下页)13定理3.1(证明继续2)把(3.2)式和(3.3)式代入到(3.1)式，我们得到：T(n)=T(k)=T(

k/2

)+T(

k/2

)+(k-1)

(

k/2

(

lgk

-1)–

k/2

+1)+(

k/2

(

lgk

-1)–

k/2

+1)+(k-1)=k(

lgk

-1)–k+2+(k-1)=k

lgk

–k+1=k

lgk

–(k-1)。

归纳成功。

由定理3.1知，T(n)=O(nlgn)。因为合并部分的最好情况需要至少min(n1,n2)=

n/2

次比较，所以有

T(n)

T(

n/2

)+T(

n/2

)+

n/2

。由主方法知，

T(n)

2T(

n/2

)+

n/2

=

(nlgn)。因此，合并排序的最好情况，最坏情况，以及平均情况的复杂度都是T(n)=

(nlgn)。14合并排序的优缺点优点：复杂度是最好的。在第4章中，我们会证明这一点。合并排序是个稳定排序。缺点：不是就地操作的算法，它需要使用

(n)个除数组A[1..n]外的存储单元。当n很大时，这是一个很大的开销。把数组C中元素再复制回数组A要消耗时间，相当于把基本操作的次数加倍。当n很大时，递归所需要用的堆栈也会增加开销。15堆(heap)的数据结构n个数字的最大堆是有n个结点(包括叶子)的二叉树并满足：每一个结点，包括叶结点，存有一个数。所有叶结点只出现在最底下二层，可证堆的高为h=lgn

。倒数第二层的所有内结点出现在所有叶结奌的左边。除最后一个内结点可有一个左儿子外，每个内结点必须有2个儿子。满足最大堆顺序：任一内结点v中的数大于等于其儿子结点中的数，从而也大于等于v为根的子树中所有结点的数。显然，可以类似定义最小堆，因对称性，我们只讨论最大堆。在最大堆中，根结点中的数最大。4. 堆排序堆的例子16堆可以用一数组实现，例如上面的堆可存放如下：如何找出A[i]的儿子和父亲？A[i]的左儿子

=

A[2i] (如果2i

>

n,

A[i]没有左儿子。)A[i]的右儿子

=A[2i+1] (如果2i+1>n,A[i]没有右儿子。)A[i]的父亲 =

A[

i/2

] (i>1,否则A[i]=A[1]是根。)17堆排序简介设A[1..n]是一个堆，A[1]是最大数。把A[1]和A[n]中的数交换后，最大数就放在了A[n]，这正是排序后放最大数的地方。然后，我们把A[n]从堆中切除，即把n减1。这样，剩下的n-1个数就在A[1..n-1]中了。A[1..n-1]不再是堆，但我们可以把它修复成一个堆。修复后，A[1]是下一个最大的数，把它与A[n-1]交换可把第二大数安排好。重复这样的过程直至所有数都安排好。堆修复算法我们假设，在需要修复的堆中，有一处，也仅有一处违反了堆顺序。也就是说，在某一个内结点A[i]中的数小于其某个儿子结点中的数值，而其余的所有内结点A[j](j

i)都保持着最大堆顺序，即A[j]中的数大于等于以A[j]为根的子树中所有结点含有的数字。18堆修复算法伪码：Max-Heapify(A[1..heap-size],i)l

←2i，r←2i+1

//左儿子的序号l，和右儿子的序号rif

l

heap-size

and

A[l]>A[i]

then

largest←l

elselargest←i //与左儿子比较谁大endififr

heap-size

and

A[r]>A[largest]

thenlargest←r //与右儿子比较谁大endififlargest

i

//如果A[i]比A[largest]小

thenA[i]

A[largest] //A[i]与该儿子交换

Max-Heapify([1..heap-size],largest) //递归修复该儿子这一点endifEnd堆修复算法例子19堆修复算法复杂度是2h=O(lgn)，因为最多递归h

次，每次做2次比较。20为输入数据建堆方法是先把数字任意放到数组

A[1..n]中，然后调整为一个堆。把A[i]为根的子树调整为一个堆的递归算法如下。Build-Max-Heap(A[1..n],i)1 l

2i

//l是左儿子的序号2 r

2i+1

//r是右儿子的序号3 if

l≤n

4

thenBuild-Max-Heap(A[1..n],

l) //递归为左子树建堆5 endif6 if

r≤n

7

then

Build-Max-Heap

(A[1..n],

r)

//递归为右子树建堆8 endifMax-Heapify(A[1..n],i) End调用Build-Max-Heap(A[1..n],

1)后，即可将A[1..n]变为一个堆。21输入数据建堆的复杂度置n=2h+1-1。这样A[1..n]所对应的二叉树是一棵高度为h的满二叉树(completebinarytree)，这里h=lg(n+1)–1。满二叉树的所有叶结点都在底层。例如：

22堆排序算法

将A[1..n]建堆后，堆排序算法如下：Heapsort(A[1..n])Build-Max-Heap(A[1..n],

1)2 Heap-size

n3 while

heap-size>14

A[1]

A[heap-size]5

heap-size

heap-size-16

Max-Heapify(A[1..heap-size]，1)7 endwhile8 End堆排序复杂度O(n)时间建堆。然后，循环(n-1)次，因为堆修复的时间是O(lgn),所以最坏情况复杂度是

T(n)=O(n)+(n-1)O(lgn)=O(nlgn)堆排序举例2324堆排序的优缺点优点：堆排序是个就地操作的算法。它的复杂度T(n)=

(nlgn)是渐近最优。缺点：堆排序的最大缺点是不稳定。读者可以很容易地找到不稳定的例子。最坏情况下，可证明，它需要至少2n-lg(n+1)次比较先构建一个堆。而且，它的排序部分还需要约2nlgn次比较。所以，最坏情况时，比合并排序的

n

lgn

-(n-1)比较次数(定理3.1)要多将近一倍以上。25堆用作优先队列堆还可用来动态地管理和修改数据，比如插入一个数，刪除一个数，减少(或增加)一个数，找到最大(或最小)的数等。提供这些操作的数据结构都称为优先队列(Priorityqueue)。1. 增加堆中A[i]的值为新值keyHeap-Increase-Key(A[1..n]，i，key)1 ifkey<A[i]2

thenerror //要增加的值比原来值还小，不合理3 endif4 A[i]

key，father(i)

i/2

while

i>1and

A[father(i)]<A[i]

A[i]

A[father(i)]，i

father(i) father(i)

i/2

8 endwhile9 End

这个算法复杂度为O(lgn)。262. 插入一个数keyMax-Heap-Insert(A[1..heap-size],key)1 heap-size

heap-size

+12 n

heap-size3 A[n]

-

4 Heap-Increase-Key(A[1..n],n,key)End

//这个算法复杂度为O(lgn)。3. 取走最大数并放入变量max当中

Heap-Extract-Max(A[1..heap-size]，max)1 n

heap-size2 if

n<13

thenreturn“error,heapunderflow”4 endif(接下页)273. 最大数放入变量max当中

(继续)max

A[1]A[1]

A[n]heap-size[A]

n–18 Max-Heapify(A[1..heap-size]，1)9 return

max10 End //这个算法复杂度为O(lgn)将最大数复制到变量max当中(不删除最大数)Heap-Maximum(A[1..heap-size],max)1 if

heap-size<12 thenreturnerror“heapunderflow” //堆是个空集3 endif4 max

A[1]5 returnmax6 End //这个算法复杂度为O(1)5.

快排序28快排序用分治法序列含1个数或没有数时是底，此时不需任何操作。取序列A[p..r]中一个数，例如A[r]，作为中心点。文献中有各种取法，都差不多，本书取A[r]作为中心点。

把序列中数，从A[p]到A[r-1]，逐个与中心点比较，小于等于A[r]的数放左边，大于A[r]的数放右边。最后，A[r]放中间。 左边任何数≤A[r]<右边任何数。递归地快排序左、右两部分。划分A[p..r]为二的算法指针j指向下一个要检查的数，初始值为p，即指向A[p]。指针i指向当前左边部分中最后一个数，初始值为p-1。29划分算法每步的具体操作：每次我们比较A[j]和A[r]时，有两种结果，分述如下：

如果A[j]>A[r]，A[j]中数字属于第二部分，只需指针j加1。如果

A[j]≤A[r]，A[j]中数字属于第一部分。把A[j]和A[i+1]中数字交换后可把A[j]中的数字并入第一部分。这时需把指针i和j分别加1。当A[1..r-1]中每个数都和A[r]比较后，交换A[i+1]和A[r]中数字。这样就把A[r]中数放在了中心点位置上。显然，中心点位置是q

=i+1。30划分算法伪码：Partition(A[p..r],q)1 x

A[r]2 i

p-13 for

j

ptor-1 //每次操作后，for循环会把j加14 ifA[j]

x//如A[j]>x，不需任何操作，i不变5 then

i

i+16

A[i]

A[j]7

endif

8 endfor9 A[i

+1]

A[r] 10 q

i+1 //中心点在A[i+1]11 returnq12 End

划分算法需要n-1次比较，是就地操作。这里，n=r-p+1。31I=p-1J=pr初始状态28713564ij一次比较后28713564ij2次比较后28713564ij3次比较后28713564ij4次比较后21783564ij5次比较后21387564ij6次比较后21387564ij7次比较后21387564把A[r]放到中21347568心点后q划分算法举例32快排序算法伪码Quicksort(A[p..r]) 1 ifp<r //如果p

r，则见底2

then Partition(A[p..r],q)3

Quicksort(A[p..q-1])4

Quicksort(A[q+1..r])5 endif6 End

如果要把A[1..n]排序的话，只需调用Quicksort(A[1..n])。快排序最坏情况复杂度定理3.2

给定序列A[p..r]，快排序Quicksort(A[p..r])需要最多n(n-1)/2次比较，这里n为数组中元素的个数，即n=p-r+1。(证明见下页)33

34

35

36*快排序算法最好情况复杂度定理3.4

给定序列A[p..r]，快排序Quicksort(A[p..r])需要最少

(n+1)lg(n+1)

–2n次比较，这里n=p-r+1

为数组中元素的个数。证明：

对n进行归纳证明。归纳基础：n

=0时，T(0)=0,

(0+1)lg(0+1)

–2

0=0，定理正确。n

=1时，T(1)=0,

(1+1)lg(1+1)

–2

1=