算法导论第八章思考题

8-1(比较排序的概率下界) 在这一问题中，我们将证明对于给定的n个互异的输入元素，任何确定或随机的比较排序算法，其概率运行时间都有下界Ω(nlgn)。首先分析一个确定的比较排序算法A，其决策树为Ta，假设A的输入的每一种排列情况都是等可能的。

a) 假设Ta的每个叶子结点都标有在给定的随机输入情况下到达该结点的概率。证明：恰有n!个叶子结点标有1/n!，其他的叶结点标记为0.

因为对于n个元素有n!种可能数组元素排列，那么由此对应于决策树的n!个叶子结点，对于n!个叶子结点中的每一个叶子结点对应一种排序情况，因为假设每一种排列情况都是等可能的，所以到达每一个叶子结点的概率1/n!，对于决策树来说，我们只考虑这n!个叶子结点。其他叶子结点不属于这n!种排序情况，所以随机输入排序情况到达该结点的概率是0.

b)定义D(T)表示一颗决策树T的外部路径长度，即D(T)是T的所有叶结点深度的和，假设T为一颗有k>1个叶结点的决策树，LT和RT分别是T的左子树和右子树。证明：D(T)=D(LT)+D(RT)+k.

c)定义d(k)为所有具有k>1叶结点的决策树T的最小D(T)值。证明：d(k)=min{d(i)+d(k-i)+k}.

d)证明：d对于给定的k(k>1)和i(1<i<k-1),函数ilgi+(k-i)lg(k-i)在i=k/2处取得最小值，并有结论d(k)=Ω(klgk).

e)证明：D(Ta)=Ωm(n!lgn!),并得出在平均情况下，排序n个元素的时间代价Ω(nlgn)

f) 不太懂。

8-2 (线性时间原址排序) 假设有一个包含n个待排序数据记录的数组，且每条记录的关键字的值为0或1，对这样一组记录进行排序的算法可能具备如下三种特性中的一部分。

1,算法的时间代价是O(n).

2,算法是稳定的。

3,算法是原址排序，除了输入数组之外，算法只需要固定的额外存储空间。

a,给出满足1和2的算法

计数排序

b,给出满足1和3的算法

既然n个数只有0和1两种值，那么可以按照我设计的算法，满足线性时间，不需要辅助空间，但是不稳定。

[cpp] view plaincopy

1. #include <iostream>  
2. #include <time.h>  
3. using namespace std;  
4. void _8_2_b(int A[],int n)  
5. {  
6.    int k=0;  
7.    for (int i=0;i<n;i++)  
8.    {  
9.       if (A[i]==0)  
10.       {  
11.           k++;  
12.       }  
13.    }  
14.    for (int j=0;j<n;j++)  
15.    {  
16.        if (j<=k)  
17.        {  
18.            A[j]=0;  
19.        }  
20.        else   
21.        {  
22.            A[j]=1;  
23.        }  
24.     }  
25. }  
26. void main()  
27. {  
28.     const n=100;  
29.     int A[n]={0};  
30.     srand( (unsigned)time( NULL ) );  
31.     for (int i=0;i<n;i++)  
32.     {  
33.         A[i]=rand()%2;  
34.     }  
35.     _8_2_b(A,n);  
36.     for ( i=0;i<n;i++)  
37.     {  
38.         cout<<A[i]<<" ";  
39.     }  
40. }  

c,给出满足2和3的算法

插入排序

d 你设计的算法a-c中的任一个是否可以用于RADIX-SORT的第2行作为基础排序方法，从而使RADIX-SORT在排序有b位关键字的n条记录时的时间代价是O(bn)?如果可以，请解释应如何处理，如果不行，请说明原因。

(a)可以。用计数排序作为基数排序的子程序即可。
(b)不可以。我设计的这个程序，只是在特定情况下可以排序，不具备普遍性。
(c)不可以。插入排序属于比较排序算法，所以其时间下界是Ω(nlgn)。没有达到O(bn).

e.假设有n条记录，其中所有关键字的值都在1到k的区间内，你应该如何修改计数排序，使得它可以在O(n+k)时间内完成对n条记录的原址排序。除输入数组外，你可以O(k)使用大小的额外存储空间。你给出的算法是稳定的吗？

不稳定。以下是具体算法：

[cpp] view plaincopy

