2.1 初级排序算法
Robert Sedgewick Kevin Wayne
作为对排序算法领域的第一次探索，我们将学习两种初级的排序算法以及其中一种的一个变体。深入学习这些相对简单的算法的原因在于：第一，我们将通过它们熟悉一些术语和简单的技巧；第二，这些简单的算法在某些情况下比我们之后将会讨论的复杂算法更有效；第三，以后你会发现，它们有助于我们改进复杂算法的效率。
2.1.1 游戏规则
我们关注的主要对象是重新排列数组元素的算法，其中每个元素都有一个主键。排序算法的目标就是将所有元素的主键按照某种方式排列（通常是按照大小或是字母顺序）。排序后索引较大的主键大于等于索引较小的主键。元素和主键的具体性质在不同的应用中千差万别。在 Java 中，元素通常都是对象，对主键的抽象描述则是通过一种内置的机制（请见 2.1.1.4 节中的 Comparable 接口）来完成的。
“排序算法类模版”中的 Example 类展示了我们的习惯约定：我们会将排序代码放在类的 sort() 方法中，该类还将包含辅助函数 less() 和 exch()（可能还有其他辅助函数）以及一个示例用例 main()。Example 类还包含了一些早期调试使用的代码：测试用例 main() 将标准输入得到的字符串排序，并用私有方法 show() 打印字符数组的内容。我们还会在本章中遇到各种用于比较不同算法并研究它们的性能的测试用例。为了区别不同的排序算法，我们为相应的类取了不同的名字，用例可以根据名字调用不同的实现，例如 Insertion.sort()、Merge.sort()、Quick.sort() 等。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了选择排序、插入排序和希尔排序这三种初级排序算法的基本概念和实现框架。选择排序通过选择剩余元素中的最小者进行排序，具有运行时间和输入无关、数据移动最少的特点。插入排序则是逐个将元素插入到已有序部分中，对某些非随机数组非常有效。希尔排序是一种基于插入排序的快速排序算法，通过对数组中任意间隔为 h 的元素进行排序，最终用插入排序将局部有序的数组排序。文章通过代码示例和图表展示了排序算法的实际应用和实现细节，分析了这三种排序算法的时间复杂度和性能特点。希尔排序在处理大规模乱序数组时表现出色，对于中等大小的数组也具有可接受的运行时间，且代码量小，不需要额外内存空间。总的来说，本文以简洁清晰的语言介绍了初级排序算法的基本概念和实现框架，适合初学者快速了解和入门。文章还提到了一些练习和测试用例，帮助读者更好地理解和评估排序算法的性能特性。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《算法（第 4 版）》
《算法（第 4 版）》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论