1. 证明：基于比较的排序算法平均时间复杂度A(n)>=O(nlogn) 与最坏时间复杂度
W(n)>=O(nlogn) 解答：
(1)证最坏时间复杂度W(n)>=O(nlogn)
对于n个元素排序，若排序正确，必须使n!中排序结果都出现在判定树叶子中; 最坏时间对应最深叶子深度，最深叶子深度对应判定树的高度。 要证W(n)>=O(nlogn) 即证判定树高h>=O( nlogn) 判定树高度为0时， <=20 =1个叶子 判定树高度为1时， <=21 =2个叶子 假定高度为h的判定树有<=2h 个叶子
那么高度为h+1的判定树，其左子树的高度<=h，叶子个数<=2h ；
其右子树的高度<=h，叶子个数<=2h 。于是高度为h+1的二分树叶子个数<=2h+1 所以高度为h的判定树有<=2h 个叶子。 叶子数n<=2h 即h>=logn
叶子数为n!的判定树高h>=log(n!)
log(n!)??log2i??log2xdx?i?11nn1n11lnxdx?[nln?(n?1)]?nlogn?(n?1)?O(nlog2n)2?1ln2ln2ln2因此W(n)>=O(nlogn)
证毕！
(2) 平均时间复杂度A(n)>=O(nlogn)
比较排序的平均时间复杂度>=判定树的平均叶子深度
A(n)?111n!11h(i)?log(n!)?..log(n!)?log(n!)?nlog2n?O(nlog2n)??222n!i?1n!i?1n!222n!n!2推导说明: 叶子数为n!的判定树高度?log2(n!)，判定树高度为log2(n!)?1时，至多
n!n!个叶子，因此在高度为log2(n!)的判定树中，至少有个叶子结点的高度为22log2(n!)。第一次放缩时，将高度小于log2(n!)的n!个叶子结点的高度都缩为0，
2n!只考虑剩余的高度为log2(n!)的个叶子结点。
2有
2. 归并排序的复杂度分析及优化措施
(1).归并算法时间复杂度分析 最坏情况
采用归并算法对n个元素排序，在一趟归并操作中，要进行的比较次数为n-1，
合并操作的公式为，n表示元素的个数，有
Wn?W(?n/2?)?W(?n/2?)?n?1
??可以递归推导得
W(n)?nlogn?logn(logn?1)/2
即
W(n)??(nlogn)。
所以归并排序优点为:平均时间与最坏时间都达到了排序的最好指标，速度快。 (2) 优化措施 归并排序改进方法：
1）：与插入排序相结合 2）：无逆序 3）：不递归 4）：不回写
具体改进的算法描述：
将原数据集合分成若干组，分组策略如下：
第一组：从第1个元素a1开始到第20个元素a20，用插入排序排成有序集，从第21个元素起，按无逆序原则向后找到第一个出现逆序的元素ak?1为止。那么第一组的元素为
a1,a2…a20…ak.
第二组：从ak?1开始按照找第一组的方法，找出第二组;
第三组、第四组……依次类推。
按此方法将数据集分成若干组，在分组的过程中体现出与插入排序相结合和无逆序的改进。
对划分的组进行如下处理：
假定初始的元素存放在数组A中，申请同样大存储空间的数组B。 奇数趟归并排序时（此时元素存储在数组A中），从前向后，两两相邻的分组归并后存放到数组B。
偶数趟归并排序时（此时元素存储在数组B中），从后向前，两两相邻的分组归并后存放到数组A。
重复上述操作，直到最后归并到成一个集合为止。
按此方法对组进行归并排序，体现了不回写和不递归的改进。 3. 快速排序算法时间复杂度分析及优化措施
(1) 快速排序最坏时间复杂度为W(n)=O(n2) (2) 快速排序平均时间复杂度为A(n)=O(nlogn)
假定序列的每个元素被选为参考元素的可能性相等 A(1)=A(0)=0
2n?11n?1
A(k)A(n)?n?1?(A(k)?A(n?1?k))?n?1?n nk?0k?02n?12n?1klogk?n?1?klnk假设A(k)<=klogk 则 A(n)??n?1?n?1nk?1nln2k?1n ?klnk?xlnxdx1 k?1n 111xlnxdx?n2ln(n)?n2?1 244 21211?A(n)??n?1?(nln(n)?n2?) nln2244???????111(n2ln(n)?n2?)nln22211?nlogn?(1?)n??1?O(nlogn)ln2nln2?n?1?(3) 优化措施
a) 与插入法结合使用，当分割集<20时用插入
b) 取a1 an/2 an 中的中间元作为参考元（适当选择参考元） c) 不使用递归
4. n个数据元素，设计算法输出其中不相同的数据元素，并说明你的算法有多快？要求：
输出时，不改变输入的顺序。
答： 1）算法描述：设输入序列为3，1，1，3 设定数据结构，每个节点如图：
输入顺序号 关键字域 标志域 由这样的一些数据结构的节点再构成数组
初始化如下：标志域均为0，数组如下：
1 3 0 2 1 0 3 1 0 4 3 0
按照关键字进行归并排序： 第一次归并： 2 1 0 1 3 0 3 1 0 4 3 0
第二次归并：
1 0 3 1 0 1 3 0 4 3 0 2
将第一个元素的标志域置1，因为前面还没有与之相同的关键字。 1 1 2 然后每次将后一个与前一个元素的关键字进行比较，如果不相同，则将标志域置为1，相同则不变，那么数组成为： 1 1 3 1 0 1 3 1 4 3 0 2 然后，按照输出序号再次进行排序得： 3 1 2 1 1 3 1 0 4 3 0 1
最后将标志域为1的元素输出即可。 2）算法复杂度分析
对数据域进行归并排序时间复杂度为：O（nlogn） 对序号进行归并排序时间复杂度为：O(nlogn) 输出元素的时间复杂度为 O(n)
总的算法时间复杂度为：O（nlogn）
5. 给出最坏情况下，只需7次比较的5个元素排序算法。
1）.对a1,a2,a3,a4进行3次比较
a4a2a4a1a2a3a4
若a3>a4,a3和a4对换；若a1>a2,a1和a2对换；若a2>a4,a2和a4对换且a1和a3对换. 生成序列为
a1a2a3a4
a2a3a42）. ：
a5a1a1a2a5a3a4
a4a1a2a3
a5a1a5a2a3a4
3）.将a3插入到以上四种可能，用折半查找，最多需要2次比较 由1、2、3得，此方法只需7次比较。
6. 输入n个元素，输出其和为m的全部整数对。
答：首先进行排序，对排好序元素设置首尾两个指针low,high,当low 如果E[low]+E[high]==m,则; low++;high--,输出数对 如果E[low]+E[high] 解：假设A中元素个数为n,B中元素个数为m. 算法思想：输入两个序列A、B a.分别对A、B进行归并排序 b.同时扫描A、B,设两个指针分别指向A、B的当前扫描元素。初始时i、j分别指向A[0]、B[0] c. 若A[i]< B[j]则将A[i]存入C中，i后移 若A[i]>B[j] 则将B[j]存入C中，j后移 若A[i]= B[j] 则同时将i、j后移，直到分别出现与其前一个元素值不同的元素为止。 d 重复c直至A、B同时扫描完或某一个扫描完，此时将另一个序列所有剩余元素直 接 插入C中即可。 归并排序的时间复杂度为O(nlog2n?mlog2m),扫描的时间复杂度为O(n?m)，总的时间复杂度为O(nlog2n?mlog2m)。 8. 给出n个正整数内置分奇偶的算法，偶数排在奇数前边，并说明算法的比较次数和移动 次数。（类似快速排序中的一趟比较） 答 (1)算法描述 1.第一个元素放入temp中， low指向第一个元素，high指向最后一个元素 2.先从右向左依次扫描判断high指向的元素的奇偶， 若E(high)为奇数 high--; 若E(high)为偶数 E(high)->E(low++) 然后再从右向左扫描判断low指向的元素的奇偶性 若E(low)为偶数 low ++ 若E(low)为奇数 E(low)->E(high--) 3 若low 否则 temp->E(low)中 程序结束。 (2)伪代码： Void partion ( int * a , int n) { Int low=0,high=n-1; Int temp=a[0]; While(low While(a[high]是奇数&&high>=0) high--; If(high!=0) a[low++]=a[high]; While(a[low]是偶数&&low If(high!=0&&low!=n-1) A[low]=temp; } (3)复杂度分析 本算法在比较次数上：因为第一个元素没有参加比较，故为n-1次 在移动元素次数上，是来回移动的，最坏情况下，n-1个元素都要相互移动，为n-1次，还要将首位置元素移动到temp和从temp移入最终空位 2次，共需要n-1+2次。 9. 对一个数值在(1,100)之间的数组进行排序，假设共有n个元素。 （1）试给出基数排序的空间消耗，桶数，总需要时间。 （2）给出在基数排序过程中找出n个元素（n>10）前10个最大的算法思想。 空间复杂度：桶的个数m(如m取100),此时只需一次装桶倒桶完成排序。n个元素需要n个空间存放，还需要n个链表(2n)空间，因此总共需要(3n+m)个空间. 时间复杂度：在元素插入链表时，将元素插入链头，这样插入的时间为O(n)，然后将m