1. //此算法也是对计数排序的一种改进，这里有以下3点改进。  
2. //1.只需要计算等于A[i]的元素，不用添加循环用来计算小于A[i]的元素  
3. //2.同时也不用添加辅助数组B来对数组A进行输出，只需要在原来的A数组上进行排序就可以了。  
4. //3.对于含有重复数据的数组进行排序时，用于存放数据出现次数的数组C的长度是刨去重复数据的最小值k，但是对于重复数据的处理是不稳定的。  
5. //但是我还在思考这个排序是否是原址的计数排序？懂的请留言和我交流下哦，谢谢！  
6. #include <iostream>  
7. #include <time.h>  
8. using namespace std;  
9. const n=20;  
10. void COUNTING_SORT(int A[n])  
11. {  
12.     int max=A[0],min=A[0];  
13.     for (int i=0;i<n;i++)  
14.     {  
15.         if (A[i]>max)  
16.         {  
17.             max=A[i];  
18.         }  
19.         if (A[i]<min)  
20.         {  
21.             min=A[i];  
22.         }  
23.     }  
24.     int k=max-min+1;     
25.     int *C=new int[k+1];  
26.     for ( i=0;i<=k;i++)  
27.     {  
28.         C[i]=0;  
29.     }  
30.     for (int j=0;j<n;j++)  
31.     {  
32.         C[A[j]-min+1]++;  
33.     }  
34.     for (j=n-1;j>=0;)  
35.     {  
36.         k=max-min+1;  
37.         if(C[k]!=0)  
38.         {  
39.           A[j]=max;  
40.           C[k]--;j--;  
41.         }  
42.         else   
43.         {  
44.             max--;  
45.         }  
46.     }  
47. }  
48. void main()  
49. {  
50.     int A[n]={0};  
51.     srand( (unsigned)time( NULL ) );  
52.     for (int i=0;i<n;i++)  
53.     {  
54.         A[i]=rand()%100;  
55.     }  
56.     COUNTING_SORT(A);  
57.     for (int j=0;j<n;j++)  
58.     {  
59.         cout<<A[j]<<" ";  
60.     }     
61. }  

8-3 (变长数据项的排序)

a.给定一个整数数组，其中不同的整数所包含的的数字的位数可能不同，但该数组中，所有整数中包含的总数字位数为n.设计一个算法，使其可以在O(n)时间内对该数组进行排序。

[cpp] view plaincopy

1. #include <iostream>  
2. #include <time.h>  
3. using namespace std;  
4. const n=15,m=4;//n代表元素个数最大值m代表位数最大值   
5. int Max(int B[n][m],int h)//O(n)  
6. {//求最大k值  
7.     int k=0;  
8.     for (int i=0;i<n;i++)//O(n)  
9.     {  
10.         if (B[i][h]>k)  
11.         {  
12.             k=B[i][h];  
13.         }  
14.     }  
15.     return k;  
16. }  
17. void COUNTING_SORT(int B[n][m],int C[n],int k,int h)//O(k)+O(n)+O(k)+O(n)=O(n+k)  
18. {//计数排序  
19.       
20.     int *D=new int[k+1];  
21.     for (int i=0;i<=k;i++)//O(k)  
22.     {  
23.         D[i]=0;  
24.     }  
25.     for (int j=0;j<n;j++)//O(n)  
26.     {  
27.         D[B[j][h]]=D[B[j][h]]+1;  
28.     }  
29.     for (i=0;i<=k;i++)//O(k)  
30.     {  
31.         D[i+1]=D[i+1]+D[i];  
32.     }  
33.     for (j=n-1;j>=0;j--)//O(n)  
34.     {  
35.         C[D[B[j][h]]-1]=j;  
36.         D[B[j][h]]=D[B[j][h]]-1;  
37.     }  
38. }  
39. void Converted_to_Decimal(int E[],int B[][m],int i,int k)//O(d)+O(d)=O(d)  
40. {//此函数是将十进制数以2维数组B的形式存放。  
41.     int x=E[i];  
42.     for (int j=0;x>0;j++ )//O(di)循环了di次 di为当前数的位数  
43.     {  
44.         B[i][j]=x%10;  
45.         x=x/10;  
46.     }  
47.     if (j<=k+1&&k+1!=m)  
48.     {  
49.         /*for (int k=j;k<m;k++)//O(d) 循环了d-j次 高位补0 
50.         { 
51.             B[i][k]=0; 
52.         }*/  
53.         B[i][k+1]=0;//如果A[i]位数小于将要COUNTING_SORT函数排序的那一位，那么将该位重置为0  
54.                     //相比以前需要循环置0，现在只需要一个常数时间内就可以达到原来的目的。  
55.     }  
56. }  
57. void Radix_sort(int A[n],int B[][m],int C[n],int E[n],int d)  
58. {  
59.     d=m;int k=0;  
60.     for ( int i=0;i<n;i++)//O(∑di)=O(n1) n1为总的位数。  
61.     {  
62.         Converted_to_Decimal(A,B,i,k);//O(di)    
63.     }  
64.     for ( int j=0;j<d;j++)//O(d) d为位数  
65.     {//因为d<=d位数的最小值<=k,(例如3<3位数最小值100)所以d<=n+k,内层循环O(n)+O(n+k)+O(n)+O(n)+O(d)+O(n)=O(n+k)  
66.         cout<<endl;  
67.         int k=Max(B,j);//O(n)  
68.         COUNTING_SORT(B,C,k,j);//O(n+k)  
69.         for ( i=0;i<n;i++)//O(n)  
70.         {  
71.             E[i]=A[C[i]];  
72.         }  
73.         /*if (j==d-1)//当循环到最高位时，直接跳出循环。不进行下面的循环，这样缩短运行时间。 
74.         { 
75.             break; 
76.         }*/  
77.         for ( i=0;i<n;i++)//O(n)  
78.         {  
79.             Converted_to_Decimal(E,B,i,j);//O(n1)因为这n个数最低是1位数，所以n个1位数<=总位数和n1 O(n)=O(n1)  
80.         }  
81.         for (i=0;i<n;i++)//O(n)  
82.         {  
83.             A[i]=E[i];  
84.         }  
85.     }//所以Radix_sort时间复杂度为O(d(n+k))  
86.     //O(n1d)+O(d(n1+k))=O(d(n1+k)) 当d为常数且k=O(n)时，时间复杂度为线性时间O(n1)  
87. }  
88. void main()  
89. {  
90.     srand( (unsigned)time( NULL ) );  
91.     int A[n]={0};  
92.     for (int i=0;i<n;i++)  
93.     {  
94.         A[i]=rand()%10000;  
95.     }  
96.     //int A[n]={1,45,23,8,120,78,9,4,25,200,9,10,34,58,78};  
97.     int C[n]={0},E[n]={0},B[n][m]={0};  
98.     Radix_sort(A,B,C,E,m);  
99.     for ( i=0;i<n;i++)  
100.     {  
101.         cout<<A[i]<<" ";  
102.     }    
103. }  

