归并排序
2021-09-20 21:34 作者:氢氟酸_Official | 我要投稿
归并排序（英语：merge sort）是一种采用了分治思想的排序算法。
所谓分治，即为分而治之。首先把一个序列分成两部分，然后对这两部分序列分别进行排序。
那末如何对这两部分序列进行排序呢？请重新阅读上面这句话。
说白了，我们递归的把一个数列进行分解，直到分割出的最小单元元素数量<=2时。举个例子，有一个11个元素的数列。
11 = 5+6 = 2 + 3 + 3 + 3 = 2 + 2 +1 +2 + 1 + 2 + 1
接下来模仿上面分解的过程进行合并，在合并的过程中完成排序。这样，排序好2个和1个元素的单元，然后把合并成3个和4个元素的单元，这时这样的单元已经部分有序，接下来继续排序3个和4个元素的单元，然后再合并成……以此类推，直到合并成一个长度为n的单元。
这样我们可以得到归并排序的工作过程：
三个步骤：
将数列划分为两部分；
递归地分别对两个子序列进行归并排序；
合并两个子序列。
不难发现，归并排序的前两步都很好实现，关键是如何合并两个子序列。注意到两个子序列在第二步中已经保证了都是有序的了，第三步中实际上是想要把两个 有序 的序列合并起来。
归并排序的性质：
归并排序是一种稳定的排序算法。
归并排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为O(n log n) 。
归并排序的空间复杂度为 O(n)
C++代码实现↓
链接：https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/1639015?fr=aladdin
链接：https://oi-wiki.org/basic/merge-sort/
#include <stdlib.h>#include <stdio.h>void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){ int i = startIndex, j=midIndex+1, k = startIndex; while(i!=midIndex+1 && j!=endIndex+1) { if(sourceArr[i] > sourceArr[j]) tempArr[k++] = sourceArr[j++]; else tempArr[k++] = sourceArr[i++]; } while(i != midIndex+1) tempArr[k++] = sourceArr[i++]; while(j != endIndex+1) tempArr[k++] = sourceArr[j++]; for(i=startIndex; i<=endIndex; i++) sourceArr[i] = tempArr[i];}//内部使用递归void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex){ int midIndex; if(startIndex < endIndex) { midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int MergeSort(sourceArr, tempArr, startIndex, midIndex); MergeSort(sourceArr, tempArr, midIndex+1, endIndex); Merge(sourceArr, tempArr, startIndex, midIndex, endIndex); }}int main(int argc, char * argv[]){ int a[8] = {50, 10, 20, 30, 70, 40, 80, 60}; int i, b[8]; MergeSort(a, b, 0, 7); for(i=0; i<8; i++) printf("%d ", a[i]); printf("\n"); return 0;}推荐例题：
洛谷P1309，P1908，P1774等
