2.7 排 序

 

2.7 排 序

排序和查找一样，也是数据处理中的一种重要运算，高效地进行排序也是计算机应用的重要课题之一。在前一节的查找算法中，对分查找较线性查找效率高，主要是后者要求线性表是有序的。

2.7.1有关的概念和术语

1. 排序

定义：设有n个数据元素序列{ }，其相应的关键字为{}，要求确定一种排列，使关键字（或），使原来序列成为按关键字有序的序列{}。

2. 算法的稳定性

    当序列中元素的关键字项各不相同（主关键字）时，排序结果是惟一的，不存在稳定性问题。

   当序列中元素有相同的关键字项（次关键字）时，排序结果可能不惟一。若在排序前领先，排序后和次序不变，称为稳定排序，否则称为不稳定排序。

3. 内排序和外排序

待排序的数据元素均在内存中，称为内排序；反之，有部分数据元素存放在外存中，排序过程要进行内外交换操作的称为外排序。

4. 算法的时间复杂度

影响排序算法时间复杂度的因素有二。

（1）   比较次数：排序过程中对元素关键字进行比较的次数。

（2）   记录移动次数：比较后元素记录从一个位置移到另一位置的次数。

5. 算法种类

本节中介绍三种类型的排序算法：

（1）   选择排序——简单选择排序、堆排序。

（2）   插入排序——简单插入排序、对半插入排序。

（3）   交换排序——冒泡排序、快速排序。

在上述三类算法中，每一类介绍了两种算法，一般说来，前一种算法比较简单，稳定性较好，但时间复杂度较高，适用于长度较小的线性表排序，而后一种是为了提高排序效率做了一些改进，但算法相对较复杂，稳定性也不如前者，尤其是堆排序和快速选择排序，我们将重点作一些补充说明。此外，利用树的形式进行排序，即二叉排序树的方法，在前面以已经作了介绍，它是一种动态排序方法，适用于元素个数变化比较频繁的情况。

2.7.2选择排序

   选择排序的算法思想是把线性表中的元素分为有序区与无序区两部分，排序开始时，整个线性表为无序区，通过不断在无序区中选择合适的元素放入有序区中，逐渐扩大有序区，直到整个线性表成为有序区为止。

1.简单选择排序

在由n个元素组成的无序区中，顺序查找关键字最小的元素，并将它与第1个元素交换，称为进行了一趟排序，然后在对余下的(n-1)个元素重复上述操作，使得在线性表前端逐渐形成一个由小到大的有序区，直到整个线性表成为有序区为止。

算法分析

（1）比较次数

有n个元素的线性表，共需进行(n-1)躺排序，每一趟中对关键字进行比较的次数为（n-i）次，因此比较次数为

                  C==n(n-1)/2

(2)记录移动次数

①  最少移动次数

如果初始状态已处于排序状态，就不需要进行记录移动，因此最小移动次数为0。

②  最大移动次数

如果初始状态为逆序状态，每一趟后要进行一次交换记录，每交换一次需要3次赋值运算，所以移动次数为3（n-1）。

总的时间复杂度为O(n),空间复杂度为O(1)。

特点：算法简单，适用于n较小的情况。

2. 堆排序

简单排序的时间复杂度为O(n),影响了排序的效率，这是由于它没有把前一趟排序过程中进行元素关键字的比较结果保留下来，以致在后一趟排序过程中又重复进行比较。堆排序是另一种选择排序方法，它是利用“堆”的特性来选择元素，进行排序。堆排序的主要工作是建立处世堆以及在排序过程中（每一趟结束）不断地调整堆。

(1)堆

堆是一种特殊的完全二叉树，在这种二叉树中，每一个非叶子结点的数值均大于或等于它的左、右孩子结点的数值。因此这类二叉树的根结点具有这棵树中的最大值，称为堆顶。将一棵一般的完全二叉树改造成堆称为构造堆。

由于完全二叉树的结点序号具有自上而下，自左而右的编号规则，因此我们可以将一棵有n个结点的完全二叉树存放在长度为n的一维数组中，数组的下标值与二叉树结点的编号一致。如果这棵完全二叉树已经构成堆，则其结点数值一定满足

                     k>=k,k>=k(i=1,2,…)