每次调用Converted_to_Decimal函数都循环了di次，di是数组第i个数的位数。在Radix_sort函数里面，调用了n次Converted_to_Decimal函数，那么这样O(∑di)=O(n1) n1为总的位数。对于基数排序，需要对数组最大位数d循环d次才可以将整个数组好序，每循环一次就要调用n次Converted_to_Decimal函数其运行时间为O(n1) ，那么循环d次，就是O(dn1),进行基数排序和计数排序还需要满足两个前提条件才可以使程序运行呈现线性时间，第1点是最大整数k=O(n),第2点d应该是常数，这样 O(dn1)=O(n1)

b.给定一个字符串数组，其中不同的字符串所包含的字符数可能不同，但所有字符串中的总字符个数为n。设计一个算法，使其可以在O(n)时间内该数组进行排序。

[cpp] view plaincopy

1.  #include <iostream>    
2. using namespace std;   
3. const len=10,bit=5,n=26;  
4. void Bubble_sort(char B[n][len][bit],int m);//首字母为B[n],比如B[0][len][bit]='A'  
5. void BucketSort(char arr[len][bit],char B[n][len][bit]);  
6. int my_strcmp(char *p1, char *p2);  
7. void main()  
8. {  
9.     char arr[len][bit]={"aBc","cdE","Aa","CCFC","X","Bc","SDkF","BvX","CCEF","QW"};  
10.     char B[n][len][bit]={0};  
11.     BucketSort(arr,B);  
12.     for (int i=0;i<len;i++)  
13.     {  
14.         for (int j=0;j<bit;j++)  
15.         {  
16.             if ((arr[i][j]>='A'&&arr[i][j]<='Z')||(arr[i][j]>='a'&&arr[i][j]<='z'))  
17.             {  
18.                 cout<<arr[i][j];  
19.             }  
20.         }  
21.         cout<<" ";  
22.     }  
23. }  
24. void BucketSort(char arr[len][bit],char B[n][len][bit])  
25. {  
26.     int t=0,k=0,A[n]={0};  
27.     for (int i=0;i<len;i++)//len代表字符串元素个数n1   
28.     {//这个循环 O(len*bit)=O(n1*k)   
29.         if (arr[i][0]<='z'&&arr[i][0]>='a')  
30.         {  
31.             t=arr[i][0]-'a';  
32.         }  
33.         else if(arr[i][0]<='Z'&&arr[i][0]>='A')  
34.         {  
35.             t=arr[i][0]-'A';  
36.         }  
37.         k=A[t];  
38.         for (int j=0;j<bit;j++)//bit代表字符串长度k  
39.         {  
40.             B[t][A[t]][j]=arr[i][j];            
41.         }  
42.         A[t]++;           
43.     }  
44.     for (int j=0;j<n;j++)//O(n*len*bit)n代表26个字母，肯定是常数c，len代表元素个数n1,bit代表位数也就是字符串长度k  
45.     {//O(ckn1) c是常数，我们假设字符串长度k也为常数，那么O(ckn1)=O(n1)就是线性时间了。字符串个数n1<=字符串总的字符数n，所以O(n1)=O(n)  
46.         Bubble_sort(B,j);//O(len*bit) 冒泡排序法的时间复杂度O(nj^2)  
47.     }  
48.     i=0;  
49.     for (int a=0;a<n;a++)//这个循环分析同上  
50.     {  
51.         for (int b=0;b<len;b++)  
52.         {  
53.             if (B[a][b][0]!='\0'&&i!=len)  
54.             {  
55.                 for (int c=0;c<bit;c++)  
56.                 {  
57.                     arr[i][c]=B[a][b][c];   
58.                 }  
59.                 i++;  
60.             }  
61.         }  
62.     }  
63. }  
64. void Bubble_sort(char B[n][len][bit],int m)//首字母为B[n],比如B[0][len][bit]='A'    
65. {     
66.     for (int j=0;B[m][j][0]!='\0';j++)//O(len)     
67.     {     
68.         for (int i=j+1;B[m][i][0]!='\0';i++)  
69.         {  
70.             if(my_strcmp(B[m][i],B[m][j])<0)  
71.             {  
72.                 char temp[100];  
73.                 strcpy(temp,B[m][i]);  
74.                 strcpy(B[m][i],B[m][j]);  
75.                 strcpy(B[m][j],temp );   
76.             }  
77.         }   
78.          
79.     }   
80. }  
81. int my_strcmp(char *p1, char *p2)  
82. {  
83.     int result = 0;  
84.     while (*p1 && *p2)  
85.     {  
86.         if ((*p1<='z'&&*p1>='a')&&(*p2<='z'&&*p2>='a'))  
87.         {//先判断p1与p2是否都是小写？  
88.             *p2-=32;*p1-=32;//小写转化成大写。  
89.             if (*p1 == *p2)  
90.             {  
91.                 *p2+=32;*p1+=32;//恢复小写  
92.                 p1++;  
93.                 p2++;  
94.                   
95.                 continue;//如果相等，2个字符串比较下一个字母，并且下面的程序将不执行。  
96.             }  
97.             else  
98.             {  
99.                 result = *p1 - *p2;  
100.                 *p2+=32;*p1+=32;//恢复小写。  
101.                 break;//如果不等，计算2者之差，然后跳出循环。  
102.             }//下面几个判断中的continue与break的含义类似  
103.         }  
104.         if((*p1<='z'&&*p1>='a'))  
105.         {//如果p1与p2中有大写，那么再判断p1是小写？  
106.             *p1-=32;  
107.             if (*p1 == *p2)  
108.             {  
109.                 *p1+=32;  
110.                 p1++;  
111.                 p2++;              
112.                 continue;  
113.             }  
114.             else  
115.             {  
116.                 result = *p1 - *p2;  
117.                 *p1+=32;  
118.                 break;  
119.             }  
120.         }  
121.         if (*p2<='z'&&*p2>='a')  
122.         {//如果p1与p2中有大写，那么再判断p2是小写？  
123.             *p2-=32;  
124.             if (*p1 == *p2)  
125.             {  
126.                 *p2+=32;  
127.                 p1++;  
128.                 p2++;                  
129.                 continue;  
130.             }  
131.             else  
132.             {  
133.                 result = *p1 - *p2;  
134.                 *p2+=32;  
135.                 break;  
136.             }  
137.         }  
138.         if (*p1 == *p2)  
139.         {  
140.             p1++;  
141.             p2++;  
142.             continue;  
143.         }  
144.         else  
145.         {  
146.             result = *p1 - *p2;  
147.             break;  
148.         }  
149.     }  
150.     return result;  
151. }   

