归并排序（merge-sort）

一，归并排序

归并排序是建立在归并操作上的一种排序算法，它采用了分治法的思想，是一种稳定的排序算法，而且归并排序的速度仅次

于快速排序。时间复杂度：O（n*logn），最坏的情况：O（n*logn），空间复杂度：O(n)。从数据就可以看出：归并排序比快速

排序快很多，同样为稳定排序。

算法的思想：先将一个无序的数组不断的分解成2部分直至不能分解为止，这时每一个层次都有两部分，然后再一层一层的地

柜将前后两部分合并好来，最初的递归就是将两个单独的数排好序，后面的递归就是在前面递归的进一步的加大加深。

例子： 6 2 4 7 3 8

第一趟排序： 2 6 4 3 7 8

第二趟排序： 2 4 6 3 7 8

第三趟排序： 2 3 4 6 7 8

示例代码：

#include <stdio.h>
void Merge(int  arrayA[], int first, int mid, int last, int  arrayB[])   //将分解的数组进行归并
{
     int n = mid, m = last;
     int i = first, j = mid+1;
     int k = 0;
     while(i<=n && j<=m)                 //进行归并操作
     {
          if(arrayA[i] <= arrayA[j])
               arrayB[k++] = arrayA[i++];
          else
               arrayB[k++] = arrayA[j++];
     }
     while(i<=n)
     {
          arrayB[k++] = arrayA[i++];
     }
     while(j<=m)
     {
          arrayB[k++] = arrayA[j++];
     }
     for(i = 0; i<k; i++)                     //将归并好的数组按照一定的次序放回原来的数组
          arrayA[first+i] = arrayB[i];
}
void MergeSort(int  arrayA[], int first, int last, int  arrayB[])    //将数组进行分解操作
{
     if(first < last)
     {
          int mid = (first+last)/2;
          MergeSort(arrayA, first, mid, arrayB);
          MergeSort(arrayA, mid+1, last, arrayB);
          Merge(arrayA, first, mid, last, arrayB);
     }
}
int main()
{
     int n;
     int arrayA[100], arrayB[100];
     printf("请输入要排序数组的大小：");
     scanf("%d", &n);
     printf("请输入数组中各个数：");
     for(int i = 0; i<n; i++)
          scanf("%d", &arrayA[i]);
     MergeSort(arrayA, 0, n-1, arrayB);
     for(int i = 0; i<n; i++)
          printf("%d  ",arrayB[i]);
     printf("
");
     for(int i = 0; i<n; i++)
         printf("%d  ",arrayA[i]);
}

二，用插入排序来优化归并排序

归并排序可以使得效率达到O(n*logn)，但我们可以利用插入排序将归并排序进一步优化，优化后的时间复杂度

为：O(n*log(n/k))，k的取值范围为：10到20左右，就是将数组切分成小于10个数来进行插入排序，这样可以进一步

减短归并排序的开销。因为在插入排序中，当n比较小时速度还是很快的。

优化后的代码：

#include <stdio.h>
void Merge(int arrayA[], int first, int mid, int last, int arrayB[])   //将排序好的部分数组进行归并
{
    int n = mid, m = last;
    int i = first, j = mid+1;
    int k = 0;
    while(i<=n && j<=m)
    {
        if(arrayA[i] <= arrayA[j])
            arrayB[k++] = arrayA[i++];
        else
            arrayB[k++] = arrayA[j++];
    }
    while(i<=n)
    {
        arrayB[k++] = arrayA[i++];
    }
    while(j<=m)
    {
        arrayB[k++] = arrayA[j++];
    }
    for(i = 0; i<k; i++)
        arrayA[first+i] = arrayB[i];
}
void InsertionSort(int arrayA[], int first, int last)      //进行插入排序操作
{
    int mark;
    int i, j;
    for(i = first+1; i<=last; i++)
    {
        mark = arrayA[i];
        j = i-1;
        while(j>=first && mark<arrayA[j])
        {
            arrayA[j+1] = arrayA[j];
            j--;
        }
        arrayA[j+1] = mark;
    }
}
void MergeSort(int arrayA[], int first, int last, int arrayB[])   //将数组进行分割，分割成每一块小于10个数
{
    if((last-first)>10)       //若大于10个数则进行分割
    {
        int mid = (first+last)/2;
        MergeSort(arrayA, first, mid, arrayB);
        MergeSort(arrayA, mid+1, last, arrayB);
        Merge(arrayA, first, mid, last, arrayB);
    }
    else                         //若小于10个数则进行插入排序
    {
        InsertionSort(arrayA, first, last);
    }
}
int main()
{
    int n;
    int arrayA[100], arrayB[100];
    printf("请输入要排序数组的大小：");
    scanf("%d", &n);
    printf("请输入数组中的各个数：");
    for(int i = 0; i<n; i++)
        scanf("%d", &arrayA[i]);
    MergeSort(arrayA, 0, n-1, arrayB);
    for(int i = 0; i<n; i++)
        printf("%d  ", arrayA[i]);
    return 0;
}