归并排序（merge sort）

女爷i 2022-03-29 06:12 171阅读 0赞

**归并排序****（Merge sort）**是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。(出自[维基百科][Link 1])

<table style="text-align:left;text-transform:none;text-indent:0px;font:13px/1.5em sans-serif;letter-spacing:normal;color:#000000;margin-left:1em;clear:right;word-spacing:0px;border:#aaaaaa 1px solid;"> 
 <tbody> 
  <tr> 
   <th style="text-align:left;vertical-align:top;">平均时间复杂度</th> 
   <td style="vertical-align:top;"><img style="vertical-align:middle;" src="http://upload.wikimedia.org/math/f/2/9/f296a521bff060cd02c3ef6ee7931dd7.png" alt="\Theta(n\log n)"></td> 
  </tr> 
 </tbody> 
</table>

Conceptually ,归并算法的基本步骤如下所示：

1）使用递归(recursion)方法把未排序的序列分成n个子序列，每个子序列只包含一个元素（一个元素被认为是有序的）；

2）使用归并操作重复合并子序列产生新的序列，直到只剩下一个序列，那么这个序列就是有序的。

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

### 归并操作算法描述 ###

归并操作的过程如下：

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

**代码实现**

#include <stdio.h>
    #include <stdlib.h>
    
    void mergeSort(int arr[], int left, int right);
    void Merge(int arr[], int left, int middle, int right);
    
    
     int main()
     {
         int i;
         int arr[]={
        5,2,6,3,9,10,8};
         int len = sizeof(arr)/sizeof(int);
    
         mergeSort(arr,0,len-1);
         for (i = 0; i <= len-1; i++)
         {
             printf("%3d",arr[i]);
         }
         return 0;
    
     }
    
     void mergeSort(int arr[], int left, int right)
     { //对数组进行迭代排序
         int middle;
         
         if(left >= right) return;
         
         middle = (left + right)/2;
         mergeSort(arr,left,middle);
         mergeSort(arr,middle+1,right);
         Merge(arr,left,middle,right);  
         
     }
    
     void Merge(int arr[], int left, int middle, int right)
     {  //归并操作
         
         int length = right - left + 1;
         int *pArr;
         int beginA = left,beginB = middle + 1;  //设置两个标志，分别指向两个已排序序列的起始位置
         int nCount = 0,i;
         
         pArr = (int *)malloc(sizeof(int)*length);  //开辟空间
         if (pArr == NULL)
         {
             printf("malloc error\n");
             return;
         }
         
         while (beginA <= middle)
         {
             if (arr[beginA] > arr[beginB])
             {
                 pArr[nCount++] = arr[beginB++];
             }
             if (arr[beginA] < arr[beginB])
             {
                 pArr[nCount++] = arr[beginA++];
             }
             if (beginB > right) break;
         }
         
         while (beginA <= middle)
         {
             pArr[nCount++] = arr[beginA++];
         }
         
         while (beginB <= right)
         {
             pArr[nCount++] = arr[beginB++];
         }
         
         for (i = 0; i < length; i++)   //把排序好的部分移回arr数组中
         {
             arr[left++] = pArr[i];
         }
         free(pArr);
     }
    
    2013/6/15 12:34

[Link 1]: http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F