【算法】排序——归并排序和计数排序

=========================================================================

主页点击直达：个人主页

我的小仓库：代码仓库

C语言偷着笑：C语言专栏

数据结构挨打小记：初阶数据结构专栏

Linux被操作记：Linux专栏

LeetCode刷题掉发记：LeetCode刷题

算法头疼记：算法专栏

=========================================================================

前言

归并排序

递归实现代码

非递归实现归并排序

计数排序

排序算法复杂度及稳定性分析

前言

上两篇文章讲解了插入排序、选择排序以及交换排序，每种类型的排序大类下都有一到两种排序，今天给大家带来的是归并排序，和前面几种排序一样都属于比较排序中的一种，是通过比较数组中的元素来实现排序的，还给大家带来一种非比较排序计数排序，让我们开始今天的排序之吧！！！

归并排序

基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序核心步骤：

这张图片看起来是不是非常眼熟？和上篇文章的快速排序非常的相似，归并排序也是一种类似与二叉树结构的排序，我们也是使用递归的思想来实现，归并排序是先将一整个乱序的数组分成若干个数组（极限情况下每一个数字可以看成一个数字）然后将每个有序的数组进行有序的合并，通过多次合并最终成为一个有序的数组。

递归实现代码

void _MergerSort(int* a, int* tmp,int begin, int end )
{if (begin >= end){return;}int mid = (end + begin) / 2;//[begin,mid] [mid+1,end]_MergerSort(a, tmp, begin, mid);_MergerSort(a, tmp, mid + 1, end);//归并到tmp数组int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int index = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1]< a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = 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){perror("malloc failed");return;}//不可以自己递归，因为每次都要开辟新的空间_MergerSort(a, tmp, 0, n - 1);free(tmp);
}

递归实现排序确实优点难理解，大家可以根据我画的图和代码结合起来自己多多画图理解。

非递归实现归并排序

上篇文章的快速排序我们可以使用栈数据结构来实现，但是归并排序我们很难用栈数据结构来实现，普通的方法实现起来也不难，递归是将一整个数组分成若干数组（极限情况下每一个数字是一个数组）来实现分治，最后归并。我们逆向着来，根据控制数组的下标来直接实现归并。

非递归实现代码
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc failed");return;}int gap = 1;while (gap < n){//11归并 22归并 44归并for (int i = 0; i < n;i=i+2*gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int index = i;//防止越界，防止只能排序个数为2的倍数//当begin2大于等于数组个数时end2一定越界了if (begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}memcpy(a + i, tmp + i, (end2-i+1) * sizeof(int));}gap *= 2;}free(tmp);
}
在对数组进行操作时我们一定要注意越界问题，下面是解决上面问题的图解。

因此当end2越界时但begin2没越界时我们将end2调到n-1的位置时候就可以了。

归并排序的特性总结：
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

操作步骤：
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

开辟一个新的数组利用数组下标统计原数组中每个数出现的次数，因为时从小到大统计的因此直接将每个数字放在原数组中即可，如果原数组全是大数据呢？开辟空间的大小是个问题，因此我们先遍历数组找到最大值和最小值做差作为我们开辟空间大小的基准，每个数的代表下标=数组元素-最小值。

实现代码
void CoutSort(int* a, int n)
{int max = a[0];int min = a[0];//遍历数组求出最大值for (int i = 0; i < n; i++){if (max < a[i]){max = a[i];}if (min > a[i]){min = a[i];}}//根据最大值和最小值的差值开辟空间int range = max - min+1;int* cout = (int*)malloc(sizeof(int) * range);if (cout == NULL){perror("malloc failed");return;}//将开辟的空间所有值置为0memset(cout, 0, sizeof(int) * range);for (int i = 0; i < n; i++){//计数//防止数值过大cout[a[i] - min]++;//3 4 5 6 7 8 9 10//0 1 2 3 4 5 6 7//2 1 1 2 1 1 2 1}int j = 0;for (int i = 0; i < range; i++){while (cout[i]--){a[j++] = i + min;}}
}
计数排序的特性总结：
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)