山东查询网站备案,网站流量用完了,分销渠道,服务之家网站推广公司主页点击直达#xff1a;个人主页
我的小仓库#xff1a;代码仓库
C语言偷着笑#xff1a;C语言专栏
数据结构挨打小记#xff1a;初阶数据结构专栏
Linux被操作记#xff1a;Linux专栏
LeetCode刷题掉发记#xff1a;LeetCode刷题
算法头疼记#xff1a;算法专栏…
主页点击直达个人主页
我的小仓库代码仓库
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] [mid1,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;ii2*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-i1) * 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 - min1;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(范围) 排序算法复杂度及稳定性分析 经典的几大排序本片文章就彻底完结了大家可以根据这三篇文章对排序有新的认识。希望大家阅读完可以有所收获同时也感谢各位看官的三连支持。文章有问题可以直接留言我一定及时认真的修改。