其中k和k分别为k结点的左右孩子，为最低层的非叶子结点序号。

(2)构造堆

将一棵一般的完全二叉树构成堆，首先从最低层的非叶子结点（即第个结点）开始直到根结点，逐个进行本结点与其左右孩子结点数值比较。

a)   若本结点数值等于其左右孩子结点的数值，满足堆的要求，不作任何处理。

b)   若本结点数值小于其左右孩子中某一个的数值，则将左右孩子中数值较大的交换到该结点，同时对被交换以后孩子结点及其下属的结点进行调整处理，使它仍满足堆的要求。

(3)堆排序

把待排序的n个无序序列放在一维数组中，把它看作一棵完全二叉树，对它构造堆，取堆顶元素（第1个元素）与第n个元素交换，此时第n个元素即为有序区。然后对第1～（n-1）个元素进行调整处理，使其再成为堆，重复上述操作，直到整个数组都成为有序区，排序结束。

(4)算法分析

    堆排序算法中时间复杂度主要是在构造堆的过程中，这里不作详细推导，时间复杂度为。交换元素需要1个辅助单元，空间负责度为O（1）。

堆排序适用于n较大情况，待排序序列的初始状态对它影响不大，它是不稳定排序。

 

2.7.3插入排序

   插入排序的基本思想中的时间复杂度主要是在构造堆的过程中，不断扩大有序区，直到所有元素都插到有序区中，排序结束。每插入一个元素的过程称为一趟排序。

   1.线性插入排序

   这是一种简单的排序方法，基本操作是以第1个与元素作为有序区，顺序将后续元素逐个插入到有序区中。插入的方式是将被插入元素与已在有序区中的元素逐个比较，直到找到合适的插入位置，移动元素，进行插入，完成一趟排序。在上一节线性查找算法中曾在线性表的末尾设立一个“监视哨”，一旦比较得到监视哨元素时会自动结束比较。在这里由于插入过程是从有序区尾部向前推进，所以在有序表的首部第0个单元中放入本次要插入的元素值，同样起到监视哨的作用。

   算法分析

(1)比较次数

最少比较次数：当待排序序列已有序时，每趟只需比较1次就找到插入位置 ，所以总的比较次数为

=

最大比较次数：当待排序序列为逆序时，每一趟排序需比较i次，所以总的比较次数为

    

(2)记录移动次数

最少移动次数：当待排序序列已有序列时，插入时不用移动元素，但在每趟排序前后需把本次要插入的元素值放入监视哨内及把监视哨内数值放入该插入位置2次移动。所以总的移动次数为

最大移动次数：当待排序序列为逆序时，每一趟排序需要有序区中元素（共i-1个）逐个移动一位以便插入新元素。再加上每趟排序前后对监视哨的数据的放入与取出，总的移动次数为

时间复杂度为，空间复杂度是用于监视哨用的一个单元，所以为。

特点：算法较简单，用于n最小时，它的运算效率与待排序序列的初始状态有关。

   2.对半插入排序

    在线性插入排序中，将元素插入到有序区的过程中，实际上是对有序区进行顺序查找的过程。由于有序区中的元素已经有序，所以可以用对分查找来取代原来的顺序查找，以减少算法的比较次数。

   算法分析

由于采用了对分查找法进行插入比较，使得算法比较次数的时间复杂度为，但总的时间复杂度仍为，空间复杂度为。

 

2.7.4 交换排序

交换排序是通过对序列中各元素的关键字相互比较交换位置，使得关键字大的元素逐渐向后移动，关键字小的元素向前移动，最后达到全部元素的排序。

1.冒泡排序

冒泡排序的算法思想是从第一个元素开始对相邻两个元素的关键字进行比较，每次比较结果把关键字小的元素交换到关键字大的前面，一趟排序以后，使最大的关键字元素交换到表的尾端形成一个有序区，而关键字较小的元素则向表头方向移动。重复上述操作，逐渐扩大有序区，而关键字较小的元素在每趟排序中如同气泡一般逐渐向表头“飘浮”，直到飘出“水面”。为说明问题，并能与后面的快速排序方法相比较，这里用一个例子来描述排序的过程。

