1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 //合并排序的合并程序他合并數組nData中位置為[nP,nM) 和[nM,nR).這個是更接近標準的思路
  5 bool MergeStandard(int nData[], int nP, int nM, int nR)
  6 {
  7     int n1 = nM - nP;        //第一個合并數據的長度
  8     int n2 = nR - nM;        //第二個合并數據的長度
  9 
 10     int *pnD1 = new int[n1 + 1];        //申請一個保存第一個數據的空間
 11     int *pnD2 = new int[n2 + 1];        //申請二個保存第一個數據的空間
 12 
 13     for (int i = 0; i < n1; ++i)        //復制第一個數據到臨時空間里面
 14     {
 15         pnD1[i] = nData[nP + i];
 16     }
 17     pnD1[n1] = INT_MAX;                    //將最后一個數據設置為最大值(哨兵)
 18 
 19     for (int i = 0; i < n2; ++i)        //復制第二個數據到臨時空間里面
 20     {
 21         pnD2[i] = nData[nM + i];
 22     }
 23     pnD2[n2] = INT_MAX;                    //將最后一個數據設置為最大值(哨兵)
 24     
 25     n1 =  n2 = 0;
 26 
 27     while(nP < nR)
 28     {
 29         nData[nP++] = pnD1[n1] <  pnD2[n2] ? pnD1[n1++] : pnD2[n2++];        //取出當前最小值到指定位置
 30     }
 31 
 32     delete pnD1;
 33     delete pnD2;
 34     return true;
 35 }
 36 
 37 //合并排序的合并程序他合并數組nData中位置為[nP,nM) 和[nM,nR).
 38 bool Merge(int nData[], int nP, int nM, int nR)
 39 {
 40     //這里面有幾個注釋語句是因為當時想少寫幾行而至。看似短了，其實運行時間是一樣的，而且不易閱讀。
 41 
 42     int nLen1 = nM - nP;        //第一個合并數據的長度
 43     int nLen2 = nR - nM;         //第二個合并數據的長度
 44     int* pnD1 = new int[nLen1];    //申請一個保存第一個數據的空間
 45     int* pnD2 = new int[nLen2];   //申請一個保存第一個數據的空間
 46     
 47     int i = 0; 
 48     for ( i = 0; i < nLen1; ++i)        //復制第一個數據到臨時空間里面
 49     {
 50         pnD1[i] = nData[nP + i];
 51     }
 52 
 53     int j = 0;
 54     for (j = 0; j < nLen2; ++j)        //復制第二個數據到臨時空間里面
 55     {
 56         pnD2[j] = nData[nM + j];
 57     }
 58 
 59     i = j = 0;
 60     while (i < nLen1 && j < nLen2)
 61     {
 62         //nData[nP++] = pnD1[i] < pnD2[j] ? pnD1[i++] : pnD2[j++];        //取出當前最小值添加到數據中
 63         
 64         if (pnD1[i] < pnD2[j])        //取出最小值，并添加到指定位置中，如果pnD1[i] < pnD2[j]
 65         {
 66             nData[nP] = pnD1[i];    //取出pnD1的值，然后i++，定位到下一個個最小值。
 67             ++i;
 68         }
 69         else                        //這里同上
 70         {
 71             nData[nP] = pnD2[j];
 72             ++j;
 73         }
 74         ++nP;                        //最后np++，到確定下一個數據
 75     }
 76 
 77     if (i < nLen1)                    //如果第一個數據沒有結束（第二個數據已經結束了）
 78     {
 79         while (nP < nR)                //直接把第一個剩余的數據加到nData的后面即可。
 80         {
 81             //nData[nP++] = pnD1[i++];
 82             nData[nP] = pnD1[i];
 83             ++nP;
 84             ++i;
 85         }
 86     }
 87     else                            //否則（第一個結束，第二個沒有結束）
 88     {
 89         while (nP < nR)                //直接把第一個剩余的數據加到nData的后面即可。
 90         {
 91             //nData[nP++] = pnD2[j++];
 92             nData[nP] = pnD2[j];
 93             ++nP;
 94             ++j;
 95         }
 96     }
 97 
 98     delete pnD1;        //釋放申請的內存空間
 99     delete pnD2;
100 
101     return true;
102 }
103 
104 //合并的遞歸調用,排序[nBegin, nEnd)區間的內容
105 bool MergeRecursion(int nData[], int nBegin, int nEnd)
106 {
107     if (nBegin >= nEnd - 1)        //已經到最小顆粒了,直接返回
108     {
109         return false;
110     }
111 
112     int nMid = (nBegin + nEnd) / 2;            //計算出他們的中間位置，便于分治
113     MergeRecursion(nData, nBegin, nMid);    //遞歸調用，合并排序好左邊一半
114     MergeRecursion(nData, nMid, nEnd);        //遞歸調用，合并排序好右邊一半
115     //Merge(nData, nBegin, nMid, nEnd);        //將已經合并排序好的左右數據合并，時整個數據排序完成
116     MergeStandard(nData, nBegin, nMid, nEnd);//(用更接近標準的方法合并)
117 
118     return true;
119 }
120 
121 //合并排序
122 bool MergeSort(int nData[], int nNum)
123 {
124     return MergeRecursion(nData, 0, nNum);        //調用遞歸，完成合并排序
125 }
126 
127 int main()
128 {
129     int nData[10] = {4,10,3,8,5,6,7,4,9,2};    //創建10個數據，測試
130 
131     MergeSort(nData, 10);
132     for (int i = 0; i < 10; ++i)        
133     {
134         printf("%d ", nData[i]);
135     }
136 
137     printf("\n");
138     system("pause");
139     return 0;
140 }
141