排序就是将一组对象按照某种逻辑顺序重新排列的过程。比如，信用卡账单中的交易是按照日期排序的——这种排序很可能使用了某种排序算法。在计算时代早期，大家普遍认为30%的计算周期都用在了排序上。如果今天这个比例降低了，可能的原因之一是如今的排序算法更加高效，而并非排序的重要性降低了。现在计算机的广泛使用使得数据无处不在，而整理数据的第一步通常就是进行排序。所有的计算机系统都实现了各种排序算法以供系统和用户使用。
即使你只是使用标准库中的排序函数，学习排序算法仍然有三大实际意义：
1.对排序算法的分析将有助于你全面理解本书中比较算法性能的方法；
2.类似的技术也能有效解决其他类型的问题；
3.排序算法常常是我们解决其他问题的第一步。
更重要的是这些算法都很经典、优雅和高效。排序在商业数据处理和现代科学计算中有着重要的地位，它能够应用于事物处理、组合优化、天体物理学、分子动力学、语言学、基因组学、天气预报和很多其他领域。其中一种排序算法（快速排序）甚至被誉为20世纪科学和工程领域的十大算法之一。
我们将学习几种经典的排序算法，并高效地实现了“优先队列”这种基础数据类型。
我们将讨论比较排序算法的理论基础并在本章结尾总结若干排序算法和优先队列的应用。
作为对排序算法领域的第一次探索，我们将学习两种初级的排序算法以及其中一种的一个变体。深入学习这些相对简单的算法的原因在于：第一，我们将通过它们熟悉一些术语和简单的技巧；第二，这些简单的算法在某些情况下比我们之后将会讨论的复杂算法更有效；第三，以后你会发现，它们有助于我们改进复杂算法的效率。
我们关注的主要对象是重新排列数组元素的算法，其中每个元素都有一个主键。排序算法的目标就是将所有元素的主键按照某种方式排列（通常是按照大小或是字母顺序）。排序后索引较大的主键大于等于索引较小的主键。元素和主键的具体性质在不同的应用中千差万别。在Java中，元素通常都是对象，对主键的抽象描述则是通过一种内置的机制（请见2.1.1.4节中的Comparable接口）来完成的。“排序算法类模版”中的Example类展示了我们的习惯约定：我们会将排序代码放在类的sort()方法中，该类还将包含辅助函数less()和exch()（可能还有其他辅助函数）以及一个示例用例main()。Example类还包含了一些早期调试使用的代码：测试用例main()将标准输入得到的字符串排序，并用私有方法show()打印字符数组的内容。我们还会在本章中遇到各种用于比较不同算法并研究它们的性能的测试用例。为了区别不同的排序算法，我们为相应的类取了不同的名字，用例可以根据名字调用不同的实现，例如Insertion.sort()、Merge.sort()、Quick.sort()等。
大多数情况下，我们的排序代码只会通过两个方法操作数据：less()方法对元素进行比较，
exch()方法将元素交换位置。exch()方法的实现很简单，通过Comparable接口实现less()方
法也不困难。将数据操作限制在这两个方法中使得代码的可读性和可移植性更好，更容易验证代码的正确性、分析性能以及排序算法之间的比较。在学习具体的排序算法实现之前，我们先讨论几个对于所有排序算法都很重要的问题。
这个类展示的是数组排序实现的框架。对于我们学习的每种排序算法，我们都会为这样一个类实现一个sort()方法并将Example改为算法的名称。测试用例会将标准输入得到的字符串排序，但是这段代码使我们的排序方法适用于任意实现了Comparable接口的数据类型。