例2.23 用冒泡排序方法对下列序列进行排序

28 19  27  49  56  12  ⑩   49  25  20   50

19   27  28  49  12   ⑩  49 25   20  50    第1趟

19   27  28  12   ⑩  49  25   20  49     第2趟

19   27  12  ⑩   28  25   20   49  50    第3趟

    19   12  ⑩  27  20  25  28    49  50    第4趟

    12   ⑩  19  20  25  27    49  49  50    第5趟

    ⑩   12  19  20  25    28  49  49  50    第6趟

    10   12  19  20  25    28  49  49  50    第7趟 结束排序

对于有n个元素组成的排序序列，用冒泡排序方法进行排序，最多需进行（n-1）趟排序。但由于待排序元素初始状态不同，有时不一定需要（n-1）趟就已有序，如上述例子，在第6趟排序结束时元素已基本有序。因此在算法设计时应增加一个标志量来判断是否还需要继续下一趟排序。当一趟排序完成后没有出现一次元素的交换，就意味着排序结束，应把标志信号翻过来，例如上述例子中第7趟排序操作后应结束。

算法分析

最少比较次数：当原始序列已为有序时，只要一趟排序即可结束排序

                     =

最大比较次数：当原始序列正好逆序时，共要进行（n-1）趟排序，每趟比较次数为（n-i）。

                     =

(2)记录移动次数

最少移动次数：当原始序列已为有序时，不需要进行元素交换。

最大移动次数：当原始序列为逆序列时，每次比较都要交换（移动3次）。

             

时间复杂度为，交换需要1个辅助单元，空间复杂度为。

特点：适用于关键字基本有序时。

    2.快速排序

是在冒泡排序基础上改进的一种排序方法。冒泡排序经每一趟排序后，使在表的一端的有序区扩大，最后达到完全有序，最坏的情况下，他的时间复杂度为。为了提高排序效率，我们设想一种算法，同样是进行元素的比较和交换，若是能使一趟排序后，将原无序区划分为两个独立的无序子区，再分别对它们进行排序，借助的道理，使得排序的时间复杂度由降到。

例2.24 对例2.23的序列，使快速排序法进行排序，第1趟排序的过程如下：

 

 

 

以上为一趟排序过程，其中28位控制关键字，不带箭头的线段表示两个元素只进行比较不交换位置；带双向箭头的线段表示两个元素比较后要交换位置。I指针指向无序区的头，j指针指向无序区的尾，在比较过程中i指针向右移动，j指针向左移动，当i=j时一趟排序结束，这时形成以控制关键字为界的两个无序子区，再分别对它们进行快速排序。

对上述方法的改进：从上面对快速排序的过程可以看到，控制关键字要多次进行交换操作，最终找到它的位置。其实我们需要的仅是它的最终位置，而对其中间的交换位置宾不感兴趣，而每交换一次位置就需要三个语句在加一个辅助单元来完成，为节省时间开销，我们采用下列改进算法，将控制关键字暂存到一个辅助单元x中，以后比较时，用x单元与表中其它元素进行比较。上例的排序过程可以按如下方式进行：

 

由于每一趟排序前把本次控制关键字暂存起来，在比较过程中遇到要交换位置时只要用移动元素（用单向箭头的线段表示）来处理，节省了时间。在一趟排序结束时，再把暂存单元中的控制关键元素放入i，j指针指向的位置中。

算法分析

(1)快速排序在目前市被认为最好的排序方法，它利用不断分割排序区间的方法进行排序，在理想情况下，当每趟排序结束，正好把无序区等分，则其推进速度类似于对分查找，因此它的时间复杂度为。但当原始排序序列已按关键字有序排列（递增有序或递减有序）时，情况反而恶化了，因为一趟排序结束，控制关键字将落在表的一端，失去了快速排序的优势，蜕化为冒泡排序。

(2)快速排序需要一个辅助单元存放控制关键字，因此空间复杂度为。但因算法中采用了递归算法，因此系统要为此开辟一个递归调用的栈空间。

(3)本算法为不稳定排序