交换类排序法

2.8.1　交换类排序法

所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类的排序方法。

1．冒泡排序法

冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序表。

冒泡排序法的基本过程如下：

首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两个相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是线性表中最大元素应有的位置。

然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前面，这也是线性表中最小元素应有的位置。

对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序表。

在上述排序过程中，对线性表的每一次来回扫描后，都将其中的最大者沉到了表的底部，最小者像气泡一样冒到表的前头。冒泡排序由此而得名，且冒泡排序又称为沉排序。

假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。但这个工作量不是必需的，一般情况下要小于这个工作量。

如图2-35所示是冒泡排序的示意图。图中有方框的元素位置表示扫描过程中最后一次发生交换的位置。由图2-35可以看出，整个排序实际上只用了2遍从前往后的扫描和2遍从后往前的扫描就完成了。

图2-35　冒泡排序过程示意图

2．快速排序法

在前面所讨论的冒泡排序法中，由于在扫描过程中只对相邻两个元素进行比较。因此，在互换两个相邻元素时只能消除一个逆序。如果通过两个（不是相邻的）元素的交换，能够消除线性表中的多个逆序，就会大大加快了排序的速度。显然，为了通过一次交换能消除多个逆序，就不能像冒泡排序法那样对相邻两个元素进行比较，因为这样只能使相邻两个元素进行交换，从而只能消除一个逆序。下面介绍的快速排序法可以实现通过一次交换而消除多个逆序。

快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。

快速排序法的基本思想如下：

从线性表中选取一个元素，设为T，然后将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。

如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变成了有序表。由此可知，快速排序法的关键是对线性表进行分割，以及对各分割出的子表再进行分割，这个过程如图2-36所示。

图2-36　快速排序示意图

在对线性表或子表进行实际分割时，可以按如下步骤进行：

首先，在表的第一个、中间一个与最后一个元素中选取中项，设为P(k)，并将P(k)赋给T，再将表中的第一个元素移到P(k)的位置上。

然后，设置两个指针i和j分别指向表的起始与最后的位置。反复操作以下两步：

（1）将j逐渐减小，并逐次比较P(j)与T，直到发现一个P(j)＜T为止，将P(j)移到P(i)的位置上。

（2）将i逐渐增大，并逐次比较P(i)与T，直到发现一个P(i)＞T为止，将P(i)移到P(j)的位置上。

上述两个操作交替进行，直到指针i与j指向同一个位置（即i=j）为止，此时将T移到P(i)的位置上。

在快速排序过程中，随着对各子表不断地进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行再分割处理，需要将暂时不分割的子表记忆起来，这就要用一个栈来实现。在对某个子表进行分割后，可以将分割出的后一个子表的第一个元素与最后一个元素的位置压入栈中，而继续对前一个子表进行再分割；当分割出的子表为空时，可以从栈中退出一个子表（实际上只是该子表的第一个元素与最后一个元素的位置）进行分割。这个过程直到栈空为止，此时说明所有子表为空，没有子表再需要分割，排序就完成了。