一、合并排序(Merge Sort) 就是將多個有序數據表合并成一個有序數據表。如果參與合并的只有兩個
有序表，那么稱為二路合并。對于一個原始的待排序序列，往往可以通過分割的方法來歸結為多路合
并排序。
二、一個待排序的原始數據序列進行合并排序的基本思路是，首先將含有n個結點的待排序數據序列看作有n個長度為1的有序子表組成，將他們依次兩兩合并，得到長度為2的若干有序子表;然后，再對這些子表進行兩兩合并，得到長度為4的若干有序子表; .......，重復上述過程，- -直重復到最后的子表
長度為n，從而完成排序過程。
三、例子
***********************************************************************/ // 歸并排序，分治法的典型代表: 將原問題分解了幾個子問題，解決子問題，再合并子問題的解， // 這樣就得到了原問題的解。 // 分治本質上就是把原問題分解為幾個子問題來解決。 // 快速排序也是分治思想來解決。 // // // 歸并排序(merge-sort): // 1. 把一個待排序的數組分解為兩個子數組； // 2. 對兩個子數組進行排序（通過遞歸地調用自己來實現）; // 3. 對兩個已經排序的數組進行合并。 // // 分析： // 1. 一個數組一直分解下去，只到分解成只包含一個元素的子數組為止, 此時自然是有序的； // 2. 歸并排序的重點在于合并，而不是對子數組的排序。（快速排序與它恰恰相反，快速排序的 // 重點是對子數組進行排序，而不是合并，因為它不需要合并了） // //
#include <cstring>
#include <iostream>
typedef bool(*CompareFunc)(int, int); // 下面函數實現合并功能，輸入三個下標參數表示了兩個子數組, :[nStart_, nMiddle)和[nMiddle, nEnd)
void Merge(int array[], int nStart_, int nMiddle_, int nEnd_, CompareFunc comp) {
if (array == nullptr || nStart_ >= nMiddle_ || nMiddle_ >= nEnd_)
return; // 建立一個臨時數組存放中間數據
int _nIndex = 0;
int* _pTempArray = new int[nEnd_ - nStart_]; // 對兩個子數組進行合并
int _nStartChange = nStart_;
int _nMiddleChange = nMiddle_;
while (_nStartChange < nMiddle_ && _nMiddleChange < nEnd_) { // 此處的if中比較語句的安排可以保持穩定排序的特性。
if (comp(array[_nMiddleChange], array[_nStartChange]))
{
_pTempArray[_nIndex] = array[_nMiddleChange]; ++_nMiddleChange; }
else {
_pTempArray[_nIndex] = array[_nStartChange];
++_nStartChange; }
++_nIndex; } // 把不為空的子數組的元素追加到臨時數
if (_nStartChange < nMiddle_) {
memcpy(_pTempArray + _nIndex, array + _nStartChange, sizeof(int) * (nMiddle_ - _nStartChange)); }
else if (_nMiddleChange < nEnd_) {
memcpy(_pTempArray + _nIndex, array + _nMiddleChange, sizeof(int) * (nEnd_ - _nMiddleChange)); }
else { /* do noting */ } // 數據交換 memcpy(array + nStart_, _pTempArray, sizeof(int) * (nEnd_ - nStart_));
delete [] _pTempArray; _pTempArray = nullptr; } // 歸并排序功能實現函數
void MergeSort(int array[], int nStart_, int nEnd_, CompareFunc comp) { // 數組指針為空，或者數組內的個數少于等于1個時，直接返回。
if (nullptr == array || (nEnd_ - nStart_) <= 1) return; // 劃分為兩個子數組并遞歸調用自身進行排序
int _nMiddle = (nStart_ + nEnd_) / 2;
MergeSort(array, nStart_, _nMiddle, comp);
MergeSort(array, _nMiddle, nEnd_, comp); // 合并排序完成的子數組
Merge(array, nStart_, _nMiddle, nEnd_, comp); } // 比較函數
bool less(int lhs, int rhs) {
return lhs < rhs; } // 打印數組函數
void PrintArray(int array[], int nLength_) { if (nullptr == array || nLength_ <= 0)
return; for (int i = 0; i < nLength_; ++i) {
std::cout << array[i] << " "; }
std::cout << std::endl; } /*************** main.c *********************/ >>
int main(int argc, char* argv[]) { // 測試1
int array[10] = {1, -1, 1, 231321, -12321, -1, -1, 123, -213, -13}; PrintArray(array, 10);
MergeSort(array, 0, 10, less); PrintArray(array, 10); // 測試2
int array2[1] = {1}; PrintArray(array2, 1); MergeSort(array2, 0, 1, less);
PrintArray(array2, 1); // 測試3
int array3[2] = {1, -1}; PrintArray(array3, 2);
MergeSort(array3, 0, 2, less);
PrintArray(array3, 2);
return 0; } 
