计算机算法基础 第2版 课件 第4章 不基於比较的排序算法

第4章

不基於比较的排序算法1序言

2比较排序的复杂度下界

3不基於比较的线性时间排序算法

19计数排序

19基数排序

27桶排序

3121.序言可以证明，任何比较排序在最坏情况时需要至少lg(n!)

nlgn

次比较。要想有更快的排序算法，必须考虑不基於比较的排序。不基於比较的排序往往有额外的条件限制。主要討论：

计数排序

基数排序

桶排序32.比较排序的复杂度下界

决策树模型及最坏情况下界

很多问题的决策是对输入数据作一系列某个操作决定的。每次操作会有若干个可能的结果，而下次操作如何进行是根据这一次操作的结果而定，直到得到答案。这可用一个决策树来描述。任何基於比较的排序都是通过一系列数字间的比较来决定输入数据之间大小关系的，因此可以用一棵决策树来描述。证明排序问题的下界，我们只需考虑输入的n个数都不相等的情况。这是因为针对一个特殊情况的下界也一定是包含所有情况的下界。我们将证明，即使需要排序的n个数都不相等，任何基於比较的排序算法，在最坏情况时，都必须做至少

lg(n!)

nlgn次比较。

4例（图4.1）：一个把a1,a2,a3

排序的决策树有n个不同数的序列中，最小的数称为第1顺序数，第2小的数称为第2顺序数，…，第n个小的数(即最大的数)称为第n顺序数。排序就是确定在原序列中，那个是第1顺序数，那个是第2顺序数，…，那个是第n顺序数。所以，排序的本质是给出n个顺序数在原序列中的一个排列。(接下页)5决策树模型及最坏情况下界(继续)每个叶结点代表了一个从输入序列A[1]，A[2]，…，A[n]，到输出序列

B[1]<B[2]

<…

<B[n]的映射。如果B[j]=A[i]，那么，A[i]就是第j顺序数(1

i

n)。我们可以定义这个映射函数为：

(i)=j。比如，图4-1中叶结点(1,3,2)表示A[1]<A[3]<A[2]。这个映射函数是：

(1)=1，

(2)=3，

(3)=2。因为输入的n个数都不相等，它们只能有一个排序结果，所以一个叶结点只能代表一个映射。因为一个映射正好等于一个n个元素的全排列，所以有n!个不同的映射。因此，决策树必须至少有n!个叶子来代表这些不同的映射。如n个数不等，可证明排序决策树必须正好有n!个叶子（见书）。6定理4.1

任一个比较排序算法，在最坏情况时，需要至少

lg(n!)

次比较。证明：由上面讨论，任何比较排序算法所对应的决策树必须有n!个叶子。设这个决策树的高是h。因为高度为h的二叉树最多有2h个叶子，所以必有关系：2h

≥n!，也就是h

lg(n!)。因为h是整数，所以有

h

lg(n!)。这说明，有一个叶子的深度（depth）是h。那么，如果算法从树根开始，经过一系列比较操作后到达这个叶子时，算法必定作了h次比较。这是因为，算法要做一次比较才可以沿路径前进一步。所以，一个比较排序算法，在最坏情况时，需要至少h=

lg(n!)

次比较。

注:因

lg(n!)

nlgn，通常也说，比较排序的下界是nlgn。7下界应用举例例4.1

假设我们需要判定数组A[1..n]中的n个数是否有相同的数字，那么，在最坏情况时，任何基于比较的算法需要至少lg(n!)次比较。证明：

假设算法A是这样的一个算法。设输入的A[1..n]含n个不同数。

这些数可以排序为：b1

<b2<…<bn。我们不需真的去排序，但这个递增序列肯定存在。算法A必定会判定A[1..n]中没有相同的数字。我们断定:算法A一定比较了b1和b2。我们用反证法证明这点。假设算法A没有比较b1和b2，却判定A[1..n]没有相同的数字，那么我们把