//此程序将同一种字母的大写和小写视为相同处理，如果想区分大小写，使同一个字母的大写ASC码总是小于小写ASC码，那么直接用系统自带strcmp函数即可。

对于字符串长度为常数bit=k的字符数组(字符数组元素个数len=n)来说，BucketSort函数在划分26个桶(26个字母)时，所用时间为O(n*k),我们设每个桶中字符串个数k(i),所以对于每个桶我们可以调用时间为O(ni^2)=(n*k(i)),我们需要对26个字母在首位的字符串数组调用26次Bubble_sort函数，那么有∑O(ni^2)+Θ(n*k)=∑O(ni^2)+Θ(n)=Θ(n) (此式具体证明和书中桶排序证明类似，这里不做累述)

8-4 (水壶) 假设给了你n个红色的水壶和n个蓝色的水壶，它们的形状和尺寸都各不相同。所有红色水壶中盛有的水都不一样多，蓝色水壶也是如此。而且，对于每一个红色水壶来说，都有一个对应的蓝色水壶，两者盛有一样多的水，反之亦然。

 你的任务是找出所有的所盛水量一样多的红色水壶和蓝色水壶，并将它们配成一对。为此，可以执行如下操作：跳出一对水壶，其中一个是红色的，一个是蓝色的，将红色水壶倒满水，再将水倒入蓝色水壶中。通过这一操作，可以判断出这个红色水壶是否比蓝色水壶盛的水更多，或者两者是一样多的。假设这样的比较需要花费一个单位时间。你的目标是找出一个算法，它能够用最少的比较次数来确定所有水壶的配对。注意，你不能直接比较两个红色或者两个蓝色水壶。

a.设计一个确定性算法，它能够用Θ(n^2)次比较来完成所有水壶的配对。

在进行比较前，首先固定红蓝水壶的原有顺序。然后取出第一个红水壶，与n个蓝水壶进行比较，根据题意，总能找到一个蓝水壶和这个红水壶
匹配，然后将已配对的红水壶和蓝水壶放到一边，对剩下的n-1个红蓝水壶再次按照上面的方法进行比较。这样一直进行到蓝水壶剩0个代表都检测
完毕了。

