排序_6.归并排序

归并排序

简介：

前面介绍的插入排序，交换排序和选择排序这三类排序算法都是将无序的记录序列按关键字的大小排成一个有序序列．
而归并排序则是将两个或两个以上的有序序列合并成一个有序序列的过程．

归并排序（Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

算法描述：

首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

• eg:

  a: 1 3 5 7 9 
  b: 2 4 6 8 10 12 14
      //1 和 2, 比, 小，将 1 放入c,
      //3 和 2, 比, 大，将 2 放入c,
      //3 和 4, 比, 小，将 3 放入c,
      ....
  c > 1 2 3 4 5 6 7 8 9 10 12 14
  //我们在合并这两个序列时，每次只用比较当前ａ序列第一个和当前ｂ序列第一个的大小，谁小就先放入有序序列中，当ａ比较完后，直接将ｂ剩余的依次放入有序序列即可．

//将有序数组a[]和b[]合并到c[]中  
void MemeryArray(int a[], int n, int b[], int m, int c[])  
{  
    int i, j, k;  
  
    i = j = k = 0;  
    while (i < n && j < m)  
    {  
        if (a[i] < b[j])  
            c[k++] = a[i++];  
        else  
            c[k++] = b[j++];   
    }  
  
    while (i < n)  
        c[k++] = a[i++];  
  
    while (j < m)  
        c[k++] = b[j++];  
}

//可以看出合并有序数列的效率是比较高的，可以达到O(n)。

//解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

//可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递[归]的分解数列，再合[并]数列就完成了[归并]排序。

归并排序视频演示　
备份链接1

过程演示：

首先：
       a[0]  a[1]  a[2]  a[3]  a[4]  a[5]  a[6]  a[7]  a[8]  a[9]
　　　　 4     2     8     6     0     5     1     7     3     9
　　　　 //一开始，分成两拨．
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]
　　　　 4     2     8     6     0    　　　　　 5     1     7     3     9
　　　　 //一开始，再分别分成两拨．
       a[0]  a[1] 　　　　　 a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]
　　　　 4     2    　　　　　 8     6     0    　　　　　 5     1     7     3     9
　　　　 //对于a[0]和a[1]而言，分开后不会再细分．
　　　　 //对a[0]和a[1]排序
       a[0]  a[1] 　　　　　 a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]
　　　　 2     4    　　　　　 8     6     0    　　　　　 5     1     7     3     9　　　　 
　　　　 //对于a[2]a[3]a[4]进行细分，分为a[2]以及a[3]a[4],
       a[0]  a[1] 　　　　　 a[2]      a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]
　　　　 2     4    　　　　　 8         6     0    　　　　　 5     1     7     3     9　　　　 
　　　　 //对于a[3]和a[4]而言，分开后不会再细分．
　　　　 //对a[3]和a[4]排序
       a[0]  a[1] 　　　　　 a[2]      a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]
　　　　 2     4    　　　　　 8         0     6    　　　　　 5     1     7     3     9　　
　　　　 //因其a[2]及a[3]a[4]已经有序，合并a[2]与a[3]a[4]，
       a[0]  a[1] 　　　　　 a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]
　　　　 2     4    　　　　　 0      6     8    　　　　　 5     1     7     3     9　　
　　　　 //因其a[0]a[1]与a[2]a[3]a[4]已经有序，合并a[0]a[1]与a[2]a[3]a[4]，
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]
　　　　 2     4     0     6     8    　　　　　 5     1     7     3     9　　得：
　　　　 0     2     4     6     8    　　　　　 5     1     7     3     9　　   
　　　　 //此时，我们已经将左边的元素全部有序，而且我们归并都是对有序的进行操作．
　　　　 //同理，我们将对右边的元素也进行同样的操作，使其有序，再进行两个有序序列的归并操作．

　　　　 //首先，将右边a[5]a[6]a[7]a[8]a[9]分成两拨：a[5]a[6]和a[7]a[8]a[9]：
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]　  　a[7]  a[8]  a[9]
　　　　 0     2     4     6     8    　　　　　 5     1    　　 7     3     9　　   
　　　　 //对于a[5]和a[6]而言，分开后不会再细分．
　　　　 //对a[5]和a[6]排序
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]     a[7]  a[8]  a[9]
　　　　 0     2     4     6     8    　　　　　 1     5        7     3     9　　
　　　　 //对于a[7]a[8]a[9]进行细分，分为a[7]以及a[8]a[9],
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]     a[7]    a[8]  a[9]
　　　　 0     2     4     6     8    　　　　　 1     5        7       3     9　
　　　　 //对于a[8]和a[9]而言，分开后不会再细分．
　　　　 //对a[8]和a[9]排序
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]     a[7]    a[8]  a[9]
　　　　 0     2     4     6     8    　　　　　 1     5        7       3     9　　　　
　　　　 //因其a[7]及a[8]a[9]已经有序，合并a[7]与a[8]a[9]，
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]     a[7]  a[8]  a[9]
　　　　 0     2     4     6     8    　　　　　 1     5        3     7     9　　　　　　　　 
　　　　 //因其a[5]a[6]与a[7]a[8]a[9]已经有序，合并a[5]a[6]与a[7]a[8]a[9]，
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]
　　　　 0     2     4     6     8    　　　　　 1     5     3     7     9　　得：
　　　　 0     2     4     6     8    　　　　　 1     3     5     7     9　　 　
　　　　 //此时，我们已经将左边和右边的的元素全部分别有序，这时我们可以归并两个有序的序列．
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]　　　　
　　　　 0     2     4     6     8    　　　　　 1     3     5     7     9　
　　　　 i　   　　　　　　　　　　　　　　　　　　　　j     
　　　　 //具体如下：
　　　　 //i指向第一个有序序列头，j指向第二个有序序列头～
　　　　 //比较，如果a[i] < a[j] , b[k++] = a[i], i++
　　　　 //比较，如果a[i] > a[j] , b[k++] = a[j], j++　　　　 
　　　　 // i = 0, j = 5 ,0 == a[i] < a[j] == 1  //b[0] = a[i] = 0
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]　　　　
　　　　 0     2     4     6     8    　　　　　 1     3     5     7     9　
　　　　 i　   　　　　　　　　　　　　　　　　　　　　j     
       b[0]  b[1]  b[2]  b[3]  b[4] 　　　　　 b[5]  b[6]  b[7]  b[8]  b[9]
       0