b2改动一下，让b2等于b1，b2=b1，其余数不变。然后，把这改动后的数组A[1..n]再让这个算法A去判定。(接下页)8下界应用举例(证明继续)显然，这个改动不会改变任何两个数，bi和bj(1

i<j

n)的比较结果，除非i=1，j=2。因为前一次判定时，算法没有比较b1和b2，所以算法这一次会重复所有前一次的比较，也不会比较b1和

b2。那么，算法A必定察觉不到我们的改动，而仍然会判定数组中没有相同的数字。显然，这就错了。反证法成功。所以，算法A必定要比较b1和b2。同理，如果b3是第3小的数，那么这个算法必定要比较b2和b3。以此类推，这个算法必须比较序列中每两个相邻的数字。这就意味着，根据这个算法的比较结果，我们可以把这n个不同数字排序。因为基于比较的排序至少需要lg(n!)次比较，所以这个算法A也需要至少lg(n!)次比较。

9

10*二叉树的外路径总长与平均情况下界我们先讨论有Min-EPL的二叉树的特征。引理4.3 一棵有最小外路径总长的二叉树T必定是个完全二叉树(fullbinarytree)，即每个内结点正好有二个子结点。证明：反证法。如下图(4-2)，设树T的内结点x只有一个儿子y，我们把x的儿子和x的父亲相连后，删除x。得到的新二叉树T’有相同的叶结点集合而外路经总长减小，矛盾。引理得证。

11引理4.4 一棵有最小外路径总长(Min-EPL)的二叉树T中，所有叶结点必定只出现在最底两层。证明：反证法。由引理4.3，T是完全二叉树，设高为h。如下图，假设有叶子x在第k(k

h-2)层。把h-1层的点y的儿子a和b切下后接到x上。得到树T’与T有相等的叶子个数。下面计算证明T’有较小EPL(T’)。EPL(T’)=EPL(T)

|原(r,x)|

|原(r,a)|

|原(r,b)|+|新(r,y)|+|新(r,a)|+|新(r,b)|=EPL(T)–k–h–h+(h-1)+(k+1)+(k+1)=EPL(T)–h+k+1

EPL(T)–h+(h-2)+1=EPL(T)–1。这与T有Min-EPL矛盾，引理得证。

12引理4.5 假设一个有最小外路径总长的二叉树T有l个叶结点，那么EPL(T)>l(

lgl

1)。证明：设树高为h。由引理4.3和4.4，T是个完全二叉树并且所有叶子都在最底两层。设第(h-1)层的内结点个数为

x，那么必有1

x≤2h-1。

如图，第(h-1)层正好有2h-1–x个叶子，第h层正好有2x个叶子，总共有

l

=(2h-1–x)+2x

=2h-1

+x个叶子。因为2h-1

=l-x<

l≤2h，故有(h-1)<lgl≤h，即h=

lgl

。因为叶子的深度至少是(h-1)，所以EPL(T)>l(h-1)=

l(

lgl

1)。引理得证。

13定理4.6

任一比较排序平均需要至少

lg(n!)

-1次比较。证明：假设T是决策树。算法平均需要的比较次数，A(n)，等于它外路经总和除以叶结点个数。从引理4.5，A(n)=EPL(T)/l>(

lgl

1)。因为l

n!，所以A(n)>

lg(n!)

-1。

*二叉树的全路径总长与堆排序最好情况下界引理4.7 设

T是有n个结点的，有最小全路径总长的，二叉树，其高度是h。那么，除了第h-1层外，所有内结点必定有两个子结点。证明：反证法证。设第k(k≤h-2)层的一个内结点x只有一个儿子，如下图(4-5)。

(接下页)14注意：有最小全路径总长的二叉树不一定是完全二叉树。(b)

变换后的树T’与T有相同的结点总数(a)

树T中点x在第k层且只有一个儿子x

第k层,

k

h-2第h层(最底层)y

ba

rx

第k层第h层(最底层)y

ba

r证明（继续）：如下图，我们可切去底层一个叶结点a并把它连到x上。因为点a以外各点的深度不变而点a的深度减少，所以，变换后的树T’有较小的全路径总长，矛盾，引理4.7得证。

