37｜简单选择排序与堆排序：多趟排序与利用有序完全二叉树进行排序
王健伟
你好，我是王健伟。
前面我们一起学习了交换类排序，也就是在排序过程中对元素进行两两比较并交换位置。其中，最知名的交换类排序算法——冒泡排序、快速排序我们都已经讲过了。这次，我们学习一个新的排序种类——选择类排序。
选择类排序是一种基于比较的排序算法，他的基本思想就是每一趟在待排序的元素中选取关键字最小（或最大）的元素加入到有序子序列中。而简单选择排序则是选择类排序中的一种。
什么是简单选择排序？
简单选择排序英文名称是 Simple Selection Sort。简单选择排序需要进行多趟排序才能得到最终结果。它的基本思想是每趟从待排序的元素中找出值最小的元素放到已排序序列的末尾，然后再从未排序的元素中选择最小的元素，继续放到已排序的序列的末尾，直到所有元素都被排序完毕。
简单选择排序过程演示
以图形来说明会比较直观，如图 1 所示：
图1 简单选择排序示意图
图 1 左上侧是待排序的 10 个元素，我们以从小到大排序来说明。
第一趟排序：从待排序的元素中找出值最小的元素和下标为 0 的元素做交换，这样下标为 0 的位置所保存的就是最小值的元素，此时无需再理会下标为 0 的位置。
第二趟排序：抛开下标为 0 位置的元素，从其余元素中找出值最小的元素和下标为 1 的元素做交换，这样下标为 1 位置所保存的就是剩余待排序元素中最小值的元素，此时无需再理会下标为 1 的位置。
第三趟排序：抛开下标为 0、1 位置的元素，从其余元素中找出值最小的元素和下标为 2 的元素做交换，这样下标为 2 位置所保存的就是剩余待排序元素中最小值的元素，此时无需再理会下标为 2 的位置。
如此重复，第九趟排序：抛开下标为 0、1、2、3、4、5、6、7 位置的元素，从其余元素中找出值最小的元素和下标为 8 的元素做交换，这样下标为 8 位置所保存的就是剩余待排序元素中最小值的元素。此时，下标为 9 的元素自然就是值最大的元素。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
堆排序算法是一种高效的排序方法，通过构建大顶堆来实现排序。文章详细介绍了堆排序的基本思想和实现方式，包括建堆和排序过程。通过对比简单选择排序和堆排序的特点，读者可以更好地理解多趟排序和利用有序完全二叉树进行排序的原理和实现方式。堆排序的实现代码和执行结果也得到了清晰的展示。此外，文章还提到了堆中元素的插入和删除操作，为读者提供了更全面的了解。堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，并且是不稳定的排序算法。文章还对堆排序的效率进行了分析，指出了在排序的数据记录比较多时采用堆排序的优势。总体而言，本文内容详实，适合读者快速了解堆排序算法的原理和实现方式。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论