　　　　 // i = 1, j = 5 ,2 == a[i] > a[j] == 1 // b[0] = a[j] = 1
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]　　　　
　　　　 0     2     4     6     8    　　　　　 1     3     5     7     9　
　　　　 i　   　　　　　　　　　　　　　　　　　　　　j     
       b[0]  b[1]  b[2]  b[3]  b[4] 　　　　　 b[5]  b[6]  b[7]  b[8]  b[9]
　　　　 0　　　1　　　　　　　　　　 
　　　　 // i = 1, j = 6 ,2 == a[i] < a[j] == 3 // b[0] = a[i] = 2
       a[0]  a[1]  a[2]  a[3]  a[4] 　　　　　 a[5]  a[6]  a[7]  a[8]  a[9]　　　　
　　　　 0     2     4     6     8    　　　　　 1     3     5     7     9　
　　　　 i　   　　　　　　　　　　　　　　　　　　　　j     
       b[0]  b[1]  b[2]  b[3]  b[4] 　　　　　 b[5]  b[6]  b[7]  b[8]  b[9]
　　　　 0　　　1　　　2
　　　　 ...
　　　　 //最后，可得：
       b[0]  b[1]  b[2]  b[3]  b[4]  b[5]  b[6]  b[7]  b[8]  b[9]
　　　　  0　　　1　　　2     3     4     5     6     7     8     9
　　　　//我们在整个过程中，为了合并两个有序的序列，拆分到最小再依次合并，这个就是归并过程．

算法思想：

　
归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

• 迭代法
  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

• 递归法
  原理如下（假设序列共有n个元素）：

1. 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
2. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素
3. 重复步骤2，直到所有元素排序完毕

程序代码：

按照此定义，我们很容易写出归并排序的程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void Merge(int *a, int size);
void merge(int *a, int left, int right, int *temp);
void merge_sort(int *a,int left,int mid,int right,int * temp);

void Merge(int *a, int size)
{
    int *temp = (int *)malloc(sizeof(int)*size);
    if(NULL == temp)
    {
         fprintf("the memory is full.\n");
         exit(1);
    }
    merge(a, 0, size -1,temp);   //temp相当于c[]
    free(temp);      
}
void merge(int *a, int left, int right, int *temp)
{
    int mid = 0;
    if(NULL == a )
    {
        return;
    }
    if(left < right)
    {
        mid = left + ((right-left)>>1);
        merge(a, left, mid, temp);       //先递归分解
        merge(a, mid+1, right, temp);    //递归分解
        merge_sort(a, left, mid, right, temp);  //合并两有序序列
    }

}
void merge_sort(int *a,int left,int mid,int right,int * temp)
{//合并两个有序的序列
    int i =left;
    int j =mid+1;
    int k = 0;
    int m = mid;
    int n = right;
    while(i <= m && j <= n)
    {
        if(a[i] < a[j])
        {
            temp[k++] = a[i++];
        }
        else
        {
            temp[k++] = a[j++];
        }
    }
    while( i <= m)
    {
        temp[k++] = a[i++];
    }
    while( j <= n)
    {
        temp[k++] = a[j++];
    }
    memcpy(a + left, temp ,sizeof(int)*k);
}

功能检测

• 检测代码：

  int main()
  {
      int i =0;
      int a[] = {3,0,1,8,7,2,5,4,6,9};
      int n = sizeof(a)/sizeof(a[0]);
    
      Merge(a, n);
      
      printf("\n");
      for(i = 0; i < n ; ++i)
      {
          printf("%3d",a[i]);
      }
      printf("\n");
      return 0;
  }

• 运行结果：

root@aemonair:~/Desktop# cc.sh Merge_Sort.c
Compiling ...
-e CC      Merge_Sort.c -g -lpthread
-e         Completed .
-e         Fri Jul 29 17:14:57 CST 2016
root@aemonair:~/Desktop# ./Merge_Sort 

  0  1  2  3  4  5  6  7  8  9

总结：

归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(NlogN)。
因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(NlogN)的几种排序方法（快速排序，归并排序，希尔排序）也是效率比较高的。

---