排序算法 - 归并排序-蒲公英云

排序算法 - 归并排序

基本思路

归并排序的基本思想是：首先将a[0..n-1]看成是n个长度为1的有序表，将相邻的k（k≥2）个有序子表成对归并，得到n/k个长度为k的有序子表；然后再将这些有序子表继续归并，得到n/k2个长度为k2的有序子表，如此反复进行下去，最后得到一个长度为n的有序表。

若k=2，即归并在相邻的两个有序子表中进行的，称为二路归并排序。若k>2，即归并操作在相邻的多个有序子表中进行，则叫多路归并排序。

例如：

对于{2，5，1，7，10，6，9，4，3，8}序列，其自底向上的排序过程如下图所示，图中方括号内是一个有序子序列。

　　循环log2n次，length依次取1、2、…、log2n。每次执行以下步骤：

　　① 分解：将原序列分解成length长度的若干子序列。

　　② 求解子问题：将相邻的两个子序列调用Merge算法合并成一个有序子序列。

　　③ 合并：由于整个序列存放在数组中a中，排序过程是就地进行的，合并步骤不需要执行任何操作。

自顶向下的排序过程如下图所示

　　① 分解：将序列a[low..high]一分为二，即求mid=(low+high)/2；递归地对两个子序列a[low..mid]和a[mid+1..high]进行继续分解。其终结条件是子序列长度为1（因为一个元素的子表一定是有序表）。

　　② 合并：与分解过程相反，将已排序的两个子序列a[low..mid]和a[mid+1..high]归并为一个有序序列a[low..high]。

算法代码

1 //对区间a[low..mid]和区间a[mid+1..high]进行排序
 2 void Merge(int a[], int low, int mid, int high)
 3 {
 4     int i = low, j = mid + 1;
 5     int k = 0;
 6     int *temp = (int *)malloc((high - low + 1) * sizeof(int));
 7     while (i <= mid && j <= high)
 8         if (a[i] <= a[j]) //将第1子表中的元素放入temp中
 9         {
10             temp[k] = a[i];
11             i++;
12             k++;
13         }
14         else //将第2子表中的元素放入temp中
15         {
16             temp[k] = a[j];
17             j++;
18             k++;
19         }
20     while (i <= mid) //将第1子表余下部分复制到temp
21     {
22         temp[k] = a[i];
23         i++;
24         k++;
25     }
26     while (j <= high) //将第2子表余下部分复制到temp
27     {
28         temp[k] = a[j];
29         j++;
30         k++;
31     }
32     for (k = 0, i = low; i <= high; k++, i++) //将temp复制回a中对应的位置
33         a[i] = temp[k];
34     free(temp); //释放temp所占内存空间
35 }

自底向上的二路归并排序算法

1 void MergePass(int a[], int length, int n) //一趟二路归并排序
 2 {
 3     int i;
 4 
 5     for (i = 0; i + 2 * length - 1 < n; i = i + 2 * length) //归并length长的两相邻子表
 6     {
 7         Merge(a, i, i + length - 1, i + 2 * length - 1);
 8     }
 9 
10     if (i + length - 1 < n) //余下两个子表，后者长度小于length
11     {
12         Merge(a, i, i + length - 1, n - 1); //归并这两个子表
13     }
14 }
15 
16 void MergeSort(int arr[], int n) //二路归并算法
17 {
18     for (int length = 1; length < n; length = 2 * length)
19     {
20         MergePass(arr, length, n);
21     }
22 }

自顶向下的二路归并排序算法

1 void MergeSort(int a[], int low, int high)
 2 //二路归并算法
 3 {
 4     int mid;
 5     if (low < high) //子序列有两个或以上元素
 6     {
 7         mid = (low + high) / 2;          //取中间位置
 8         MergeSort2(a, low, mid);      //对a[low..mid]子序列排序
 9         MergeSort2(a, mid + 1, high); //对a[mid+1..high]子序列排序
10         Merge(a, low, mid, high);     //将两子序列合并，见前面的算法
11     }
12 }