开发网站的意义,网页免费模板,湖州建设网站,广州网站优化平台W...Y的主页 #x1f60a;
代码仓库分享 #x1f495; #x1f354;前言#xff1a; 上篇博客我们讲解了非常重要的快速排序#xff0c;相信大家已经学会了。最后我们再学习一种特殊的排序手法——归并排序。话不多说我们直接上菜。
目录
归并排序
基本思想
递归思路…
W...Y的主页
代码仓库分享 前言 上篇博客我们讲解了非常重要的快速排序相信大家已经学会了。最后我们再学习一种特殊的排序手法——归并排序。话不多说我们直接上菜。
目录
归并排序
基本思想
递归思路 算法思路
代码思路以及实现
非递归思路
算法思路编辑
代码思路以及实现
归并排序的特性总结
非比较排序
计数排序
算法思路以及代码实现
计数排序总结
八大排序总结 归并排序
基本思想
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤
递归思路 算法思路 归并排序的思路就是先分再合。 1.我们将一个数组进行平分然后继续递归进行更细小的划分秒直到每个数组如同一个数组时然后再进行返回。 2.返回时每个小数组中的数必须排列为有序的数。 3.然后合并每个小数组然后继续进行排序直到数组有序即可。 我们可以展示一下归并排序的动图让大家更好的理解 代码思路以及实现
不难看出递归的过程非常像二叉树的后序遍历数组如果左右区间都无序我们进行向下递归直到有序再返回合并。(只有一个数时我们可以看作其有序)
所以我们的代码思路也与二叉树后序代码有点相似。 具体思路 1.创建一个与原数组相同空间大小的数组用来拷贝已经排序好的子数组。 2.创建一个函数来进行递归调用如果使用有malloc的函数递归时会重复开辟空间导致空间浪费函数的参数传入原数组新建数组与排序的起始位置与终止位置。 3.进行数组的递归调用。 4.创建临时遍历begin1、end1、begin2、end2控制子数组的区间然后进行比较排序成为有序子数组。 5.将有序的数组先放入新数组中然后拷贝到原数组中进行覆盖变为有序数组即可。 代码实现
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (end begin)return;int mid (end begin) / 2;//[begin, min][min 1, end]_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid 1, end);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 fail);return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);
}易错点 在拷贝时我们不一定是从头进行拷贝拷贝的都是与数组头的相对位置所以在参数中我们要添加begin。 非递归思路
为什么要进行非递归与快速排序的原因相同就是因为递归占用的是栈空间而栈空间的内存非常小所以我们要进行非递归的算法学习。而非递归与斐波那契切数的思路相当就是已知前两个然后去推后面的数而归并的非递归也是如此将思路进行正向整理从最小的开始进行即可。
算法思路 我们先创建一个gap数进行子数组大小记录gap为1则进行一一比较排序gap 2则进行两个两个比较以此类推。后面与递归思路基本相同。
代码思路以及实现 实现思路 1.模拟递归最后一层进行比较排序。 2.每次gap * 2. 3.当gapn时停止递归。 4.将有序数组进行拷贝 代码实现
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;int index i;if (begin2 n){break;}if (end2 n){end2 n - 1;}printf([%d][%d][%d][%d] , begin1, end1, begin2, end2);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));}printf(\n);gap * 2;}free(tmp);
} 注意当我们进行排序时我们就会进行分组。但是有些数组中的元素个数不一定够组成一组。当我们一个一个进行分组时我们可以将所以元素分为一组但是当个数为奇数时我们进行归并后进行两个一组时就会有一个剩余。四个进行分组时也会有其中一组或两组没有分满的情况所以我们如果不进行控制就会出现数组越界的情况程序就会报错。
我们将每一次的递归区间进行打印即可看出区间越界的问题 但是我们进行修改后就不会出现越界情况 其中越界的有end2、begin2、end1。begin1是不会越界的。那我们将其进行边界的修正这样即不会影响正常的归并也不会将出错的情况算入其中。 处理方法 如果end2越界则将其修改为n-1。 如果begin2和end1越界则将其修正为不存在的区间不存在则直接跳出了归并的过程。 共用三种出界情况. 但是如果begin2越界或end1越界程序直接break即可其实直接写begin2就可以涵盖所有情况所以我们可以将begin1n省略。 归并排序的特性总结 1. 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度O(N*logN) 3. 空间复杂度O(N) 4. 稳定性稳定 非比较排序
非比较排序的思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤 1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中
计数排序
计数排序是一种比较新奇的排序思路它没有两两数之间的比较而是统计每个数出现的次数然后进行排序。
这种方法适合于数目比较集中的情况且整型数据。
时间复杂度O(N range) 空间复杂度O(range)
算法思路以及代码实现 思路 1.先寻找数组中出现的最大数与最小数。 2.开辟最大数-最小数差值的数组空间大小 3.遍历数组统计数组中每个数出现的次数放入开辟好的数组中去。 4.遍历新建数组中的内容每个数出现几次就在旧数组中打印几次覆盖掉原数组的内容。 代码实现
void CountSort(int* a, int n)
{int min a[0], max a[0];for (size_t i 0; 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*)malloc(sizeof(int) * range);printf(range:%d\n, range);if (count NULL){perror(malloc fail);return;}memset(count, 0, sizeof(int) * range);// 统计数据出现次数for (int i 0; i n; i){count[a[i] - min];}// 排序int j 0;for (int i 0; i range; i){while (count[i]--){a[j] i min;}}
} 注意我们统计的数组不一定从0开始所以我们在统计出数组中的最小值时一定要在默认在每个下标后加最小值才可以得到原数组中的内容。
计数排序总结
计数排序的特性总结 1. 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 2. 时间复杂度O(MAX(N,范围)) 3. 空间复杂度O(范围) 八大排序总结
总结几种常见易错且重要的排序在这里就讲述完了我们要合理引用发挥出排序的优点舍弃其缺点。最后我将这些排序的复杂度以及稳定性进行了总结我们可以适度观看。 以上就是本次博客全部内容感谢大家观看