15引理4.8

有n个结点的堆所对应的二叉树有最小全路径总长(Min-TPL)。证明：设T是有n个结点的，有Min-TPL的二叉树，其高为h。

首先，T的所有叶子必须在最底二层。否则，如果叶子x在第k(k

h-2)层，我们可在底层切去一个叶子a，并把它连到x上。因为除点a以外各点的深度不变而点a的深度减少，变换后的树T’有较小的全路径总长，矛盾。其次，由引理4.7，除第h-1层外，所有其他内结点必须有两个子结点。所以，树T

与有n个结点的堆H，除底层外，完全一样。因此，树T和堆H有相同的高度

h=lgn,并且底层的叶结点数也必须相等。所以，有n个结点的堆H也是一个有Min-TPL的二叉树。

16定理4.9任一个有n个结点的二叉树T的全路径总长大于n(

lgn

-2)。证明：假设堆的高度是h，底层(第h层)有u个叶结点，1≤u≤2h。如下图(4-6)所示，从根到h-1层的顶点个数顺序为1，2，22，…，2h-1。

17定理4.10

如果A[1..n]中数字都不同，那么任何情况下堆排序Heapsort(A[1..n])需要的比较次数是

(nlgn)。证明：假定n是偶教，n=2k，这不影响复杂度。在建好堆之后，前k个数，A[1..k]是内结点，而后k个数A[k+1..n]是叶结点。

设中位数是x，则正好有k个数大於x。可证明：在排序开始前的堆中，至少有

k/3

个叶子(中数字)是小於等于x的。反证：如果不是，则最多有

k/3

-1个叶子是小於等于x的。那么，至少

2k/3

+1个叶子是大于x的。因为它们至少有

(2k/3+1)/2

≥

k/3

个父亲，而父亲们也是大于x的，那么，一共至少有

2k/3

+1+

k/3

>k

个结点中数大于x，矛盾。因为有

k/3

叶子是小於等于x的，故至少有

k/3

个内结点在开始时是大于x的。用S表示这些点的集合，|S|≥

k/3

=

n/6

。(接下页)18

193.不基於比较的线性时间排序算法

计数排序输入要求:数字是整数，并且有范围0≤a1,a2,…,an≤k，k=O(n)。如果不满足，设法把问题变换为一个满足该条件的问题。算法: 设输入是A[1..n]第1步，统计有多少数等于0，有多少数等于1，…，有多少数等于k。for

i

0to

k

C[i]

0 //

C[i]

记录整数i的个数，初始化为零。endfor for

i

0to

n

C[A[i]]

C[A[i]]+1 //如A[i]=j，整数j的个数加1。endfor第2步，

(见下页)。20计数排序(继续1)第2步，对数组C做累计统计，有多少数是0，有多少数是小于等于1的，有多少数是小于等于2的，等等，直到有多少数是小于等于k的。结果仍放在C中，C[0]不变。fori

1to

k

C[i]

C[i]+C[i-1] endfor例4.2

假设数组A[1..8]有如下8个整数：4,5,3,0,2,3,4,2。 笫1步后数组C为：

笫2步后数组C为：C[0]C[1]C[2]C[3]C[4]C[5]102221C[0]C[1]C[2]C[3]C[4]C[5]11357821计数排序(继续2)第3步，从A[n]到A[1]，逐个把A中数输出到B[1..n]使B[1..n]是排好序的。做法： forj

n

downto1

u

A[j] //A[j]=整数u

d

C[u] //当前数组B中还有d个小于等于u的数要安排

B[d]

A[j] //把A[j](=

u)放入B[d]中 C[u]

d-1 //修改C[u]为d-1endfor

理由：(a)

