数据结构-C语言描述(第三版)第11章内排序.ppt

易见，函数MergeSort的size取值不超过(lbn(个，即最多进行(lbn(趟排序。对size的每个值都将扫描n个记录，所以函数MergeSort的运行时间为O(n lbn)。合并排序需要与原序列相同长度的辅助数组Temp，所需的额外空间为O(n)。程序11－9的两路合并排序是一种稳定的排序方法。 11.4.3* 链表上的合并排序 　1. 合并排序的递归算法 　在11.4.1和11.4.2节中，我们讨论了合并排序的迭代算法。我们还可以设计它的递归算法。合并排序的递归算法是建立在对问题的分解的基础上的。设待排序的序列为(K0, K1，…, Kn－1)，合并排序的递归算法的基本思想是：为了将这一序列排成有序序列，我们可以如对半有哪些信誉好的足球投注网站一样，将序列对半分成左右两个长度基本相等的子序列，对两个子序列分别进行排序。 当两个子序列分别排成有序序列后，可采用将两个有序序列合并成一个有序序列的合并函数合并之。那么，采用什么方法分别对两个子序列进行排序呢？仍然采用合并排序。所谓仍然采用合并排序是说，如果子序列中多余一个记录，我们对它继续进行对半分割，再分成两半，如果分割后的子序列还不够小，即还多于一个记录，则还应继续分割，直到分割而成的子序列中只包含一个记录或为空序列为止，这时需调用Merge函数实施合并操作，从而实现合并排序。 图11－11 合并排序递归算法 (a) 分割过程；(b) 合并过程 2. 两路合并过程 单链表上的两路合并函数Node *Merge(Node *p, Node* q)有两个指针参数p和q，它们分别指向两个有序子链表的表头。程序11－10使用了一个哑结点(dummy node)，它不包含记录，仅用作合并后的有序链表的表头结点，简化指针操作。比较p和q所指示的记录，将较小关键字值的记录链接到结果链表的表尾。指针rear始终指向结果链表的表尾。这一过程进行到两个子链表之一成为空表时为止，然后再将另一个子表的剩余部分链在结果链表的尾部，算法结束，函数返回head.Link的值，该值保存着结果链表的起始结点的地址。合并过程示意图见图11－12。具体的Merge函数见程序11－10。程序中结点head是哑结点。 图11－12 有序链表的合并过程 3. 分割函数 Divide函数的功能是将一个链表分割成两个长度基本相等的链表。Divide函数使用两个指针pos和mid。两个指针都从表头开始向后移动，其中pos每次后移两个结点，mid每次后移一个结点，等到pos移出最后一个结点后成为空指针时，以mid指示的结点作为前半部分子表的表尾，这样，便将原链表对半分割成前后两半。函数值返回后半部分子表的头指针。程序11－11为Divide函数的C语言程序。 【程序11－11】 Divide函数。 Node * Divide(Node * p) { Node *pos , *mid , *q; if ((mid = p) == NULL) return NULL; pos = mid -Link; while (pos != NULL) { pos= pos-Link; if (pos!= NULL) { mid = mid -Link; pos = pos -Link; } } q= mid-Link; mid-Link = NULL; return q; } 4. 两路合并排序 利用Divide和Merge函数，我们可以很容易地实现合并排序的递归程序。程序首先调用函数Divide将链表对半分割成前后两个子表。分别对这两个子链表实行合并排序，也就是执行递归调用语句，通过两次递归调用，将这两个子链表分别排序成有序表。最后，调用Merge函数将这两个有序子链表合并成一个有序链表，从而结束合并排序。由于对链表的合并排序被设计成递归函数，所以，我们还需要设计一个面向用户的排序函数来调用此递归函数，完成排序运算。两路合并排序的C语言实现见程序11－12。 【程序11－12】 两路合并排序。 void RMSort(Node** sublst) { if (*sublst != NULL (*sublst)-Link != NULL) { Node *second = Divide(*sublst); RMSort(sublst); RMSort(second); *sublst = Merge(*sublst, second); } } void RMergeSort(List *lst) {