以下是a代码:

[cpp] view plaincopy

1. #include <iostream>  
2. using namespace std;  
3. const n=10;  
4. void Kettle_a(int A[],int B[])  
5. {  
6.    for (int i=0;i<n;i++)//O(n)  
7.    {  
8.        for (int j=0;j<n;j++)//O(n)  
9.        {  
10.            if (B[j]==0)//判断B[j]水壶是否已经被检测过，如果检测过，下面的if判断将不执行。  
11.            {  
12.                continue;  
13.            }  
14.            if (A[i]==B[j])//判断A与B水壶到底哪两个是匹配的？  
15.            {  
16.                B[j]=0;//若匹配，那么B[j]置空，说明已经被调查过了。  
17.                cout<<"A["<<i<<"]=B["<<j<<"]="<<A[i]<<endl;//输出刚被调查的两个匹配水壶。  
18.            }  
19.        }  
20.    }//O(n^2)  
21. }  
22. void main()  
23. {  
24.     int A[n]={20,1,5,8,19,4,7,23,18,10};//数组中的整数代表水壶的容量 比如A[0]=20升。  
25.     int B[n]={23,7,5,10,20,18,1,4,8,19};//同上  
26.     Kettle_a(A,B);  
27. }  

b.证明：解决该问题算法的比较次数下界为Ω(nlgn).

水壶的比较可以看做一颗决策树，对于n个水壶来说，有n!种排列方式，每次红蓝水壶比较可以产生3种大小关系(>,<,=)，那么决策树的下界在第八章开篇已经有所阐述了，下界就是Ω(nlgn).

c.设计一个随机算法，其期望的比较次数为Ο(nlgn)，并证明这个界是正确的，对你的算法来说，最坏情况下得比较次数是多少？

从期望时间来看，快速排序最合适，并且最坏时间是Ο(n^2).

我们分步：1.从红色水壶中随机选择一个水壶作为主元。

                    2.从蓝色水壶中找到与红水壶主元容量一样的水壶。

                    3.完成蓝色水壶组的划分操作。(比红水壶主元容量大的在右，比A主元容量小的在左)

                    4.重复上面123来对红水壶组进行相同的三步操作，来完成一次PARTITION函数划分红水壶组与蓝水壶组操作。

                    5.对划分后的红蓝水壶组做递归，不断重复上述4步骤，然后同时完成对红与蓝水壶的排序操作，这样按顺序红蓝水壶一样容量的一一对应完成配对。                 

以下是代码：

[cpp] view plaincopy

1.  #include <iostream>  
2. #include <time.h>  
3. using namespace std;  
4. const n=10;  
5. int RANDOM(int p,int r)  
6. {  
7.    int t=rand()%(r-p+1)+p;  
8.    return t;  
9. }  
10. int PARTITION(int A[],int B[],int p,int r)//划分操作的时间复杂度还是cn,只不过常数项大一些，以因为多了几个循环  
11. {  
12.     int q=RANDOM(p,r);  
13.     int x=A[q],t=0;//选择A水壶作为B主元。  
14.     for (int j=p;j<r;j++)  
15.     {  
16.         if (B[j]==x)//找到B水壶容量和A主元一样的B中的位置，然后和B[r]交换位置。  
17.         {  
18.             swap(B[j],B[r]);  
19.         }  
20.     }  
21.     int i=p-1;  
22.     for ( j=p;j<=r-1;j++)//将B中以A主元为界，大于A主元的放到左边，小于A主元的放在右边。  
23.     {  
24.         if (B[j]<=x)//A水壶的某个水壶作为主元与B水壶的第j个进行比较。  
25.         {  
26.             i++;  
27.             swap(B[i],B[j]);  
28.         }  
29.     }  
30.     swap(B[i+1],B[r]);//这次交换过后，完成了B中以A主元为界的划分。  
31.     int y=B[i+1];//选取B水壶作为A主元。  
32.     for ( j=p;j<r;j++)  
33.     {  
34.         if (A[j]==y)//和上面的B水壶排序类似  
35.         {  
36.             swap(A[j],A[r]);  
37.         }  
38.     }  
39.     i=p-1;  
40.     for ( j=p;j<=r-1;j++)//和上面的B水壶排序类似  
41.     {  
42.         if (A[j]<=y)  
43.         {  
44.             i++;  
45.             swap(A[i],A[j]);  
46.         }  
47.     }  
48.     swap(A[i+1],A[r]);  
49.     return i+1;//最后，我们肯定的一点是A与B选择的主元是一样的，所以A与B有相同的划分。  
50. }  
51. void QUICKSORT(int A[],int B[],int p,int r)//2T(n)+cn<=T(n)<=T(n-1)+T(0)+cn  
52. {                                          //所以nlgn<=T(n)<=cn^2  
53.     if (p<r)  
54.     {  
55.         int q=PARTITION(A,B,p,r);  
56.         QUICKSORT(A,B,p,q-1);  
57.         QUICKSORT(A,B,q+1,r);  
58.     }  
59. }  
60.   
61.   
62. void main()  
63. {  
64.     //srand((unsigned)time(NULL));   
65.     int A[n]={20,1,5,8,19,4,7,23,18,10};//数组中的整数代表水壶的容量 比如A[0]=20升。  
66.     int B[n]={23,7,5,10,20,18,1,4,8,19};//同上  
67.     QUICKSORT(A,B,0,n-1);//经过对水壶容量的排序后，A的按顺序对应的每一个位置和B按顺序从小到大对应的水壶已经配对。  
68.     for (int i=0;i<n;i++)  
69.     {  
70.         cout<<A[i]<<" ";  
71.     }  
72.     cout<<endl;  
73.     for (i=0;i<n;i++)  
74.     {  
75.         cout<<B[i]<<" ";  
76.     }  
77.     cout<<endl;  
78. }  

