归并排序（MergeSort）——算法导论

一、归并排序

归并排序算法完全遵循分治模式。直观上其操作如下：

• （1）分解：分解等排序的n个元素的序列成各具n/2个元素的两个子序列；

• （2）解决：使用归并排序递归地排序两个子序列；

• （3）合并：合并两个已排序的子序列以产生已排序的答案。

当待排序的序列长度为1时，递归"开始回升"，在这种情况下不根做任何工作，因为长度为1的每个序列都已排好序。

归并排序算法的关键操作是"合并"步骤中两个已排序序列的合并。我们可以通过调用一个辅助过程Merge(A, p, q, r)来完成合并，其中A是一个数组，p、q和r是数组下标，满足 p ≤ q < r。该过程假设子数组A[p..q]和A[q+1..r]都已排好序。它合并这两个子数组形成单一的已排好序的子数组并代替当前的子数组A[p..r]。

二、伪代码

• Merge(A, p, q, r)

Merge(A, p, q, r)
   n1 = q - p + 1//计算左数组的长度
   n2 = r - q//计算右数组的长度
   let L[1..n1] and R[1..n2] be new arrays//分别创建左右数组
   for (i = 1; i <= n1; i++)
       L[i] = A[p+i-1]//初始化左数组，拷贝过程
   for (j = 1; j <= n2; j++)
       R[j] = A[q+j]//初始化右数组，拷贝过程
   i = 1
   j = 1
   k = p
   //merge过程，即两个有序数组合并成一个有序数组，时间复杂度O(m + n)
   while (i <= n1 && j <= n2)
       if (L[i] <= R[j])
           A[k++] = L[i++]
       else A[k++] = R[j++]
   while (i <= n1) A[k++] = L[i++]
   while (j <= n2) A[k++] = R[j++]

image.png

• Merge-sort(A, p, r)

Merge-sort(A, p, r)
1    if (p < r)
2        q = (p + r) / 2
3        Merge-sort(A, p, q)
4        Merge-sort(A, q+1, r)
5        Merge(A, p, q, r)

image.png

三、完整代码

#include<iostream>
using namespace std;

void merge_sort(int a[], int p, int r);
void merge(int a[], int p, int q, int r);

int main()
{
    int a[] = {2, 4, 5, 7, 1, 2, 3, 6};
    merge_sort(a, 0, 7);
    
    for(int i = 0; i < 8; ++i)
    {
        cout<<a[i]<<" ";
    }
}

void merge_sort(int a[], int p, int r)
{
    int q = 0;
    if(p < r)
    {
        q = (p + r) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q + 1, r);
        merge(a, p, q, r);
    }
}

void merge(int a[], int p, int q, int r)//p, q, r all are Array's index
{
    int l1 = q - p + 1;//有序数组的长度 
    int l2 = r - q;//有序数组的长度
    
    //申请新数组
    int left[l1]; 
    int right[l2]; 
    
    //为申请的新数组赋值 
    for(int i = 0; i < l1; ++i)
    {
        left[i] = a[p + i];
    }
    for(int j = 0; j < l2; ++j)
    {
        right[j] = a[q + 1 + j];
    }
    
    //merge:the most important area
    int i = 0, j = 0;
    //先完成其中一个数组到新有序数组的转移 
    while(i < l1 && j < l2)
    {
        if(left[i] <= right[j])
        {
            a[p++] = left[i++];
        }else{
            a[p++] = right[j++];
        }
    }
    
    //将有剩下的数组，一次性转移到新数组 
    while(i < l1)
    {
        a[p++] = left[i++];
    }
    
    while(j < l2)
    {
        a[p++] = right[j++];
    }
}