归并排序
基本思想
归并思想：
将两个有序数组归并到一起，使其有序；
两个数组中取小尾插到新数组；
归并排序的基本思想：
1.一组数据想要有序，可以先使其左半部分有序，右半部分有序，再利用归并的思想使其整体有序；
2.在将左边的数据变为有序时，又可以分为两部分，先使其左边有序，右边有序，再利用归并想使其整体有序；
3.利用上述思想，将待排数据分为两部分，直到分到每组数据只有一个时，再边排序边返回；
4.这里归并时，需要用到另一个数组，将原数组的数据归并到该数组使其有序，再将数据拷贝回原数组；
图解
代码实现（代码中含分析）
递归实现：
void _MergeSort(int* a, int* tmp ,int begin, int end) { if (begin >= end) return; int mid = (begin + end) / 2; //[begin,mid][mid+1,end] _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid+1,end); //递归到tmp数组 //[begin1,end1][begin2,end2] int begin1 = begin, end1 = mid; int begin2 = mid+1, end2 = end; int i = begin; while (begin1<=end1 && begin2<=end2) { //取小的尾插到tmp数组 if (a[begin1] <= a[begin2]) tmp[i++] = a[begin1++]; else tmp[i++] = a[begin2++]; } //退出循环，有一个区间的元素还未取完 //因为两区间的数据都在本区间已经有序，所以剩余数据直接插入 while (begin2 <= end2) { tmp[i++] = a[begin2++]; } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } //递归完一次后将tmp中数据拷贝回原数组 //注意拷贝回去时，注意拷贝回原位置 memcpy(a+begin, tmp+begin, sizeof(int)*(end-begin+1)); } void MergeSort(int* a ,int begin, int end) { //开辟一个与待排数组同大小的tmp数组，用于归并 int* tmp = (int* )malloc(sizeof(int) * (end - begin + 1)); if (tmp == NULL) { perror("malloc fail"); return; } _MergeSort(a,tmp, begin, end); free(tmp); }
非递归实现：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } //gap等于几就是几个和几个进行归并，不一定是均分 int gap = 1; while (gap < n) { //用i控制区间边界，i+=2*gap时，就进行同层的后组归并 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; //越界处理，如果end1越界，或则begin2越界，那么第二个区间不存在，就不需要归并 if (end1 > n || begin2 >= n) { return; } //如果只是end2越界了，只需要修改边界 if (end2 > n) { end2 = n-1; } //tmp数组的下标 //开始归并 int cur = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) tmp[cur++] = a[begin1++]; else tmp[cur++] = a[begin2++]; } while (begin2 <= end2) { tmp[cur++] = a[begin2++]; } while (begin1 <= end1) { tmp[cur++] = a[begin1++]; } //拷贝回原数组 memcpy(a + i, tmp + i, sizeof(int)*(end2-i+1)); } //一一归完两两归，两两归完四四归…… gap *= 2; } free(tmp); }
性能分析
时间复杂度：O(N*logN)
空间复杂度:O(N)
稳定性：稳定
