🌈个人主页：秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥 系列专栏：《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482
目录
归并排序
代码实现（递归）
代码实现（非递归）
计数排序（非比较排序）
代码实现
排序算法的复杂度及稳定性
前言
💬 hello! 各位铁子们大家好哇。
今日更新了归并，计数排序的内容
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝
归并排序
归并过程如下：
代码实现（递归）
//时间复杂度：O(N*logN)
//空间复杂度：O(N)
void _MergeSort(int* a,int begin, int end,int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;//[begin,mid][mid+1,end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);//[begin,mid][mid+1,end]归并int begin1 = begin, end1 = mid;int begin2 = mid+1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}分析：因为是使用递归实现，开始时需要创建一个新的数组，且递归需要一个区间，因此我们要另外定义一个函数来实现递归。递归的过程跟二叉树的后序遍历类似，应当注意递归的取值范围和结束条件。归并时，我们把左右两个区间的数从头开始比较，小的就放到tmp数组中。第一个while循环的结束条件是直到某一边的数全部放到tmp就结束。然后就把另一个区间的数，全部依次放入tmp数组中，最后再把tmp的数复制给原数组。
代码实现（非递归）
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;//[begin1,end1][begin2,end2]归并if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}int j = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);
}分析：gap表示每组数的个数。非递归的实现是，开始每组一个数，两两合一，后面比较的过程和递归一样。不过需要注意越界的问题，当end1或者begin2>=n时，就已经越界，这时候就结束循环。当只是end2>=n时，前面数据没有越界，只需要把end2改成n-1即可。一趟归并结束后，gap变为2倍，进行后面的归并，直到gap>=n就停止。
计数排序（非比较排序）
代码实现
void CountSort(int* a, int n)
{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*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail");return;}//统计次数for (int i = 0; i < n; i++){count[a[i] - min]++;}//排序int i = 0;for (int j = 0; j < range; j++){while (count[j]--){a[i++] = j + min;}}
}分析：计数排序主要有两步：
- 统计相同元素出现的次数
- 根据统计的结果将序列回收到原来的序列中
计数排序需要我们新创建一个统计数组，按理来说，数组下标就可以用来当作统计的数，该位置就来存放该数出现的次数。但是，如果要排序的数是从一千多开始的，这样前面的空间就全部浪费了。所以我们采用相对映射的方法。即用待排序的数中，最大的数-最小的数+1就可以得到范围，从而减少空间浪费。接着用原数组的数减去最小值，将该值作为count数组的下标，即相对映射。最后进行排序，记得加回最小值min，这样数据才不会被改变。
排序算法的复杂度及稳定性
稳定性：指的是相同的数，在排序之后的相对位置没有改变。
分析：
时间 空间
- 直接插入：明显的等差数列 无新空间开辟
- 希尔：前面文章已分析 无
- 选择：参考动图 无
- 堆排序：前面文章已分析 无
- 冒泡：等差数列 无
- 快排：二分的思维 看递归深度
- 归并：二分的思维 开辟新的数组
稳定性通过假设来确定，只要有特例是不稳定的，那就是不稳定的。
