偶看新闻亿图水貂能卖多少钱:9.8.1 归并排序算法（1）
来源：百度文库 编辑：偶看新闻 时间：2024/04/29 03:21:13
9.8.1 归并排序算法（1）
归并”一词的中文含义就是合并、并入的意思，而在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表。
归并排序（Merging Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到.n/2.（.x.表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。7
注：7本书只介绍2路归并排序。
好了，有了对归并排序的初步认识后，我们来看代码。
- /* 对顺序表L作归并排序 */
- void MergeSort（SqList *L）
- {
- MSort（L->r,L->r,1,L->length）;
- }
一句代码，别奇怪，它只是调用了另一个函数而已。为了与前面的排序算法统一，我们用了同样的参数定义SqList *L，由于我们要讲解的归并排序实现需要用到递归调用8，因此我们外封装了一个函数。假设现在要对数组{50,10,90,30,70,40,80,60,20}进行排序，L.length=9，我现来看看MSort的实现。
- /* 将SR[s..t]归并排序为TR1[s..t] */
- 1 void MSort（int SR[],int TR1[],int s, int t）
- 2 {
- 3 int m;
- 4 int TR2[MAXSIZE+1];
- 5 if（s==t）
- 6 TR1[s]=SR[s];
- 7 else
- 8 {
- 9 m=（s+t）/2; /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
- 10 MSort(SR,TR2,s,m);/*递归将SR[s..m]归并为有序的TR2[s..m]*/
- 11 MSort(SR,TR2,m+1,t);/*递归将SR[m+1..t]归并为有序TR2[m+1..t]*/
- 12 Merge(TR2,TR1,s,m,t);/*将TR2[s..m]和TR2[m+1..t]*/
- /*归并到TR1[s..t]*/
- 13 }
- 14 }
1．MSort被调用时，SR与TR1都是{50,10,90,30,70,40,80,60,20}，s=1，t=9，最终我们的目的就是要将R1中的数组排好顺序。
2．第5行，显然s不等于t，执行第8～13行语句块。
3．第9行，m=（1+9）/2=5。m就是序列的正中间下标。
4．此时第10行，调用“MSort（SR,TR2,1,5）;”的目标就是将数组SR中的第1～5的关键字归并到有序的TR2（调用前TR2为空数组），第11行，调用“MSort（SR,TR2,6,9）;”的目标就是将数组SR中的第6～9的关键字归并到有序的TR2。也就是说，在调用这两句代码之前，代码已经准备将数组分成了两组了，如图9‐8‐2所示。
注：8也可以不用递归实现，后面有提及。
图9-8-25．第12行，函数Merge的代码细节一会再讲，调用“Merge（TR2,TR1,1,5, 9）;”的目标其实就是将第10和11行代码获得的数组TR2（注意它是下标为1～5和6～9的关键字分别有序）归并为TR1，此时相当于整个排序就已经完成了，如图9‐8‐3所示。
（点击查看大图）图9-8-36．再来看第10行递归调用进去后，s=1，t=5，m=（1+5）/2=3。此时相当于将5个记录拆分为三个和两个。继续递归进去，直到细分为一个记录填入TR2，此时s与t相等，递归返回，如图9‐8‐4的左图所示。每次递归返回后都会执行当前递归函数的第12行，将TR2归并到TR1中，如图9‐8‐4的右图所示，最终使得当前序列有序。
（点击查看大图）图9-8-47．同样的第11行也是类似方式，如图9‐8‐5所示。
（点击查看大图）图9-8-5