一、基本思想
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有 序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。 歸并排序核心步驟：
?二、歸并排序的特性總結
1. 歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(N)
4. 穩定性：穩定
三、歸并排序
1、遞歸實現
1.1 實現思想
使用遞歸方法來實現歸并排序，這其中不止包含了遞歸這個思想，還使用了分治的理念。
其原理就是把待排序數組分成兩個子序列，再分別把兩個子序列分成其對應的子序列，直到每個子序列都只有唯一的一個數據時就停止遞歸。然后分別對子序列進行排序，最后將排序好的子序列合并起來。
一個小tip：就是歸并排序歸并數據的過程中我們需要額外開辟一個空間來存放中間數據，如果在原數組中進行歸并的話會造成數據的覆蓋或者導致數據錯亂！！！
1.2 具體實現
// 時間復雜度O(N*logN) 空間復雜度:O(N)
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (end <= begin){return;}int mid = (begin + end) / 2;// [begin, mid][mid+1, end]_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);// 歸并到tmp數據組，再拷貝回去// a->[begin, mid][mid+1, end]->tmpint begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;//尾插tmp數組下標int index = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}//拷貝回原數組memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); //+begin是因為歸并的數組下標不一定從0開始
}//歸并排序
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);
}?2、 非遞歸實現
2.1 實現思想
相較于遞歸實現，非遞歸實現采用與希爾排序相似的方法。就是使用gap來確定歸并區間并進行歸并。
?2.2 具體實現
//非遞歸--歸并排序(防止下標越界)
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// 如果第二組不存在，這一組不用歸并了if (begin2 >= n){break;}// 如果第二組的右邊界越界，修正一下if (end2 >= n){end2 = n - 1;}// [begin1,end1] [begin2,end2] 歸并int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}// 拷貝回原數組memcpy(a + i, tmp + i, (end2 - i) * sizeof(int));}gap *= 2;}free(tmp);
}2.3 關于非遞歸實現歸并排序的一些細節
?在我們要用非遞歸來實現歸并排序時需要注意的是用gap來確定歸并區間的界限會不會造成數組越界的問題。
上面這張圖是我們用gap來區分歸并的區間，這種方法有可能會造成第二個數組全部越界或者第二個數組的end越界。但我們要注意的是第一個數組的開頭begin1永遠不可能越界，因為begin1 == i，而循環條件中 i < n。
如下圖所示：
所以我們就只需要加兩個判定條件即可
1、判斷begin2是否 >= 數組長度n，如果大于等于就直接跳出循環不用再進行歸并
2、判斷end2是否 >= 數組長度n，如果大于等于就修正end2，使其 == 數組結束位置 n -?1
方法)
