算法设计与分析－第四章 排序
姓 名：王 强 学号：20509345
4.1：在我们所了解的早期排序算法之中有一种叫做Maxsort的算法。它的工作流程如下：首先在未排序序列（初始时为整个序列）中选择其中最大的元素max，然后将该元素同未排序序列中的最后一个元素交换。这时，max元素就包含在由每次的最大元素组成的已排序序列之中了，也就说这时的max已经不在未排序序列之中了。重复上述过程直到完成整个序列的排序。
(a) 写出Maxsort算法。其中待排序序列为E，含有n个元素，脚标为范围为0,?,n?1。
void Maxsort(Element[] E) { int maxID = 0;
for (int i=E.length; i>1; i--) { for (int j=0; j if (E[j] > E[maxID]) maxID = k; } E[i] <--> E[maxID]; } } (b) 说明在最坏情况下和平均情况下上述算法的比较次数。 最坏情况同平均情况是相同的都是C(n)??i?i?1n?1n(n?1)。 24.2：在以下的几个练习中我们研究一种叫做“冒泡排序”的排序算法。该算法通过连续几遍浏览序列实现。排序策略是顺序比较相邻元素，如果这两个元素未排序则交换这两个元素的位置。也就说，首先比较第一个元素和第二个元素，如果第一个元素大于第二个元素，这交换这两个元素的位置；然后比较第二个元素与第三个元素，按照需要交换两个元素的位置；以此类推。 (a) 起泡排序的最坏情况为逆序输入，比较次数为C(n)??i?i?1n?1n(n?1)。(b) 最好情况为已排2序，需要(n-1)次比较。 4.3： (a) 归纳法：当n=1时显然成立，当n=2时经过一次起泡后，也显然最大元素位于末尾；现假设当n=k-1是，命题也成立，则当n=k时，对前k-1个元素经过一次起泡后，根据假设显然第k-1个元素是前k-1个元素中最大的，现在根据起泡定义它要同第k个元素进行比较，当k元素大于k-1元素时，它为k个元素中最大的，命题成立；当k元素小于k-1元素时， 第 1 页 共 54 页 算法设计与分析－第四章 排序 姓 名：王 强 学号：20509345 它要同k-1交换，这时处于队列末尾的显然时队列中最大的元素。综上所述，当n=k时命题成立。(b)反正法：假设当没有一对相邻的元素需要交换位置的时候，得到的序列是未排序的，则该未排序队列至少存在一对元素是逆序的，现设这两个元素未E(I)和E(i+k)，其中E(i)>E(i+k)。而根据没有一对相邻元素需要交换位置的条件，又有E(i+k)>E(i+k-1)>……>E(i+1)>E(i)，这是矛盾的。 4.4： (a)证明：根据4.3(a)j+1处交换后，j+1元素是前j+1个元素中最大的。又因为在j+1到n-1之间没有再发生交换，即说明E(j+1) (b) void bubbleSort(Element[] E, int n) { int numPairs; int last; int j; last = n - 1; while(last>0) { numPairs = last; last = -1; for(int j=0; j Interchange E[j] and E[j+1]; last = j; } } } return; } (c) 这种改进对最坏情况并没有什么改进，因为在最坏情况（倒序）时，还时从n-1到1的每个过程都循环一遍。 4.5 不可以。正如同前面练习中所说的那样，已经排序的并不一定在“正确的位置之上”，这也许就是所说的“小局部，大局观”吧。简单的说明可以时，每一次向后的移动都是针对当前最大值的，也就是说最大值的移动是一移到底的，而同时相对小值的移动每次最多是一步。所以说即使是局部已经排序了，但是相对于“正确”排序的位置还是有差距的。 4.6 1,n,n-1,…,2 和 n,n-1,…,3,1,2 说明：将1放在n～2的逆序中任何位置都不改变最坏情况。 第 2 页 共 54 页 算法设计与分析－第四章 排序 姓 名：王 强 学号：20509345 4.7 插入排序的最佳情况是序列已排序，这时候需要比较次数为n-1次，移动次数为0次。 4.8 (a) 最坏情况为插入位置在正数第2个位置，或者倒数第2个位置，比较次数[i/2]。在采用折半查找的时候，会设定已排序序列的首尾指针和当前指针，这样只有在第2个位置的元素进行最后的比较。 (b) 在最坏情况下插入位置在第1个位置上，移动次数为i次。 (c) 由于折半插入排序只是减少了比较的次数，并没有减少移动的次数，所以算法的时间复杂度仍然是O(n2)的。 (d) 采用链表数据结构后的插入排序是可以减少元素的移动次数的，因为整个排序的最多移动次数为3(n-1)。但是这样也仅仅是减少了元素的移动时间，并没有减少元素的比较次数，所以算法的时间复制度仍然是O(n2)的。 4.9 首先说明直接插入排序是稳定的。在有重复键值输入的情况下，插入排序的平均时间复制度会有所增加，因为在寻找插入位置的时候，会多比较那些相等的值。 4.10 含有n个元素的逆排序序列的逆序数为4.11 IntList listInsSort(IntList unsorted) { IntList sorted,remUnsort; sorted = null; remUnsort = unsorted; while (remUnsort != null) { int newE = first(remUnsort); sorted = insertl(newE,sorted); remUnsort = rest(remUnsort); } return sorted; } n(n?1)。 2算法分析：假设unsorted有n个元素。当sorted已经排序了k个元素了，这时调用insertl的时候，最好情况所耗时间为O(1)的，平均情况和最坏情况的时间消耗为O(k)的。调用insertl时，变量k的变化范围为0～n-1的。因此在整个过程中的时间复制度，最好为O(n)，平均和最坏为O(n2) 第 3 页 共 54 页 算法设计与分析－第四章 排序 姓 名：王 强 学号：20509345 4.12 4.13 extendSmallRegion的后置条件为：在元素E[low],...,E[highVac-1]中最左面一个≥“枢纽”的元素将被移动到E[highVac]中，并且指针会在这里返回；如果没有这样的元素，会将highVac返回。 4.15 对于已经排序的序列，进行快速排序将会进行 n(n?1)次比较和2(n?1)次移动。E[first]2被移动到pivotElement，之后在每次调用一次parttion的时候都被移动到后面。 4.17 考虑含有k个元素的一个子区域。选择“枢纽”需要3（C32）次比较，对于其他k-3个元素也需要进行k-3次的同“枢纽”进行比较，也就是说总共需要进行k次的比较。这相对于简单的选择E[first]作为“枢纽”的方式并没有多少改进。一种极端的情况是在选择E[first] 、E[(first+last)/2]和E[last]的时候，总是选中了两个序列中最小的两个元素，这样每次都选中序 n2列中第二小的元素做“枢纽”的话，总的比较次数是次。所以说对于逆序输入的序列进行 4快速排序，如果采用选择E[first] 、E[(first+last)/2]和E[last]的中间元素作为“枢纽”的方法的时间复制度仍然是O(n2)的。 4.19 (a) 在第一次调用后序列为：1，9，8，7，6，5，4，3，2，10；移动1次。在第二次调用后序列不变，没有移动。对含有n个元素的逆序序列进行排序，调用partition的总的移动 n次数为，同时还需要加上在选择“枢纽”是用到的2(n?1)次移动。 2(b) 在第一次调用后序列为：9，8，7，6，5，4，3，2，1，10；移动18（2(n-1)）次。在第二次调用后序列为：8，7，6，5，4，3，2，1，9，10；移动16（2(n-2)）次。总的移动次数为2?i?n(n?1)，另外还有在选择“枢纽”是用到的2(n?1)次移动。 i?1n?1(c) partitionL的最大优点就是简单。在多数情况下，调用partitionL要比调用partition需要更多的移动次数。在a和b中，partitionL需要做90（10×9）次移动，而partition仅仅做了5（10/2）次移动。（另外完成快速排序还需要增加选择“枢纽”是用到的18次移动。 4.21 第 4 页 共 54 页 算法设计与分析－第四章 排序 姓 名：王 强 学号：20509345 （a）在partitionL中，只要“unknown”元素小于“枢纽”元素，就会发生两次移动， 12(k?1)概率为。所以对k个元素进行排序的平均移动次数为。因此使用partitionL的快速 22排序的移动次数大约为1.4nlgn?cn。 （b）在partition中，，每个 “unknown”元素或者经过extendSmallRegion检测，或者经过extendLargeRegion检测。在extendSmallRegion中，“unknown”元素在“大于等于”枢纽元素 1；在extendLargeRegion中，“unknown”元素在“小于”枢纽元素21(k?1)的时候需要移动，概率为。所以平均的移动次数为。因此使用partition的快速排序 22的时候需要移动，概率为 的移动次数大约为0.7nlgn?cn （c）使用partition的快速排序将使用1.4nlgn次比较和0.7nlgn次移动。归并排序的时间复制度大约是1.5nlgn。 4.23 IntList listMerge(IntList in1, IntList in2) { IntList merged; if (in1 == nil) merged = in2; else if (in2 == nil) merged = in1; else { int e1 = first(in1); int e2 = first(in2); IntList remMerged; if (e1 <= e2) { remMerged = listMerge(rest(in1), in2); merged = cons(e1, remMerged); } else { remMerged = listMerge(in1, rest(in2)); merged = cons(e2, remMerged); } } return merged; } 或者为： IntList listMerge(IntList in1, IntList in2) { return in1 == nil ? in2 : in2 == nil ? in1 : first(in1) <= first(in2) ? 第 5 页 共 54 页 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《算法设计与分析》课后习题在线全文阅读。
相关推荐：