17网站一起做网店河北,宣传信息网网站规划书,在线商标设计logo免费,中国摄影在线官网Hi~#xff01;这里是奋斗的小羊#xff0c;很荣幸您能阅读我的文章#xff0c;诚请评论指点#xff0c;欢迎欢迎 ~~ #x1f4a5;#x1f4a5;个人主页#xff1a;奋斗的小羊 #x1f4a5;#x1f4a5;所属专栏#xff1a;C语言 #x1f680;本系列文章为个人学习… Hi~这里是奋斗的小羊很荣幸您能阅读我的文章诚请评论指点欢迎欢迎 ~~ 个人主页奋斗的小羊 所属专栏C语言 本系列文章为个人学习笔记在这里撰写成文一为巩固知识二为展示我的学习过程及理解。文笔、排版拙劣望见谅。 目录 前言一、排序算法1、归并排序2、归并非递归3、计数排序4、排序算法复杂度及稳定性分析 总结 前言
本文将继续介绍两种高效的排序算法——归并排序、计算排序。 归并排序在一些场合下如外部排序非常有效当数据量非常大且无法全部加载到内存时可以将其分块处理。 而计数排序是一种非比较排序算法适用于特定范围内的整数排序在许多数情况下计算排序可以秒杀我们介绍过的所有排序。 一、排序算法
1、归并排序
| 算法思路
归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列间段有序。 动图演示 代码实现
//子函数
void _MergeSort(int* arr, int* tmp, int begin, int end)
{if (begin end){return;}int mid (begin end) / 2;//[begin, mid] [mid 1, end]_MergeSort(arr, tmp, begin, mid);_MergeSort(arr, tmp, mid 1, end);int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[i] arr[begin1];}else{tmp[i] arr[begin2];}}while (begin1 end1){tmp[i] arr[begin1];}while (begin2 end2){tmp[i] arr[begin2];}memcpy(arr begin, tmp begin, (end - begin 1) * sizeof(int));
}//归并排序
void MergeSort(int* arr, int n)
{int* tmp (int*)malloc(n * sizeof(int));if (tmp NULL){perror(malloc fail);return;}_MergeSort(arr, tmp, 0, n - 1);free(tmp);tmp NULL;
}归并排序有几个需要特别注意的点
分割区间一定要按[begin, mid] [mid 1, end]分不然会导致死循环memcpy(arr begin, tmp begin, (end - begin 1) * sizeof(int));一定是归并一组拷贝一组因为如果存在越界的情况还整体拷贝肯定会出错归并排序算法的时间复杂度是O(N*logN)空间复杂度是O(N). 2、归并非递归 递归改非递归有两种办法一种是用栈模拟一种是用循环处理。 上篇文章中快排非递归我们是利用栈实现的但是归并的非递归使用栈解决不了因为快排的递归过程是一个类似前序遍历的过程而归并是一个类似后续的过程它是先将区间循环分割成只有一个数据再反向进行归并栈是做不到这一点的。 所以归并的非递归我们考虑用循环来实现。
我们可以直接将原数组一一归并再二二归并再四四归并…… //归并非递归
void MergeSortNonR(int* arr, int n)
{int* tmp (int*)malloc(n * sizeof(int));if (tmp NULL){perror(malloc fail);return;}//gap是每组归并数据的个数int gap 1;while (gap n){//i表示每组归并的起始位置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;int j i;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[j] arr[begin1];}else{tmp[j] arr[begin2];}}while (begin1 end1){tmp[j] arr[begin1];}while (begin2 end2){tmp[j] arr[begin2];}//memcpy(arr i, tmp i, (end2 - i 1) * sizeof(int));}gap * 2;//一一归二二归四四归}free(tmp);tmp NULL;
}memcpy(arr i, tmp i, (end2 - i 1) * sizeof(int));for (int i 0; i n; i 2 * gap)int begin2 i gap, end2 i 2 * gap - 1;
但是上面的代码还不完善仅限2的次方个数的数据归并如果不是2的次方个数则会越界。越界无非下面三种情况
[begin1, end1] [begin2, end2 ][begin1, end1] [begin2 , end2 ][begin1, end1 ] [begin2 , end2 ]
其中第二种和第三种可以归为一类因为begin2越界说明我们需要排序的数据已经排好序了越界的部分不是我们的区间我们根本不用管直接退出循环就行了。 而第一种情况只需要处理一下就好让end2变成n - 1就行了。
代码示例
//归并非递归
void MergeSortNonR(int* arr, int n)
{int* tmp (int*)malloc(n * sizeof(int));if (tmp NULL){perror(malloc fail);return;}//gap是每组归并数据的个数int gap 1;while (gap n){//i表示每组归并的起始位置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 (begin2 n){break;}//begin2没越界end2越界只需要修正一下就好if (end2 n){end2 n - 1;}int j i;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[j] arr[begin1];}else{tmp[j] arr[begin2];}}while (begin1 end1){tmp[j] arr[begin1];}while (begin2 end2){tmp[j] arr[begin2];}//归并一次拷贝一次memcpy(arr i, tmp i, (end2 - i 1) * sizeof(int));}gap * 2;}free(tmp);tmp NULL;
}3、计数排序
计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。其排序步骤为 1. 统计相同元素出现的次数将统计到的次数作为count数组以元素值对应下标处的值 2. 根据统计的结果将序列回收到原来的序列中 3. 动态开辟的count数组要初始化为全0 本质 利用count数组的自然序号排序
为了保证开辟大小合适的count数组我们可以用待排数据中最大值减最小值加一的方法来确定一个合适的范围max - min 1。 然后再用元素值减去最小值的方法来和count数组形成相对映射关系arr[i] - min得到的值是几就在数组对应下标位置递增。 最后一步排序的时候不要忘了在原数组中插入的值还要加上最小值并且count数组中下标对应位置的值是几就循环几次如果对应位置是0的话说明原数组没有这个下标数就不进入循环。
大致思想如下 代码如下
//计数排序
void CountSort(int* arr, int n)
{int min arr[0];int max arr[0];for (int i 1; i n; i){if (arr[i] arr[min]){min arr[i];}if (arr[i] arr[max]){max arr[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[arr[i] - min];}//排序int j 0;for (int i 0; i range; i)//遍历count数组{while (count[i]--){arr[j] i min;}}free(count);count NULL;
}计数排序的时间复杂度为O(N range)相比较前几种排序算法计数排序效率是非常高的但速度快的同时也有空间消耗计数排序的空间复杂度为O(range)所以计数排序也算是拿空间换时间。
计数排序虽然相对其他排序算法快且稳定但也存在一些缺陷
只能排整数不能排浮点数要求数据比较集中不然空间开销太大 4、排序算法复杂度及稳定性分析
稳定性 如果待排序数据中有多个相同的的数据若经过排序这些相同的数据相对位置保持不变则称这种排序算法是稳定的。
排序算法时间复杂度空间复杂度稳定性插入排序O(N^2)O(1)稳定希尔排序O(N^1.3)O(1)不稳定选择排序O(N^2)O(1)不稳定堆排序O(N*logN)O(1)不稳定冒泡排序O(N^2)O(1)稳定快速排序O(N*logN)O(logN)不稳定归并排序O(N*logN)O(N)稳定计数排序O(N range)O(range)稳定 总结
这些排序算法各有千秋在某些特定的情况下某个算法的性能尤为突出在一些复杂的排序中为了追求性能往往使用混合排序这使得性能大大提高。
