归并排序（merge-Sort）

是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

---

归并操作

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列${{(6，202，100，301，38，8，1)}}$
初始状态：$6,202,100,301,38,8,1$
第一次归并后：${(6,202)}$,${(100,301)}$,${(8,38)}$,${(1)}$，比较次数：$3$；
第二次归并后：${(6,100,202,301)}$，${(1,8,38)}$，比较次数：$4$；
第三次归并后：${$1,6,8,38,100,202,301)}$,比较次数：$4$；
总的比较次数为：$3+4+4=11$；
逆序数为$14$；

---

算法描述

归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

---

比较

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要。归并排序的比较次数小于快速排序的比较次数，移动次数一般多于快速排序的移动次数。

---

复杂度

时间复杂度为$O(n\log^2n) $这是该算法中最好、最坏和平均的时间性能。
空间复杂度为$ O(n)$
比较操作的次数介于 $\frac{n\log n}{2}$ 和$n\log n – n + 1$。
赋值操作的次数是$(2n\log n)$。归并算法的空间复杂度为：$O (n)$
归并排序比较占用内存，但却是一种效率高且稳定的算法。

---

下面就是源代码了

源代码

//归并排序（从小到大） 
#include <stdio.h>
int a[3001000];   //在主函数外定义数组 
int c[3001000];

void merge_sort(int left,int right)   //定义归并函数"merge_sort" 
{
    if ( left == right ) return;   //判断是否只有一个数 
    int mid = ( left + right ) / 2;   //取一个中间数 
    merge_sort(left, mid);      //这两行将输入的数列强行二分 
    merge_sort(mid + 1,right);
    int i = left;   //把开始和中间的值保存在别的变量中 
    int j = mid + 1;
    int len = 0;
    while (i <= mid && j <= right)    //在范围内判断前后两数的大小 
    {
        if (a[i] < a[j])    //判断大小 大到小"<",小到大">"！！！ 
        {
            c[len] = a[i];    //如果条件成立（这里是后数比前数小）把后面的值赋到前面 
            len++;   //表示判断过一遍 
            i++;    //当i与下面的j其中有一个不满足上面while后的条件则跳出循环，表示排序完成 
        }
        else
        {
            c[len] = a[j];  //不成立就不变 
            len++;
            j++;
        }
    }
    for (;i<=mid;i++)    //下面几个for循环把排序好的数记录下来 
    {
        c[len] = a[i];      
        len++;           //挨个赋值 
    }
    for (;j<=right;j++)
    {
        c[len] = a[j];
        len++;
    }
    for (int ii = left; ii <= right ;ii++)
        a[ii] = c[ii - left];
}


int main()    //主函数 
{
    int n;
    printf("输入数字个数：\n");
    scanf("%d",&n);   //输入要排序的数字个数 
    printf("输入%d个数:\n",n);
    for (int i = 0 ; i < n ; i++)   //循环输入 
        scanf("%d",&a[i]);
    merge_sort(0,n-1);   //调用归并排序函数"merge_sort" 
    for (int i = 0 ; i < n ; i++)   //循环输出
    {
        if(i!=0)     //第一个数前面不加空格 
        printf(" ");
        printf("%d",a[i]);
    }
    return 0;
}

---

希望大家喜欢这篇文章！！！
如有问题请留言，谢谢！！！