个人主页：秦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 || 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]  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. 统计相同元素出现的次数
  2. 根据统计的结果将序列回收到原来的序列中

计数排序需要我们新创建一个统计数组，按理来说，数组下标就可以用来当作统计的数，该位置就来存放该数出现的次数。但是，如果要排序的数是从一千多开始的，这样前面的空间就全部浪费了。所以我们采用相对映射的方法。即用待排序的数中，最大的数-最小的数+1就可以得到范围，从而减少空间浪费。接着用原数组的数减去最小值，将该值作为count数组的下标，即相对映射。最后进行排序，记得加回最小值min，这样数据才不会被改变。

排序算法的复杂度及稳定性

稳定性：指的是相同的数，在排序之后的相对位置没有改变。

分析：

时间空间

  • 直接插入：明显的等差数列无新空间开辟
  • 希尔：前面文章已分析 无
  • 选择：参考动图无
  • 堆排序：前面文章已分析 无
  • 冒泡：等差数列无
  • 快排：二分的思维看递归深度
  • 归并：二分的思维开辟新的数组

稳定性通过假设来确定，只要有特例是不稳定的，那就是不稳定的。