算法7-排序-归并排序

朱雀 2021-12-15 03:34 232阅读 0赞

## 归并排序的基本思想 ##

将待排序序列R\[0...n-1\]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。

综上可知：

归并排序其实要做两件事：

（1）“分解”——将序列每次**折半划分**。

（2）“合并”——将划分后的序列段**两两合并后排序**。

我们先来考虑第二步，**如何合并**？

在每次合并过程中，都是对两个有序的序列段进行合并，然后排序。

这两个有序序列段分别为 R\[low, mid\] 和 R\[mid+1, high\]。

先将他们合并到一个局部的**暂存数组**R2中，带合并完成后再将R2复制回R中。

为了方便描述，我们称 R\[low, mid\] 第一段，R\[mid+1, high\] 为第二段。

每次从两个段中取出一个记录进行关键字的比较，将较小者放入R2中。最后将各段中余下的部分直接复制到R2中。

经过这样的过程，R2已经是一个有序的序列，再将其复制回R中，一次合并排序就完成了。

**核心代码**

public void Merge(int\[\] array, int low, int mid, int high) \{  
int i = low; // i是第一段序列的下标  
int j = mid + 1; // j是第二段序列的下标  
int k = 0; // k是临时存放合并序列的下标  
int\[\] array2 = new int\[high - low + 1\]; // array2是临时合并序列  
  
// 扫描第一段和第二段序列，直到有一个扫描结束  
while (i <= mid && j <= high) \{  
// 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描  
if (array\[i\] <= array\[j\]) \{  
array2\[k\] = array\[i\];  
i++;  
k++;  
\} else \{  
array2\[k\] = array\[j\];  
j++;  
k++;  
\}  
\}  
  
// 若第一段序列还没扫描完，将其全部复制到合并序列  
while (i <= mid) \{  
array2\[k\] = array\[i\];  
i++;  
k++;  
\}  
  
// 若第二段序列还没扫描完，将其全部复制到合并序列  
while (j <= high) \{  
array2\[k\] = array\[j\];  
j++;  
k++;  
\}  
  
// 将合并序列复制到原始序列中  
for (k = 0, i = low; i <= high; i++, k++) \{  
array\[i\] = array2\[k\];  
\}  
\}

掌握了合并的方法，接下来，让我们来了解 **如何分解**。

在某趟归并中，设各子表的长度为**gap**，则归并前R\[0...n-1\]中共有**n/gap**个有序的子表：R\[0...gap-1\], R\[gap...2\*gap-1\], ... , R\[(n/gap)\*gap ... n-1\]。

调用Merge**将相邻的子表归并**时，必须对表的特殊情况进行特殊处理。

若子表个数为奇数，则最后一个子表无须和其他子表归并（即本趟处理轮空）：若子表个数为偶数，则要注意到最后一对子表中后一个子表区间的上限为n-1。

转载于:https://www.cnblogs.com/yk123/p/8340231.html