阿土伯 是做网站的吗,儿童教育机构网页设计素材,wordpress 创意,企业密信#x1f525;博客主页#xff1a;小王又困了
#x1f4da;系列专栏#xff1a;数据结构
#x1f31f;人之为学#xff0c;不日近则日退
❤️感谢大家点赞#x1f44d;收藏⭐评论✍️ 目录
一、排序的概念及其分类
#x1f4d2;1.1排序的概念
#x1f4d2;1.2排序…
博客主页小王又困了
系列专栏数据结构
人之为学不日近则日退
❤️感谢大家点赞收藏⭐评论✍️ 目录
一、排序的概念及其分类
1.1排序的概念
1.2排序的分类
二、插入排序
2.1直接插入排序
2.1.1直接插入排序的思想
2.1.2排序步骤
2.1.3代码实现
2.1.4直接插入排序的特点
2.2希尔排序
2.2.1希尔排序法的基本思想
2.2.2排序步骤
2.2.3代码实现
2.2.4希尔排序的特点
三、选择排序
3.1直接选择排序
3.1.1直接选择排序的思想
3.1.2排序步骤
3.1.3代码实现
3.1.4直接选择排序的特点
3.2堆排序
3.2.1堆排序的思想
3.2.2排序步骤
3.2.3代码实现
3.2.4堆排序的特点 ️前言 排序是我们数据结构学习中很重要的章节我们在生活中买东西都会挑选更好的点外卖会选评分高的等等这些都需要用到排序。接下来我们将会学习常见的排序算法。 一、排序的概念及其分类
1.1排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排 序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 1.2排序的分类 二、插入排序
2.1直接插入排序
2.1.1直接插入排序的思想 把待排序的数据按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的数据插入完为止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想。 注意数组中除了第一个元素默认有序其余所有元素都看作待插入数据。 2.1.2排序步骤
将有序数据的最后一个元素的下标记为 end则第一个待插入元素的下标为 end1记作 tmp将 tmp 与有序数据从后向前依次比较如果 tmp a[end]就将 a[end] 向后移动end--再去找下一位进行比较直到 tmp a[end] 或者 end 0将 tmp 插入到 end1 的位置重复步骤就可以实现排序
2.1.3代码实现
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];}else{break;}--end;}a[end 1] tmp;}
} 2.1.4直接插入排序的特点 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定 2.2希尔排序
2.2.1希尔排序法的基本思想 先选定一个整数把待排序文件中所有记录分成个组所有距离为3的数据分在同一组内并对每一组内的数据进行排序。然后重复上述分组和排序的工作。当距离1时所有数据在统一组内排好序。 希尔排序分为两步 预排序直接插入排序 当元素集合越接近有序直接插入排序的效率很高希尔排序就是通过预排序使元素集合接近有序再进行直接插入排序这样大大提高了效率。 2.2.2排序步骤
选取一个合适的 gap 作为间距将间距为 gap 的数据分为一组分成 gap 组每一组数据都进行直接插入排序使数据接近有序不断缩小间距当 gap1 时数据进行直接插入排序实现排序
2.2.3代码实现
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}
将 igap 改为 i 将分组排序变为多组并排减少了循环。 gap gap / 3 1 的目的是保证 gap 最后的值为1.
2.2.4希尔排序的特点 希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算。空间复杂度O(1)稳定性不稳定 三、选择排序
3.1直接选择排序
3.1.1直接选择排序的思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 3.1.2排序步骤
先遍历一遍数组找到最大的数和最小的数记住它们的下标将最小的数交换到数组的左边最大的数交换到数组的右边beginend--重复上述步骤即可实现排序
3.1.3代码实现
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int min begin, max begin;for (int i begin 1; i end; i){if (a[min] a[i]){min i;}if (a[max] a[i]){max i;}}Swap(a[min], a[begin]);if (max begin){max min;}Swap(a[max], a[end]);begin;end--;}
}
我们要注意当 a[max] 在数组元素的第一个进行 Swap(a[min], a[begin]) 后最大的元素的位置就发生了改变要及时修改 max。
3.1.4直接选择排序的特点 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定 3.2堆排序
3.2.1堆排序的思想 堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。 3.2.2排序步骤
将待排序的数据构造成一个大堆当前堆的根节点堆顶就是该组数组中最大的元素将堆顶元素和最后一个元素交换将剩下的节点重新构造成一个大堆重复步骤2每次循环构建都能找到当前堆中的最大值并通过交换的方式把它放到该大堆的尾部直至所有元素全部有序
3.2.3代码实现
void HeapSort(int* a, int n)
{//第一步建大堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//第二步堆删除思想进行排序依次选数调堆for (int i n - 1; i 0; i--){Swap(a[0], a[i]);AdjustDown(a, i , 0);}
}
void AdjustDown(HPDataType* a, int n, int parent)
{//默认左孩子是较小的int child parent * 2 1;while (child n){// 找出小的那个孩子if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);// 继续往下调整parent child;child parent * 2 1;}else{break;}}
}3.2.4堆排序的特点 堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定 本次的内容到这里就结束啦。希望大家阅读完可以有所收获同时也感谢各位读者三连支持。文章有问题可以在评论区留言博主一定认真认真修改以后写出更好的文章。你们的支持就是博主最大的动力。
