目录
1、归并排序
1.1 基本思想
1.2 归并排序递归方式的实现
1.3 归并排序非递归方式的实现
1.4 归并排序的特性总结
2、计数排序
2.1 计数排序基本思想
2.2 计数排序的实现
2.3计数排序的特性总结：
1、归并排序
1.1 基本思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
1.2 归并排序递归方式的实现
归并排序相当于后序遍历，此时可以求出中间位置，控制归并区间
【begin, mid】【mid + 1，end】，递归，直到只有一个值，返回左右区间，对左右区间进行归并，完成后返回，在对右区间递归，递归完后，在返回，归并左右区间。
void _MergeSort(int* a,int begin,int end,int* tmp) {if (begin >= end) {return;}int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);//归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int tmpPos = begin1;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] > a[begin2]) {tmp[tmpPos++] = a[begin2++];}else {tmp[tmpPos++] = a[begin1++];}}while (begin1 <= end1) {tmp[tmpPos++] = a[begin1++];}while (begin2 <= end2) {tmp[tmpPos++] = a[begin2++];}memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));}void MergeSort(int* a, int n) {int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL) {printf("malloc fail\n");exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);}
1.3 归并排序非递归方式的实现
问题分析：
快排类似于先序遍历，先处理 keyi 值，因此可以利用数据结构栈和队列记录后续区间，进行非递归实现，由于其keyi值先进行了处理，并不关注左右起始位置是否记录，依次进行左右位置出栈入栈数据处理，最终获得有序序列。
但是归并排序，在出栈获得序列左右边起始位置后，处理完左边子序列和右边子序列后，仍需对原序列再次进行归并处理，而此时栈内已不再有原序列，因此借助数据结构方式进行实现非递归是困难的。
解决方法：
此时可借助循环，控制起始序列方式，进行处理。此时需要控制其两组数据如果第一组以达到边界，下一组数据便会越界，出现越界访问错误。
void MergeSortNonR(int* a, int n) {assert(a);int* tmp = (int*)malloc(sizeof(int) * n);assert(tmp);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 (end1 >= n) {end1 = n - 1;//begin2、end2 修正为一个不存在的空间begin2 = n;end2 = n - 1;}else if (begin2 >= n) {begin2 = n;end2 = n - 1;}else if (end2 >= n) {end2 = n - 1;}int tmpPos = begin1;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] > a[begin2]) {tmp[tmpPos++] = a[begin2++];}else {tmp[tmpPos++] = a[begin1++];}}while (begin1 <= end1) {tmp[tmpPos++] = a[begin1++];}while (begin2 <= end2) {tmp[tmpPos++] = a[begin2++];}}memcpy_s(a, sizeof(int) * n, tmp, sizeof(int) * n);gap *= 2;}free(tmp);}
1.4 归并排序的特性总结
归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度：O(N*logN)空间复杂度：O(N)稳定性：稳定
2、计数排序
2.1 计数排序基本思想
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
3.局限性：
1）如果是浮点数、字符串就不能排序
2）如果数据范围很大，空间复杂度高，不合适
3）如果使用绝对映射，容易浪费空间，且负数不便于处理
2.2 计数排序的实现
优化，统计最小，将其所计数映射位置减去最小值，可以相对减少空间浪费，同时可以排序负数
void CountSort(int* a, int n) {assert(a);int min = a[0], max = a[0];for (int i = 1; i < n; i++) {if (a[i] < min) {min = a[i];}if (a[i] > max) {max = a[i];}}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);assert(count);memset(count, 0, sizeof(int) * range);//计数for (int i = 0; i < n; i++) {count[a[i] - min]++;}//回写排序int j = 0;for (int i = 0; i < range; i++) {while (count[i]--) {a[j++] = i + min;}}}
2.3计数排序的特性总结：
计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。时间复杂度：O(MAX(N,范围))空间复杂度：O(范围) 比特就业课稳定性：稳定
