民以食为天,我以乐为先
嘴上来的嘘寒问暖,不如直接打笔巨款
一、选择排序
1.直接选择排序
1.1 基本思想
1.2 实现原理
1.3 代码实现
1.4 直接选择排序的特性总结
2.堆排序
跳转链接:数据结构 之 堆的应用
二、完结撒❀
–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–
一、选择排序
1.直接选择排序
1.1 基本思想
original版(原始版):
每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
optimize版(优化版):
每一次从待排序的数据元素中选出最小和最大的两个元素,分别存放在序列的起始位置和队尾位置,直到全部待排序的数据元素排完。
1.2 实现原理
这里我们讲解optimize版
在元素集合array[0]–array[n-1]中选择值最大和值小的数据元素
若最大值不是这组元素中的最后一个元素,则将它与这组元素中的最后一个元素交换,若最小值不是这组元素中的第一个元素,则将它与这组元素中的第一个元素进行交换
在剩余的array[1]–array[n-2]集合中,重复上述步骤,直到集合剩余1个元素或2个元素
因为我们完成一次循环后就可以将数组开头下标加1,结尾下标减一,所以我们需要记录下标实现交换
这里直接说明,按照上述逻辑执行到数组中剩下两个元素的时候可能会出现BUG,当剩下两个下标对应值不符合逻辑时会相互进行两次交换,但这时只进行一次交换就足够
动态图解:
1.3 代码实现
//选择排序 同时选出最大和最小的两个数据
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin<end){int mini = begin, 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 (begin == maxi)//!!!{maxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}
1.4 直接选择排序的特性总结
1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1)
4. 稳定性:不稳定
2.堆排序
跳转链接:数据结构 之 堆的应用
堆排序我之前博客有讲大家直接跳转学习即可
二、完结撒❀
如果以上内容对你有帮助不妨点赞支持一下,以后还会分享更多编程知识,我们一起进步。
最后我想讲的是,据说点赞的都能找到漂亮女朋友❤