如果A[j]是从A[n]到A[1]中，第一个u。那么A[1..n]一共有d个小于等于u的数，而A[j]是最右边的一个。所以，B[1..d]必定是排好序的这d个数。B[d+1]以及之后的数必大于u。因为A[j]是最右边的一个u，所以应该把A[j]放入B[d]中，然后修改C[u]为d–1。22计数排序(继续3)如果A[j]不是从A[n]到A[1]中，第一个u。那么C[u]=d表明，除去那些之前已经安排好的等于u的数字外，包括A[j]在内，A[1..n]有d个小于等于u的数。它们必须被安放在B[1]至B[d]中。因为A[j]是这d个数中最右边的一个，所以应该把A[j]放入B[d]中。注意到，我们之前可能还看到过小于u的数，它们已被安排在B[1]至B[d-1]中某些地方，但它们不影响A[j]在序列中的位置是B[d]。同理，我们之前可能还看到过大于u的数，它们已被安排在B[d+1]之后的地方，也不影响A[j]在序列中的位置是B[d]。A[j]放入B[d]后，修改C[u]为d–1，指明下一个等于u的数在B中的位置。(如果还有等于u的数，否则不起作用。)下面看一个例子。23例将A[8]到A[1]中数字放入B[1..8]中，一共操作8次。第1步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[8]2C[0]C[1]C[2]C[3]C[4]C[5]113578C[0]C[1]C[2]C[3]C[4]C[5]更新后112578第2步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[7]24C[0]C[1]C[2]C[3]C[4]C[5]更新后112568A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]4530234224第3步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[6]234A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]453023C[0]C[1]C[2]C[3]C[4]C[5]更新后112468第4步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[5]2234C[0]C[1]C[2]C[3]C[4]C[5]更新后111468第5步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[4]02234C[0]C[1]C[2]C[3]C[4]C[5]更新后01146825A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]453第6步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[3]022334C[0]C[1]C[2]C[3]C[4]C[5]更新后011368第7步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[2]0223345C[0]C[1]C[2]C[3]C[4]C[5]更新后011367第8步B[1]B[2]B[3]B[4]B[5]B[6]B[7]B[8]A[1]02233445C[0]C[1]C[2]C[3]C[4]C[5]更新后01135726计数排序伪码Counting-Sort(A[1..n],B[1..n],k)for

i

0to

k

C[i]

0 //初始化数组C为全零endforfor

i

0to

n

C[A[i]]

C[A[i]]+1 //C[j]记录整数

j

的个数endforfori

1to

k

C[i]

C[i]+C[i-1] //C[i]记录小于等于i的个数endforforj

n

downto1

u

A[j]，

d

C[u]

B[d]

A[j]，

C[u]

d-1endforEnd

显然，计数排序复杂度是O(n)。27基数排序(Radixsort)要求：数字是由d位数组成的整数，每位取0，1，…,k中一个整数。k通常是一个常数，比如十进制数中每位可以取0到9中任一数。做法：从右向左，即从最低位到最高位，逐位排序。这n个数字被排序d次，每次取一位作为关键字来对前一次排序的结果重做一次排序。因为每一位的取值范围是[0..k]，可以用计数排序来完成。伪码见下页28基数排序的伪码Radix-Sort(A[1..n],d,k)for

i

1to

d

forj

1to

n

D[j]

ithdigitofA[j]//抽取A[j]中右起第i位数 endfor

Counting-Sort(D[1..n],B[1..n],k)//以D[1..n]为关键字排序

A[1..n]

B[1..n]endforEnd基数排序复杂度是O(d(n+k))。通常d和k都是常数，其复杂度是O(n)。29例4.3

基数排序例子24963170424945867363139567370493745893739524963163193745867370445867370439524939593730基数排序正确性证明：设a

和b是序列中任意两个数。假设a的d位数字，从高位到低位，是ad,ad-1,…,a2,a1，而b的d位数字是bd,bd-1,…,b2,b1。如果a

=b，因为计数排序是稳定排序，a和b的相对次序始终保持不变，所以基数排序是稳定排序。如果a<b，那么，一定会在某h位上使ah<bh。假定h是从左到右，第一个出现个不等式的位，即ad

=bd,a