以上程序完全符合快速排序性质，只不过划分操作时的时间Θ(n)中常数项多一些，因为多了几个循环。所以总的期望时间Ο(nlgn)常数项大些，快排的时间以前书中已经证明过了

8-5(平均排序)假设我们不是要完全排序一个数组，而只是要求数组中的元素在平均情况下是升序的。更准确地说，如果对所有的i=1,2,...n-k有下式成立，我们就称一个包含n个元素的数组A为k排序的：

a.一个数组是1排序的，表示什么含义？

1排序说明 A[i]≤A[i+1] 数组在任何情况下都是非降序排列的。

b.给出对数字1,2....10的一个排列，它是2排序的，但不是完全有序的。

1,3,2,4,6,5,7,9,8,10

c.证明：一个包含n个元素的数组是k排列的，当仅当对所有的ι=1,2...n-k,有A[i]≤A[i+k].

两边∑式展开后，左右两边个剩一项 也就是最终结论：A[i]≤A[i+k] 

d.设计一个算法，它能在Ο(nlg(n/k))时间内对一个包含n个元素数组进行k排序。当k是一个常数时，也可以给出k排序算法的下界。

[cpp] view plaincopy

1. #include <iostream>  
2. #include <time.h>  
3. using namespace std;  
4. const n=10;  
5. int PARTITION(int A[],int p,int r)  
6. {  
7.     int x=A[r];  
8.     int i=p-1;  
9.     for (int j=p;j<=r-1;j++)//O(n)  
10.     {  
11.         if (A[j]<=x)  
12.         {  
13.             i++;  
14.             swap(A[i],A[j]);  
15.         }  
16.     }  
17.     swap(A[i+1],A[r]);  
18.     return i+1;  
19. }  
20. void QUICKSORT(int A[],int p,int r,int k)  
21. {  
22.     if (p<r&&r-p>=k)//小于等于k时停止递归。其递归深度为lg(n/k)。  
23.     {  
24.         int q=PARTITION(A,p,r);  
25.         QUICKSORT(A,p,q-1,k);  
26.         QUICKSORT(A,q+1,r,k);  
27.     }  
28. }  
29. void Print(int A[])  
30. {  
31.     for (int i=0;i<n;i++)  
32.     {  
33.         cout<<A[i]<<" ";  
34.     }  
35. }  
36. void main()  
37. {  
38.     int A[n]={0};  
39.     srand( (unsigned)time( NULL ) );  
40.     for (int i=0;i<n;i++)  
41.     {  
42.         A[i]=rand()%100;  
43.     }  
44.     Print(A);  
45.     cout<<endl;  
46.     QUICKSORT(A,0,n-1,3);//k=3  
47.     Print(A);  
48.     cout<<endl;  
49. }  

其实不用快排用归并排序也可以实现。

将k排序数组分为k组有序子数组，每组Ai,A(i+k)....A(n-k+i) (i=1,2...k),进行最小堆的k路归并后，利用6.5-9结论可知时间复杂度O(nlgk)

f.证明：当k是一个常数时，对包含n个元素的数组进行k排序需要Ω(nlgn)的时间。

可以用决策树模型。可以看成对于n个数分成k组数，分别对每组n/k个数进行排序，所用方法是决策树，这n/k个数有(n/k)!种排列，其下界为Ω((n/k)lg(n/k)),那么对于k组数非严格证明就是把这k组数下界相加，那么就有Ω(k(n/k)lg(n/k))=Ω(nlg(n/k))因为k是常数，对于足够大的n 常数k忽略不计，所以有Ω(nlg(n/k))=Ω(nlg(n))

8-6 (合并有序列表的下界)合并两个有序列表是我们经常会遇到的问题。作为MERGE-SORT的一个子过程，我们在2.3.1节中已经遇到过这一问题。对这一问题，我们将证明在最坏情况下，合并两个都包含n个元素的有序列表所需的比较次数的下界是2n-1.

首先，利用决策树来说明比较次数一个下界2n-ο(n).

a.给定2n个数，请算出共有多少种可能的方式将它们划分成两个有序的列表，其中每个列表都包含n个数。

从2n个数里选取n个数分成一组共有C(2n,n)种方法，然后剩下n个数为一组。

