程序员学数据结构

第12章　排序：为混乱带来秩序

除非待解决问题中的数据集合规模较小，其中任何一个数据集都能从较小的数据组织形态中获益，不然仅为特定应用程序建立正确的数据结构或数据集只能算是我们终极目标的一部分。将数据列表或数据集中的元素按照特定的值或值的集合组织起来的方式称为排序（sorting）。

并不是一定要对数据进行排序，但排序会令搜索或查找操作的效率更高。同样地，当你试图把多个数据集合并在一起的时候，若事先就对这些数据集进行了排序，合并操作的效率就会有极大的提升。

若要对纯数值的数据集进行排序，只需将该数据集以升序或降序的方式进行重新组织即可。然而，若要对复杂对象的数据集进行排序，则需要将该数据集按照特定值进行重新组织。在这种情况中，排序操作所参考的字段或属性被称为键（key）。例如，现有一个由汽车对象组成的数据集，要将该数据集按照不同的汽车生产商进行排序，如福特、雪佛兰、道奇等，则这些汽车生产商就为该排序的键。然而，若需要使用多个键对该数据集排序，如汽车生产商和型号，则令汽车生产商为主键（primary key），而汽车型号为辅键（secondary key）。若将该模式进一步扩展，将会产生三级键（tertiary key）、四级键（quaternary key）等额外键。

不同排序算法适用于不同规模或不同类型的排序问题，每种排序算法往往只适用于特定类型的数据结构。尽管对已知或常用的排序算法进行详细分析已超出了本书的范畴，但本章仍会将重点集中在通用的排序算法或适用于之前所学数据结构的排序算法上。在学习每一种排序算法时，我们都将使用本书所讨论的4种开发语言进行逐一举例，同时会对每种算法的复杂度进行讨论。

本章将涵盖以下主要内容：

• 选择排序（selection sort）；
• 插入排序（insertion ...