排序也是数据处理的重要内容。所谓排序是指将一个无序列整理成按非递减顺序排列的有序序列。排列的方法有很多，根据待排序序列的规模以及对数据的处理的要求，可以采用不同的排序方法。本节主要介绍一些常用的排序方法。
　  排序可以在各种不同的存储结构上实现。在本节所介绍的排序方法中，其排序的对象一般认为是顺序存储的线性表，在程序设计语言中就是一维数组。

　  1.8.1 交换类排序法
　　1.8.2 插入类排序法
　　1.8.3 选择类排序法

　　1.8.1 交换类排序　

　　所谓交换排序法是指借助数据元素之间互相交换进行排序的方法。冒泡排序与快速排序法都属于交换类排序方法。
　  1. 冒泡排序法
　  冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据的交换逐步将线性表变成有序。
　  冒泡排序法的基本过程如下：
　  首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们交换，称之为消去了一个逆序。显然在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是线性表中最大元素应有的位置。
　  然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序，显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前面，这也是线性表中最小元素应有的位置。
　  对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。
　  在上述的排序过程中，对线性表的每一次来回扫描后，都将其中的最大者沉到了表的底部，最小者象气泡一样冒到表的前头。冒泡排序由此而得名，且冒泡排序又称下沉排序。
　  假设线性表的长度为 n ，则在最坏情况下，冒泡排序需要经过 n/2 遍的从前往后的扫描和 n/2 遍的从后往前的扫描，需要的比较次数为 n(n-1)/2 。但这个工作量不是必要的，一般情况下要小于这个工作量。
　  图 1.36 是冒泡排序的示意图。图中有方框的元素位置表示扫描过程中最后一次发生交换位置。由图 1.36 可以看出，整个排序实际上只用了 2 遍从前往后的扫描和 2 遍从后往前的扫描就完成。
　　
　　　　　　　　　　　　　　　　　　　　　　　　　　图1.36　冒泡排序实例
　　2 ．快速排序法
　  在前面所讨论的冒泡排序法中，由于在扫描过程中只对相邻两个元素进行比较，因此，在互换两个相邻元素时只能消除一个逆序。如果通过两个（不是相邻的）元素的交换，能够消除线性表中的多个逆序，就会大大加快排序的速度。显然，为了通过一次交换能消除多个逆序，就不能象冒泡排序法那样对相邻两个元素进行比较，因为这只能使相邻两个元素进行交换从而只能消除一个逆序。下面介绍的快速排序法可以实现通过一次交换而消除多个逆序。
　  快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。
　  从线性表中选取一个元素，设为 T ，将线性表后面小于 T 的元素移到前面，而前面大于 T 的元素移到后面，结果就将线性表分成了两部分（称之为两个子表）， T 插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以为 T 分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于 T ，而后面子表中的元素均不小于 T 。
　  如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变为了有序表。
　  由此可知，快速排序法的关键是对线性表进行分割，以及对各分割出的子表再进行分割，这个过程如图 1.37 所示。


　　在对线性表或子表进行实际分割时，可以按如下步骤进行：
　  首先，在表的第一个，中间一个与后一个元素中选取中项，设为 P(k) ，并将 P(k) 赋给 T ，再将表中的第一个元素移到 P(k) 的位置上。
　  然后设置两个指针和分别指向表的起始和最后位置。反复操作以下两步：
　  （ 1 ）将 j 逐渐减小，并逐次比较 P(j) 与 T ，直到发现一个 P(j)<T 为止，将 P(j) 移到 P(i) 的位置上。
　  （ 2 ）将 i 逐渐增大，并逐次比较 P(i) 与 T ，直到发现一个 P(i)>T 为止，将 P(i) 移到 P(j) 的位置上。
　  上述两个排序过程中，随着对各子表不断的进行分割，划分出的子表回越来越多，但一次又只能对一个子表进行分割处理，需要将暂时不分割的子表记忆起来，这就要用一个栈来实现。在对某个子表进行分割后，可以将分割出的后一个子表的第一个元素与最后一个元素的位置压入栈中，而继续对前一个子表进行再分割；当分割出的子表为空时，可以从栈中退出一个子表（实际上只是该子表的第一个元素与最后一个元素的位置）进行分割。这个过程直到栈为空为之，此时说明所有子表为空，没有子表在需要分割，排序完成了。

　　1.8.2 插入类排序法