b.利用决策树和(a)的答案，证明：任何能够正确合并两个有序列表的算法都至少要进行2n-ο(n)次比较。

合并前，有C(2n,n)种方法排列这两组有序列表，将此列表看成决策树，所以有C(2n,n)个叶子结点，C(2n,n)<2^h <=> h>lg2n!-2lgn!

 现在我们来给出一个更紧缺界2n-1

c.请说明：如果两个元素在有序序列中是连续的，且它们分别来自不同的列表，则它们必须进行比较。

网上查了貌似没有答案，所以自己写了个，写得不好莫要见笑。两个元素在有序序列是连续的。书中没有给出有序序列中两个元素是连续的概念，我的理解是这两个元素和挨着的元素连续(设An,Bn)An与(B(n-1)或Bn或B(n+1))，Bn与(A(n-1)或An或A(n+1))都可以称为连续的，而An与B(n+2)或Bn与A(n+2)是不连续的，并且(An与Bn的值非常接近)不存在d∈(An,Bn)且d∈(两个有序序列)。如果An跳过了与它连续的两个元素Bn与B(n+1)，直接与B(n+2)比较，那么An与未进行比较的两个元素Bn与B(n-1)必然形成了一段无序序列。同理Bn跳过了与它连续的两个元素An与A(n+1)也是一样的。

d 利用你对上一部分的回答，说明合并两个有序表时的比较次数下界为2n-1

完全没有思路。。。

8-7  这道题是第三版新增加的。

(0-1排序引理和列排序)针对两个数组元素A[i]和A[j](i<j)的比较交换操作的形式如下：

COMPARE-EXCHANGE(A,i,j)

1.if A[i]和A[j]

2.   exchange A[i]withA[j]

经过比较交换操作之后，我们得到A[i]≤A[j]。

     遗忘比较交换算法是指算法只按照事先定义好的操作执行，即需要比较的位置下标必须事先确定好。虽然算法可能依靠待排序元素个数，但它不能依赖排序元素的值，也不能依赖任何之前的比较交换操作的结果。例如，下面是一个基于遗忘比较交换算法的插入排序：

INSERTION-SORT(A)

1 for j=2 to A.length

2.   for i=j-1downto 1

3.          COMPARE-EXCHANGE(A,i,i+1)

    0-1排序引理提供了有力的方法来证明一个遗忘比较交换算法可以产生正确的排序结果。该引理表明，如果一个遗忘比较交换算法能够对所有只包含0和1的输入序列排序，那么它也可以对包含任意值的输入序列排序。

    你可以用反例来证明0-1排序引理：如果一个遗忘比较交换算法不能对一个包含任意值得序列进行排序，那么它也不能对某个0-1序列进行排序。不妨假设一个遗忘比较交换算法X未能对数组A[1..n]排序。设A[p]是算法X未能将其放到正确位置的最小的元素，而A[q]是被算法X放在A[q]是被算法X放在A[p]原本应该在的位置上的元素。定义一个只包含0和1的数组B[1..n]如下：B[i]=0 若A[j]≤A[p]  B[i]=1 若A[j]>A[p]。

    a.讨论：当A[q]>A[p]时，有 B[p]=0 和B[q]=1.

分两种情况讨论：
当A[q]>A[p]时，设i=q时，有A[i]>A[p]，那么根据B的定义有B[i]=1 <=> B[q]=1
当A[q]>A[p]时，设i=p时，有A[q]>A[i](<=>A[i]<A[q])，这里的q相当于原B定义的p,那么根据B的定义有B[i]=0 <=> B[p]=0 

  b.为了完成0-1排序引理的证明，请先证明算法X不能对数组B正确排序。

根据我们对数组B的定义，如果有A[i]≤A[j]则就有B[i]≤B[j]，因此算法X对于数组A和数组B进行交换的顺序都相同。所以在数组A上产生的输出...A[q]...A[p]...那么也有数组B产生相同的输出顺序...B[q]...B[p]...，因为算法X不能对包含任意值的数组A进行排序，对于相同的排列顺序B也就不能正确排序。

      现在，需要用0-1排序引理来证明一个特别的排序算法的正确性。列排序算法是用于包含n个元素的矩形数组的排序。这一矩形数组有r行s列(因此n=rs),满足下列三个限制条件：r必须是偶数

       s必须是r的因子

       r≥2s^2

当列排序完成时，矩形数组是列优先有序的，按照列从上到下，从左到右，都是单调递增的。

     如果不包括n的值计算，列排序需要8步操作。所有奇数步都一样；对每一列单独进行排序。每一个偶数步是一个特定的排列。具体如下：

1.对每一列进行排序。

2.转置这个矩形数组，并重新规整化为r行s列的形式。也就是说，首先将最左边的一列放在前r/s行，然后将下一列放在第二个r/s行，以此类推。

3.对每一列进行排序。

4.执行第2步排列操作的逆操作。

5.对每一列进行排序。

