本篇博文旨在介绍排序中的归并排序；介绍了归并排序的基本思想以及算法的执行步骤；并从时间复杂度和空间复杂度进行分析；最后用代码实现了归并排序

归并排序

基本思想

归并排序的主要思想，是将两个有序的数组进行合并，从而得到有序的序列

算法步骤

1、将数组按二分法分成两个区间，然后继续将区间进行递归划分，直到区间只有一个数为止

2、将相邻两个区间进行排序，使之合并成为有序的区间

3、返回上一层递归，继续合并，直到全部被合并

算法图解

时间复杂度和空间复杂度

由图可知，递归了logN层，每层排序了N常亮个数

所以其时间复杂度为O(N* logN)

由于申请了N个大小的空间进行临时存放，所以空间复杂度为O(1)

代码实现

#pragma once //归并排序 //时间复杂度:O(N* logN) //思想: //运用归并的思想，将两个有序的链表和为一起 //需要一个数组来保存合并后的值 //也有二分的思想 //进行排序 void _Marge(int* a, int* tmp, int left, int mid, int right) { int bgn1 = left; int end1 = mid; int bgn2 = mid + 1; int end2 = right; int index = left; //进行归并排序,放入到tmp中 while (bgn1 <= end1 && bgn2 <= end2) { if (a[bgn1] < a[bgn2]) tmp[index++] = a[bgn1++]; else tmp[index++] = a[bgn2++]; } //归并时，必有一个数组是没有放完的，需要判别是bgn1还是bgn2 //然后将其放入tmp while (bgn1 <= end1) tmp[index++] = a[bgn1++]; while (bgn2 <= end2) tmp[index++] = a[bgn2++]; //将tmp中的元素放回数组a中 for (size_t i = left; i <= right; ++i) a[i] = tmp[i]; } //从排序的控制 void _MargeSort(int* a,int* tmp ,int left, int right) { //如果元素不大于一个，不用进行排序 if (left >= right) return; int mid = left + ((right - left) >> 1); //元素不止一个，需要递归排序 _MargeSort(a, tmp, left, mid); _MargeSort(a, tmp, mid+1, right); //进行排序 _Marge(a, tmp, left, mid, right); } //主排序，申请和释放tmp void MargeSort(int* a, size_t n) { assert(a); int* tmp = new int[n]; //调用归并 _MargeSort(a, tmp, 0, n-1); delete[] tmp; } void TestMargeSort() { int a[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 }; MargeSort(a, sizeof(a) / sizeof(a[0])); Print(a, sizeof(a) / sizeof(a[0])); }