归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

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

  1 // 参考白话经典算法之归并排序的思想
  2 #include <stdio.h>
  3 #include <malloc.h>
  4 
  5 void SwapValue(int *OperatorA, int *OperatorB)
  6 {
  7     if ((NULL == OperatorA) || (NULL == OperatorB))
  8     {
  9         printf ("Invalid Parameter(s)!\n");
 10         return;
 11     }
 12 
 13     if ((*OperatorA) != (*OperatorB))
 14     {
 15         *OperatorA ^= *OperatorB;
 16         *OperatorB ^= *OperatorA;
 17         *OperatorA ^= *OperatorB;
 18     }
 19 }
 20 
 21 void CombineArray(int *a, int fStart, int fEnd, int sStart, int sEnd)
 22 {
 23     if ((NULL == a) || (fStart < 0) || (fStart > fEnd) || (sStart < 0) || (sStart > sEnd))
 24     {
 25         printf ("Invalid Parameter(s)!\n");
 26         return;
 27     }
 28 
 29     int *pTemp = NULL;
 30 
 31     if (NULL == (pTemp = (int *)malloc((fEnd - fStart + 1 + sEnd - sStart + 1) * sizeof(int))))
 32     {
 33         printf ("Fail to malloc space to pTemp!\n");
 34         return;
 35     }
 36 
 37     if (fStart > sStart)
 38     {
 39         SwapValue (&fStart, &sStart);
 40         SwapValue (&fEnd, &sEnd);
 41     }
 42 
 43     int i = fStart;
 44     int j = sStart;
 45     int k = 0;
 46 
 47     while ((i <= fEnd) && (j <= sEnd))
 48     {
 49         if (a[i] < a[j])
 50         {
 51             pTemp[k++] = a[i++];
 52         }
 53         else
 54         {
 55             pTemp[k++] = a[j++];
 56         }
 57     }
 58 
 59     while (i <= fEnd)
 60     {
 61         pTemp[k++] = a[i++];
 62     }
 63 
 64     while (j <= sEnd)
 65     {
 66         pTemp[k++] = a[j++];
 67     }
 68 
 69     k = 0;
 70     for (i = fStart; i <= fEnd; ++i)
 71     {
 72         a[i] = pTemp[k++];
 73     }
 74 
 75     for (i = sStart; i <= sEnd; ++i)
 76     {
 77         a[i] = pTemp[k++];
 78     }
 79 }
 80 
 81 void MergeSort(int *a, int nLow, int nHigh)
 82 {
 83     if ((NULL == a) || (nLow < 0) || (nLow > nHigh))
 84     {
 85         printf ("Invalid Parameter(s)!\n");
 86         return;
 87     }
 88 
 89     if (nLow < nHigh)
 90     {
 91         int nMid = (nLow + nHigh) >> 1;
 92 
 93         // 左边有序
 94         MergeSort (a, nLow, nMid);
 95 
 96         // 右边有序
 97         MergeSort (a, nMid + 1, nHigh);
 98 
 99         // 合并有序
100         CombineArray (a, nLow, nMid, nMid + 1, nHigh);
101     }
102 }
103 
104 int main(void)
105 {
106     int a1[9] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
107 
108     MergeSort (a1, 0, 8);
109 
110     for (int i = 0; i < 9; ++i)
111     {
112         printf ("%d ", a1[i]);
113     }
114 
115     printf ("\n");
116 
117     return 0;
118 }