6.将每一列的上半部分移到同一列的下半部分位置，将每一列的下半部分移到下一列的上半部分，并将最左边一列的上半部分置空。此时，最后一列的下半部分成为新的最右列的上半部分，新的最右列的下半部分为空。

7.对每一列进行排序。

8.执行第6步排列操作的逆操作。

       图8-5显示了一个在r=6和s=3时的列排序步骤(即使这个例子违背了 r≥2s^2的条件，列排序仍然有效。)

c.讨论：即使不知道奇数步采用了什么排序算法，我们也可以把列排序看做一种遗忘比较交换算法。

奇数步可能没有采用遗忘比较算法，但是根据遗忘比较算法定义需要比较的位置下标在奇数步排序后已经被确定好了，而偶数步用的排序方法是固定的，所以不需要依赖任何之前的比较交换操作的结果，更不依赖于排序元素的值。所以总体来看这8步是可以看做一种遗忘比较交换算法。

    虽然似乎很难让人相信列排序也能实现排序，但是你可以利用0-1排序引理来证明这一点。因为列排序可以看做是一种遗忘比较交换算法，所以我们可以使用0-1排序引理。

下面一些定义有助于你使用这一引理。如果数组某个区域只包含全0或全1，我们定义这个区域是干净的。否则，如果这个区域包含的是0和1混合的，则称这个区域是脏的。这里，假设输入数据只包含0和1，且输入数据能够被转换为r行s列。

d.证明：经过第1-3步，数组由三部分组成，顶部一些由全0组成的干净行，底部由一些全1组成的干净行，以及中间最多s行脏行。

第一步过后，绝大部分的0在矩阵中的最前几个干净的行，绝大部分的1在矩阵的最后几个干净的行，而中间有一些行可能是由0与1混合的脏行

第二步过后，各行之间遵循这样一种规律，1.最上面的是一些干净的0行(纯0)，2.然后干净的0开始变脏混合一些1形成脏行(0逐渐少1逐渐多)，3.然后脏行逐渐干净(直到最终为纯1为止)。这样在第一步中的第一列在第二步中转化为数行输出完毕。然后对第一步的第二列实现同样的上述操作。。。。上面3点不断重复循环直到最终整个矩阵按照步骤2排列好了。一共有s组由以上3点(1.纯0,2.0->1过渡,3.纯1)组成的行，而每组含有r/s行，每组中最多只有一行为过渡(0->1)行(不存在2行以上的0->1过渡行，因为如果存在，比如有2行是过渡行，那么需要从0到1然后又从0到1,这样原来第一步的那一列就根本没有排好序)，所以对于这s组来说，就有s行是脏行。

第三步过后，和第一步有着类似的结果就是前面一些行是含有纯0的干净的行，然后中间是由0与1混合而成的共s行脏行(0逐渐变少1逐渐增多)，最后一些行含有纯1的干净的行。

e.证明：经过第4步之后，如果按照列优先原则读取数组，先读到的是全0的干净区域，最后是全1的干净区域，中间是由最多s^2个元素组成的脏的区域。

第四步由于是第二步的逆操作，将每r/s行按顺序放入每一列，那么其中有s行是脏行转成列的形式，因为只是存放的形式变了(由行转成列)，其中并没有对其排序，脏行的元素个数是不变的。那么只要计算下第三步过后脏行元素个数即可，第三步过后，s行是脏行，同时这个矩阵总共有r行s列，那么这个矩阵其中的s脏行也应该有s列，元素个数=s脏行Xs列=s^2。所以第四步过后有最多s^2个元素组成的区域。

f.证明：第5-8步产生一个全排序的0-1输出，并得到结论，列排序可以正确的对任意输入值排序。

第五步排序包含脏区域的列并且在排序过程中脏区域没有增加。

第六步将整个脏区域移动到同一列中。

第七步对此矩阵再次进行排序，脏区域也变得有序，

第八步再移动回来。

并且在5-8步排序过程中脏区域最多s^2≤r/2,也就是5-8步脏区域元素个数没有超过r/2。既然由0-1组成的矩阵已经排好序了。那么根据0-1排序引理知，如果一个遗忘比较算法能够对所有只包含0和1的输入序列排序，那么它也可以对包含任意值得输入序列排序。

g.现在假设s不能被r整除。证明：经过第1-3步，数组的顶部有一些全0的干净行，底部有一些全1的干净行，中间是最多2s-1行脏行。那么与s相比，在s不能被r整除时，r至少要多大才能保证列排序的正确性？

如果中间最多有2s-1脏行，那么对于r行s列的矩阵来说，中间脏区域的元素个数应该是(2s-1)脏行xs列=2s^2-s个，根据f)的结论知道脏区域元素个数不超过r/2，那么有2s^2-s≤r/2，这样r≥4s^2-2s.但是这个结论的大前提是“中间最多有2s-1脏行”，可我不太明白为什么是2s-1脏行？由请高手留言。谢谢！

h.对第1步做一个简单修改，使得我们可以在s不能被r整除时，也保证r ≥2s^2，并且证明在这一修改后，列排序仍然正确。

完全不懂。懂的请留言谢谢！