个人主页:欢迎大家光临——>沙漠下的胡杨
各位大帅哥,大漂亮
如果觉得文章对自己有帮助
可以一键三连支持博主
你的每一分关心都是我坚持的动力
☄: 本期重点:选择排序
希望大家每天都心情愉悦的学习工作。
今天我们进入排序章节的选择我排序篇,我们本篇主要是讲解简单选择排序和堆排序的回顾。
选择排序的整体思想:简单选择排序:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的 数据元素排完 。
代码实现:1. 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
2. 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换
3. 在剩余的array[i]--array[n-2](array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素
就是找到一些数中的最小的放在前面,然后找到次小的放在最小的后面,遍历一个个比较交换,我们看下示意图:
我们还可以在这个算法的基础上优化,我们可以一次选出最大的和最小的两个数,把最大的放在最后,最小的放在最前面。
直接选择排序分析:代码整体比较简单,我们要注意的是:
我们要注意,如果是下面的情况呢?
void SelectSort(int* a, int n)//选择排序 { assert(a); int begin = 0;//开始下标 int end = n - 1; //结束下标 while (begin < end)//如果两者没有相遇或错过就继续 { int mini = begin;//最小值下标 int maxi = begin;//最大值下标 for (int i = begin + 1; i <= end; ++i) { if (a[i] < a[mini]) { mini = i; } if (a[i]>a[maxi]) { maxi = i; } } Swap(&a[begin], &a[mini]); //如果交换完,刚好交换的位置是下一次要交换的,我们就手动改变一下 if (maxi == begin) { maxi = mini; } Swap(&a[end], &a[maxi]); ++begin; --end; } }
堆排序: 堆排序思路:1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1)
4. 稳定性:不稳定
堆排序:堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。
堆排序的分析:我们在二叉树的章节中讲的详细啦,就不在赘述啦,请见 堆排序。
1. 堆排序使用堆来选数,效率就高了很多。
2. 时间复杂度:O(N*logN)
3. 空间复杂度:O(1)
4. 稳定性:不稳定