　　冒泡排序与快速排序法本质上都是通过数据元素的交换来逐步消除线性表中的逆序。本小节讨论另一类排序的方法，即插入类排序法。
　  •  简单插入排序法
　  所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。
　  我们可以想象，在线性表中，只包含第 1 个元素的子表显然可以看成是有序表。接下来的问题是，从线性表的第 2 个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面已经有序子表中，插入过程如下：
　  首先将第 j 个元素放到一个变量 T 中，然后从有序子表的最后一个元素（即线性表中第 j-1 个元素）开始，往前逐个与 T 进行比较，将大于 T 的元素均依次向后移动一个位置，直到发现一个元素不大于 T 为止，此时就将 T （即原线性表中的第 j 个元素）插入到刚移出的空位置上，有序子表的长度就变为 j 了。
　  图 1.38 给出了插入排序的示意图。图中画有方框的元素表示刚被插入到有序子表中。
　  在简单插入排序中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要 n(n-1)/2 次比较。
　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　图 1.38 简单插入排序示意图
　　•  希尔排序法
　  希尔排序法 (shell sort) 属于插入类排序，但它对简单插入排序做了较大的改进。
　  希尔排序法的基本思想如下：
　  将整个无序列分割成若干小的子序列分别进行插入排序。
　  子序列的分割方法如下；
　  将相隔某个增量 h 的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当 h 减到 1 时，进行一次插入排序，排序就完成。
　  增量序列一般取 h t =n/2 k (k=1,2, …,[logn]) ，其中 n 为待排序序列的长度。
　  图 1.39 为希尔排序法的示意图。
　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　图1.39 希尔排序
　  在希尔排序过程中，虽然对于每一个子表采用的仍是插入排序，但是，在子表中每进行一次比较就有可能移去整个线性表中的多个逆序，从而改善了整个排序过程的性能。
　  希尔排序的效率与所选取的增量序列有关。如果选取上述增量序列，则在最坏情况下，希尔排序所需要的比较次数为 O （ n 1.5 ）。

　　1.8.3 选择类排序 　

　　1. 简单选择排序法
　  选择排序法的基本思想如下：
　  扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到空表为止。
　  对于长度为 n 的序列，选择排序需要扫描 n-1 遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。图 1.40 是这种排序法的示意图，图中有方框的元素是被选出来的最小元素。
　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　图 1.40 简单选择排序法示意图
　　简单选择排序法在最坏情况下需要比较 n （ n-1 ） /2 次。
　  2. 堆排序法
　  堆排序法属于选择类的排序方法。
　  堆定义如下：
　  具有 n 个元素的序列（ h 1 ， h 2 ……， h n ），当且仅当满足
　　 h i ≥ h 2i h i ≤ h 2i
　　 hi ≥ h 2i+1 或 hi ≤ h 2i+1
　  （ i=1 ， 2 ，…， n/2 ）时称之为堆。本节只讨论满足前提条件的堆。
　  由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。
　  在实际的处理中，可以用一维数组 H （ 1 ： n ）来存储堆序列中的元素，也可以用完全二叉树来直观地表示堆的结构。例如，序列（ 91 ， 85 ， 53 ， 36 ， 47 ， 30 ， 24 ， 12 ）是一个堆，它所对应的完全二叉树如图 1.41 所示。由图 1.41 可以看出，在用完全二叉树表示堆时，树中所以非叶子结点值均不小于其左、右子树的根结点值，因此，堆顶（完全二叉树的根结点）元素必为序列的 n 个元素中的最大项。
　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　图1.41 堆顶元素为最大元素
　　在具体讨论堆排序法之前，先讨论这样一个问题：在一棵具有 n 个结点的完全二叉树 [ 用一维数组 H （ 1 ： n ）表示 ] 中，假设结点 H （ m ）的左右子树均为堆，现要将以 H （ m ）为根结点的子树也调整为堆。这是调整建堆的问题。
　  例如，假设图 1.42 （ a ）是某完全二叉树的一棵子树。显然，在这棵子树中，根结点 47 的左、右子树均为堆。现在为了将整个子树调整为堆，首先将根结点 47 与其左、右子树的根结点的值进行比较，此时由于左子树根结点 91 大于右子树根结点 47 ，因此，根据堆的条件，应将元素 47 与 91 交换，如图 1.42 （ b ）所示。经过这一次交换后，破坏了原来左子树的堆结构，需要对左子树再进行调整，将元素 85 与 47 进行交换，调整后的结果如图 1.42 （ c ）所示。
　　　　　　　　
　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 (c)
　　　　　　　　　　　　　　　　　　　　　　　　　　图 1.42 调整建堆示意图
　　由这个列子可以看出，在调整建堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点中的大者与根结点值进行交换。这个调整过程一直做到所以子树均为堆时为止。
　  有了调整堆的算法后，就可以将一个无序序列建为堆。
　  假设无序序列 H （ 1 ： n ）以完全二叉树表示。从完全二叉树的最后一个非叶子结点（即第 n/2 个元素）开始，直到根结点（即第一个元素）为止，对每一个进行调整建堆，最后就可以得到与该序列对应的堆。
　  根据堆的定义，可以得到堆排序的方法如下：
　  （ 1 ）首先将一个无序序列建成堆。
　  （ 2 ）然后将堆顶元素（序列中的最大值）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前 n-1 个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第（ 2 ）步，直到剩下的子序列为空为止。
　   堆排序的方法对于规模较小的线性表并不适合，但对较大规模的线性表来说是很有效的。在最坏的情况下，堆排序需要比较的次数为 O （ nlog 2 n ）。