«

[排序算法]归并排序(C++实现)

归并排序是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。常见的归并排序有两路归并排序(Merge Sort),多相归并排序(Polyphase Merge Sort),Strand排序(Strand Sort)。下面介绍第一种:

1.两路归并排序
最差时间复杂度:O(nlogn)
平均时间复杂度:O(nlogn)
最差空间复杂度:O(n)
稳定性:稳定

两路归并排序(Merge Sort),也就是我们常说的归并排序,也叫合并排序。它是建立在归并操作上的一种有效的排序算法,归并操作即将两个已经排序的序列合并成一个序列的操作。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

归并操作的基本步骤如下:

  1. 申请两个与已经排序序列相同大小的空间,并将两个序列拷贝其中;
  2. 设定最初位置分别为两个已经拷贝排序序列的起始位置,比较两个序列元素的大小,依次选择相对小的元素放到原始序列;
  3. 重复2直到某一拷贝序列全部放入原始序列,将另一个序列剩下的所有元素直接复制到原始序列尾。

设归并排序的当前区间是R[low..high],分治法的三个步骤是:

  1. 分解:将当前区间一分为二,即求分裂点
  2. 求解:递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序;
  3. 组合:将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。

递归的终结条件:子区间长度为1(一个记录自然有序)。

算法示意图:

代码实现:

// a表示需要排序的整数数组
// p表示需要排序的数列第一个数字在数组中的位置
// r表示需要排序的数列最后一个数字在数组中的位置。
void Merge(int *a, int p, int q, int r)  
{
    int n1 = q-p+1;
    int n2 = r-q;
    int *L = new int[n1+1];
    int *R = new int[n2+1];
    int i, j, k;

    for (i=0; i<n1; i++){
        L[i] = a[p+i];
    }
    for (j=0; j<n2; j++){
        R[j] = a[q+j+1];
    }
    L[n1] = 10000000;
    R[n2] = 10000000;

    for (i=0, j=0, k=p; k<=r; k++)
    {
        if (L[i]<=R[j])
        {
            a[k] = L[i];
            i++;
        }else{
            a[k] = R[j];
            j++;
        }
    }

    delete []L;
    delete []R;
}

void MergeSort1(int *a, int p, int r)  
{
    if (p<r)
    {
        int q = (p+r)/2;
        MergeSort1(a, p, q);
        MergeSort1(a, q+1, r);
        Merge(a, p, q, r);
    }
}

虽然插入排序的时间复杂度为O(n^2),归并排序的时间复杂度为O(nlogn),但插入排序中的常数因子使得它在n较小时,运行得要更快一些。因此,在归并排序算法中,当子问题足够小时,采用插入排序算法就比较合适了。

代码实现:

void MergeSort2(int *a, int p, int r)  
{
    if ((r-p)>=50) // 小于50个数据的数组进行插入排序
    {
        int q = (p+r)/2;
        MergeSort2(a, p, q);
        MergeSort2(a, q+1, r);
        Merge(a, p, q, r);
    }else
    {
        InsertionSort(a+p, r-p+1);
    }
}

MergeSort1与MergeSort2算法排序时间实验结果比较:

数据量      | 1K      | 10K    | 100K   | 1000K  | 10000K |
MergeSort1 | 0.001s  | 0.008s | 0.065s | 0.552s | 5.875s |  
MergeSort2 | <0.001s | 0.001s | 0.021s | 0.219s | 2.317s |  
分享