数据结构_课件_8

1、本章中主要介绍下列内容：本章中主要介绍下列内容：l 插入排序插入排序l 交换排序交换排序l 选择排序选择排序l 归并排序归并排序l 基数排序基数排序8.1 基本概念基本概念8.2 插入排序插入排序8.3 交换排序交换排序8.4 选择排序选择排序8.5 归并排序归并排序8.6 基数排序基数排序 关键字关键字 是数据元素中的某个数据项。如果某个数是数据元素中的某个数据项。如果某个数据项可以唯一地确定一个数据元素，就将其称为主关据项可以唯一地确定一个数据元素，就将其称为主关键字；否则，称为次关键字。键字；否则，称为次关键字。 排序排序 是把一组无序地数据元素按照关键字值递增是把一组无序地数据元素按照

2、关键字值递增（或递减）地重新排列。如果排序依据的是主关键字，（或递减）地重新排列。如果排序依据的是主关键字，排序的结果将是唯一的，排序的结果将是唯一的， 排序算法的稳定性排序算法的稳定性 如果在待排序的记录序列中有如果在待排序的记录序列中有多个数据元素的关键字值相同，经过排序后，这些数多个数据元素的关键字值相同，经过排序后，这些数据元素的相对次序保持不变，则称这种排序算法是稳据元素的相对次序保持不变，则称这种排序算法是稳定的，否则称之为不稳定的。定的，否则称之为不稳定的。 内部排序与外部排序内部排序与外部排序 根据在排序过程中待排序的根据在排序过程中待排序的所有数据元素是否全部被放置在内存中，

3、可将排序方所有数据元素是否全部被放置在内存中，可将排序方法分为内部排序和外部排序两大类。内部排序是指在法分为内部排序和外部排序两大类。内部排序是指在排序的整个过程中，待排序的所有数据元素全部被放排序的整个过程中，待排序的所有数据元素全部被放置在内存中；外部排序是指由于待排序的数据元素个置在内存中；外部排序是指由于待排序的数据元素个数太多，不能同时放置在内存，而需要将一部分数据数太多，不能同时放置在内存，而需要将一部分数据元素放置在内存，另一部分数据元素放置在外设上，元素放置在内存，另一部分数据元素放置在外设上，整个排序过程需要在内外存之间多次交换数据才能得整个排序过程需要在内外存之间多次交换数

4、据才能得到排序的结果。本章只讨论常用的内部排序方法。到排序的结果。本章只讨论常用的内部排序方法。 排序的基本方法排序的基本方法 内部排序主要有内部排序主要有5种方法：插入、种方法：插入、交换、选择、归并和基数。交换、选择、归并和基数。 趟趟 在排序过程中，基本动作执行一次。在排序过程中，基本动作执行一次。 排序算法的效率排序算法的效率 评价排序算法的效率主要有两点：评价排序算法的效率主要有两点：一是在数据量规模一定的条件下，算法执行所消耗的一是在数据量规模一定的条件下，算法执行所消耗的平均时间，对于排序操作，时间主要消耗在关键字之平均时间，对于排序操作，时间主要消耗在关键字之间的比较和数据元素

5、的移动上，因此我们可以认为高间的比较和数据元素的移动上，因此我们可以认为高效率的排序算法应该是尽可能少的比较次数和尽可能效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动次数；二是执行算法所需要的辅助少的数据元素移动次数；二是执行算法所需要的辅助存储空间，辅助存储空间是指在数据量规模一定的条存储空间，辅助存储空间是指在数据量规模一定的条件下，除了存放待排序数据元素占用的存储空间之外，件下，除了存放待排序数据元素占用的存储空间之外，执行算法所需要的其他存储空间，理想的空间效率是执行算法所需要的其他存储空间，理想的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无算法执行期间所需

6、要的辅助空间与待排序的数据量无关。关。 待排序记录序列的存储结构待排序记录序列的存储结构 待排序记录序列可以待排序记录序列可以用顺序存储结构和和链式存储结构表示。在本章的讨用顺序存储结构和和链式存储结构表示。在本章的讨论中（除基数排序外），我们将待排序的记录序列用论中（除基数排序外），我们将待排序的记录序列用顺序存储结构表示，即用一维数组实现。其定义如下顺序存储结构表示，即用一维数组实现。其定义如下所示：所示：#define MAX_NUM 80/待排序记录序列中的最大数待排序记录序列中的最大数据元素个数据元素个数typedef struct elemtype /待排序的数据元素类型待排序的数

7、据元素类型 keytype key;/数据元素的关键字数据元素的关键字 anytype otheritem;/数据元素中的其他成份数据元素中的其他成份DataTypeMAX_NUM+1; 插入排序的主要思路是不断地将待排序的数值插插入排序的主要思路是不断地将待排序的数值插入到有序段中，使有序段逐渐扩大，直至所有数值都入到有序段中，使有序段逐渐扩大，直至所有数值都进入有序段中位置。进入有序段中位置。 8.2.1 8.2.1 直接插入排序直接插入排序1. 1. 直接插入排序的基本思想直接插入排序的基本思想 直接插入排序是一种比较简单的排序方法。它的直接插入排序是一种比较简单的排序方法。它的基本思想

8、是依次将记录序列中的每一个记录插入到有基本思想是依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。其具体的排序序段中，使有序段的长度不断地扩大。其具体的排序过程可以描述如下：首先将待排序记录序列中的第一过程可以描述如下：首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录个记录作为一个有序段，将记录序列中的第二个记录插入到上述有序段中形成由两个记录组成的有序段，插入到上述有序段中形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段，形成由三个记录组成的有序段，

9、依此类推，每一趟依此类推，每一趟都是将一个记录插入到前面的有序段中，假设当前欲都是将一个记录插入到前面的有序段中，假设当前欲处理第处理第i个记录，则应该将这个记录插入到由前个记录，则应该将这个记录插入到由前i-1个记个记录组成的有序段中，从而形成一个由录组成的有序段中，从而形成一个由i个记录组成的按个记录组成的按关键字值排列的有序序列，直到所有记录都插入到有关键字值排列的有序序列，直到所有记录都插入到有序段中。一共需要经过序段中。一共需要经过n-1趟就可以将初始序列的趟就可以将初始序列的n个个记录重新排列成按关键字值大小排列的有序序列。记录重新排列成按关键字值大小排列的有序序列。2. 2. 直

10、接插入排序算法直接插入排序算法 将第将第i个记录插入到由前面个记录插入到由前面i-1个记录构成的有序段个记录构成的有序段中主要有两个步骤：中主要有两个步骤： 将待插入记录将待插入记录ai 保存在保存在a0中，即中，即a0=ai; 搜索插入位置：搜索插入位置：j=i-1; /j最初指示最初指示i的前一个位置的前一个位置while (a0.key aj.key) aj+1=aj; /后移关键字值大于后移关键字值大于a0.key的记录的记录 j=j-1; /将将j指向前一个记录，为下次比较做准备指向前一个记录，为下次比较做准备aj+1=a0; /将将a0放置在第放置在第j+1个位置上个位置上完整的插

11、入排序算法为：完整的插入排序算法为：void insertsort (DataType a, int n) for (i=2; i=n; i+) /需要需要n-1趟趟 a0=ai; /将将ai赋予监视哨赋予监视哨j=i-1;while (a0.keyaj.key) /搜索插入位置搜索插入位置 aj+1=aj; j=j-1; aj+1=a0;/ 将原将原ai中的记录放入第中的记录放入第j+1个位置个位置 直接插入排序算法简单、容易实现，只需要一个直接插入排序算法简单、容易实现，只需要一个记录大小的辅助空间用于存放待插入的记录（在记录大小的辅助空间用于存放待插入的记录（在C语语言中，我们利用了数组

12、中的言中，我们利用了数组中的0单元）和两个单元）和两个int型变量。型变量。当待排序记录较少时，排序速度较快，但是，当待排当待排序记录较少时，排序速度较快，但是，当待排序的记录数量较大时，大量的比较和移动操作将使直序的记录数量较大时，大量的比较和移动操作将使直接插入排序算法的效率降低；然而，当待排序的数据接插入排序算法的效率降低；然而，当待排序的数据元素基本有序时，直接插入排序过程中的移动次数大元素基本有序时，直接插入排序过程中的移动次数大大减少，从而效率会有所提高。大减少，从而效率会有所提高。 插入排序是一种稳定的排序方法。插入排序是一种稳定的排序方法。 8.2.2 8.2.2 希尔排序希尔

13、排序1. 1. 希尔排序的基本思想希尔排序的基本思想 希尔排序方法又称为缩小增量排序，其基本思想希尔排序方法又称为缩小增量排序，其基本思想是将待排序的记录划分成几组，从而减少参与直接插是将待排序的记录划分成几组，从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接列已经基本有序，这个时候再对所有的记录实施直接插入排序。插入排序。 具体步骤可以描述如下：假设待排序的记录为具体步骤可以描述如下：假设待排序的记录为n个，个，先取整数先取整数dn，例如，取，例如，取d=n/2 （n/2 表示不大于表

14、示不大于n/2的的最大整数），将所有距离为最大整数），将所有距离为d的记录构成一组，从而将的记录构成一组，从而将整个待排序记录序列分割成为整个待排序记录序列分割成为d个子序列，如图个子序列，如图8-2所所示，对每个分组分别进行直接插入排序，然后再缩小示，对每个分组分别进行直接插入排序，然后再缩小间隔间隔d，例如，取，例如，取d=d/2，重复上述的分组，再对每个，重复上述的分组，再对每个分组分别进行直接插入排序，直到最后取分组分别进行直接插入排序，直到最后取d=1，即将所，即将所有记录放在一组进行一次直接插入排序，最终将所有有记录放在一组进行一次直接插入排序，最终将所有记录重新排列成按关键字有序

15、的序列。记录重新排列成按关键字有序的序列。3. 3. 希尔排序算法希尔排序算法 (1) 分别让每个记录参与相应分组中的排序分别让每个记录参与相应分组中的排序 若分为若分为d组，前组，前d个记录就应该分别构成由一个记个记录就应该分别构成由一个记录组成的有序段，从录组成的有序段，从d+1个记录开始，逐一将每个记录个记录开始，逐一将每个记录ai插入到相应组中的有序段中，其算法可以这样实现：插入到相应组中的有序段中，其算法可以这样实现： for (i=d+1; i0 & a0.key=1;d=d/2) for(i=1+d;i0&a0.keyaj+1），则将其交换，最终达到有序），则将其

16、交换，最终达到有序化。其处理过程为：化。其处理过程为： （1）将整个待排序的记录序列划分成有序区和无）将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序序区，初始状态有序区为空，无序区包括所有待排序的记录。的记录。 （2）对无序区从前向后依次将相邻记录的关键字）对无序区从前向后依次将相邻记录的关键字进行比较，若逆序将其交换，从而使得关键字值小的进行比较，若逆序将其交换，从而使得关键字值小的记录向上记录向上“飘浮飘浮”（左移），关键字值大的记录好像（左移），关键字值大的记录好像石块，向下石块，向下“堕落堕落”（右移）。（右移）。 每经过一趟冒泡排序，都使无序区中

17、关键字值最每经过一趟冒泡排序，都使无序区中关键字值最大的记录进入有序区，对于由大的记录进入有序区，对于由n个记录组成的记录序列，个记录组成的记录序列，最多经过最多经过n-1趟冒泡排序，就可以将这趟冒泡排序，就可以将这n个记录重新按个记录重新按关键字顺序排列。关键字顺序排列。3. 3. 冒泡排序算法冒泡排序算法 原始的冒泡排序算法原始的冒泡排序算法 对由对由n个记录组成的记录序列，最多经过（个记录组成的记录序列，最多经过（n-1）趟冒泡排序，就可以使记录序列成为有序序列，第一趟冒泡排序，就可以使记录序列成为有序序列，第一趟定位第趟定位第n个记录，此时有序区只有一个记录；第二趟个记录，此时有序区只

18、有一个记录；第二趟定位第定位第n-1个记录，此时有序区有两个记录；以此类推，个记录，此时有序区有两个记录；以此类推，算法框架为：算法框架为： for（i=n；i1；i-） 定位第定位第i个记录；个记录； 若定位第若定位第i个记录，需要从前向后对无序区中的相个记录，需要从前向后对无序区中的相邻记录进行关键字的比较，它可以用如下所示的语句邻记录进行关键字的比较，它可以用如下所示的语句实现。实现。for（j=1；ja.j+1.key） temp=aj；aj=aj+1；aj+1=temp； 下面给出完成的冒泡排序算法：下面给出完成的冒泡排序算法：void BubbleSort1 (DataType a

19、,int n) for (i=n；i1；i-） for (j=1;ja.j+1.key） temp=aj；aj=aj+1；aj+1=temp； 改进的冒泡排序算法改进的冒泡排序算法 在冒泡排序过程中，一旦发现某一趟没有进行交换在冒泡排序过程中，一旦发现某一趟没有进行交换操作，就表明此时待排序记录序列已经成为有序序列，操作，就表明此时待排序记录序列已经成为有序序列，冒泡排序再进行下去已经没有必要，应立即结束排序冒泡排序再进行下去已经没有必要，应立即结束排序过程。过程。改进的冒泡排序算法：改进的冒泡排序算法：void BubbleSort2 (DataType a,int n)for (i=n;i

20、1;i-) exchange=0；for (j=1;ja.j+1.key) temp=aj；aj=aj+1；aj+1=temp； exchange=1； if (exchange=0) break； 进一步地改进冒泡排序算法进一步地改进冒泡排序算法 在【算法在【算法8-4】给出的冒泡排序算法的基础上，如】给出的冒泡排序算法的基础上，如果我们同时记录第果我们同时记录第i趟冒泡排序中最后一次发生交换操趟冒泡排序中最后一次发生交换操作的位置作的位置m（m1;i-) exchange=0； m=last; /初始将最后进行记录交换的位置设置成初始将最后进行记录交换的位置设置成i-1for (j=1;j

21、a.j+1.key） temp=aj；aj=aj+1；aj+1=temp； exchange=1； last=j； /记录每一次发生记录交换的位置记录每一次发生记录交换的位置 if （exchange=0）break； 冒泡排序比较简单，当初始序列基本有序时，冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低；其次冒泡冒泡排序有较高的效率，反之效率较低；其次冒泡排序只需要一个记录的辅助空间，用来作为记录交排序只需要一个记录的辅助空间，用来作为记录交换的中间暂存单元；冒泡排序是一种稳定的排序方换的中间暂存单元；冒泡排序是一种稳定的排序方法。法。 8.3.2 8.3.2 快

22、速排序快速排序 1. 1. 快速排序的基本思想快速排序的基本思想 快速排序又称为分区交换排序。其基本思想是：快速排序又称为分区交换排序。其基本思想是：首先将待排序记录序列中的所有记录作为当前待排序首先将待排序记录序列中的所有记录作为当前待排序区域，从中任选取一个记录（比如，第一个记录），区域，从中任选取一个记录（比如，第一个记录），并以该记录的关键字值为基准，从位于待排序记录序并以该记录的关键字值为基准，从位于待排序记录序列左右两端开始，逐渐向中间靠拢，交替与基准记录列左右两端开始，逐渐向中间靠拢，交替与基准记录的关键字进行比较、交换，每次比较，若遇左侧记录的关键字进行比较、交换，每次比较，若

23、遇左侧记录的关键字值大于基准记录的关键字，则将其与基准记的关键字值大于基准记录的关键字，则将其与基准记录交换，使其移到基准记录的右侧，若遇右侧记录的录交换，使其移到基准记录的右侧，若遇右侧记录的关键字值小于基准值，则将其与基准记录交换，使其关键字值小于基准值，则将其与基准记录交换，使其移至基准记录的左侧，移至基准记录的左侧， 最后让基准记录到达它的最终位置，此时，基准记录最后让基准记录到达它的最终位置，此时，基准记录将待排序记录分成了左右两个区域，位于基准记录左将待排序记录分成了左右两个区域，位于基准记录左侧的记录都小于或等于基准记录的关键字，位于基准侧的记录都小于或等于基准记录的关键字，位于

24、基准记录右侧的所有记录的关键字都大于或等于基准记录记录右侧的所有记录的关键字都大于或等于基准记录的关键字，这就是一趟快速排序；然后分别对左右两的关键字，这就是一趟快速排序；然后分别对左右两个新的待排序区域，重复上述一趟快速排序的过程，个新的待排序区域，重复上述一趟快速排序的过程，其结果分别让左右两个区域中的基准记录都到达它们其结果分别让左右两个区域中的基准记录都到达它们的最终位置，同时将待排序记录序列分成更小的待排的最终位置，同时将待排序记录序列分成更小的待排序区域，再次重复对每个区域进行一趟快束排序，直序区域，再次重复对每个区域进行一趟快束排序，直到每个区域只有一个记录为止，此时所有的记录都

25、到到每个区域只有一个记录为止，此时所有的记录都到达了它的最终位置，即整个待排序记录按关键值有序达了它的最终位置，即整个待排序记录按关键值有序排列，至此排序结束。排列，至此排序结束。 对待排序记录序列进行一趟快速排序的过程描述对待排序记录序列进行一趟快速排序的过程描述如下：如下： (1) 初始化：取第一个记录作为基准，其关键字值初始化：取第一个记录作为基准，其关键字值为为19，设置两个指针，设置两个指针i，j分别用来指示将要与基准记录分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置。最开始从进行比较的左侧记录位置和右侧记录位置。最开始从右侧开始比较，当发生交换操作后，转去再从左侧比

26、右侧开始比较，当发生交换操作后，转去再从左侧比较；较； (2) 用基准记录与右侧记录进行比较：即与指针用基准记录与右侧记录进行比较：即与指针j指向的记录进行比较，如果右侧记录的关键字值大，指向的记录进行比较，如果右侧记录的关键字值大，则继续与右侧前一个记录进行比较，即则继续与右侧前一个记录进行比较，即j减减1后，再用后，再用基准元素与基准元素与j指向的记录比较，若右侧的记录小（逆指向的记录比较，若右侧的记录小（逆序），则将基准记录与序），则将基准记录与j指向的记录进行交换；指向的记录进行交换； (3) 用基准元素与左侧记录进行比较：即与指针用基准元素与左侧记录进行比较：即与指针i指向的记录进行

27、比较，如果左侧记录的关键字值小，指向的记录进行比较，如果左侧记录的关键字值小，则继续与左侧后一个记录进行比较，即则继续与左侧后一个记录进行比较，即i加加1后，再用后，再用基准记录与基准记录与i指向的记录比较，若左侧的记录大（逆指向的记录比较，若左侧的记录大（逆序），则将基准记录与序），则将基准记录与i指向的记录交换，；指向的记录交换，； (4) 右侧比较与左侧比较交替重复进行，直到指右侧比较与左侧比较交替重复进行，直到指针针i与与j指向同一位置，即指向基准记录最终的位置。指向同一位置，即指向基准记录最终的位置。 一趟快速排序之后，再分别对左右两个区域进行一趟快速排序之后，再分别对左右两个区域进

28、行快速排序，以此类推，直到每个分区域都只有一个记快速排序，以此类推，直到每个分区域都只有一个记录为止。下面是对关键字值为（录为止。下面是对关键字值为（19,6,47,26,18,26,7,13）的记录序列进行快速排序的各趟状态的记录序列进行快速排序的各趟状态3. 3. 快速排序算法快速排序算法 快速排序是一个递归的过程，只要能够实现一趟快速排序是一个递归的过程，只要能够实现一趟快速排序的算法，就可以利用递归的方法对一趟快速快速排序的算法，就可以利用递归的方法对一趟快速排序后的左右分区域分别进行快速排序。下面是一趟排序后的左右分区域分别进行快速排序。下面是一趟快速排序的算法分析：快速排序的算法分

29、析： (1) 初始化：初始化： 将将i 和和j分别指向待排序区域的最左侧记录和最右分别指向待排序区域的最左侧记录和最右侧记录的位置。侧记录的位置。 i=first; j=end; 将基准记录暂存在将基准记录暂存在temp中。中。 temp=ai; (2) 对当前待排序区域从右侧将要进行比较的记录对当前待排序区域从右侧将要进行比较的记录（j指向的记录）开始向左侧进行扫描，直到找到第一指向的记录）开始向左侧进行扫描，直到找到第一个关键字值小于基准记录关键字值的记录：个关键字值小于基准记录关键字值的记录： while (ij & temp.key=aj) j-; (3) 如果如果i!=j，则

30、将，则将aj中的记录移至中的记录移至ai，并将，并将i+：ai=aj; i+; (4) 对当前待排序区域从左侧将要进行比较的记录对当前待排序区域从左侧将要进行比较的记录（i指向的记录）开始向右侧进行扫描，直到找到第一指向的记录）开始向右侧进行扫描，直到找到第一个关键字值大于基准记录关键字的记录：个关键字值大于基准记录关键字的记录： while (ij & ai=temp.key) i+; (5) 如果如果i!=j，则将，则将ai中的记录移至中的记录移至aj，并将，并将j+： aj=ai; j+; (6) 如果此时仍如果此时仍ij，则重复上述（，则重复上述（2）、（）、（3）、）、（4）

31、、（）、（5）操作，否则，表明找到了基准记录的最）操作，否则，表明找到了基准记录的最终位置，并将基准记录移到它的最终位置上：终位置，并将基准记录移到它的最终位置上：while （ij） 执行执行(2)、(3)、(4)、(5) 步骤步骤ai=temp; 下面是快速排序的完整算法。下面是快速排序的完整算法。void quicksort (DataType a,int first,int end ) i=first; j=end; temp=ai; /初始化初始化 while(ij) while (ij & temp.key= aj.key) j-； ai=aj； while (ij &am

32、p; ai.key=temp.key) i+； aj=ai； ai=temp； if (firsti-1) quicksort(a, first, i-1)； /对左侧分区域进行快速排序对左侧分区域进行快速排序 if (i+1end) quicksort(a, i+1, end)； /对右侧分区域进行快速排序对右侧分区域进行快速排序 快速排序实质上是对冒泡排序的一种改进，它的快速排序实质上是对冒泡排序的一种改进，它的效率与冒泡排序相比有很大地提高。在冒泡排序过程效率与冒泡排序相比有很大地提高。在冒泡排序过程中是对相邻两个记录进行关键字比较和互换的，这样中是对相邻两个记录进行关键字比较和互换的，

33、这样每次交换记录后，只能改变一对逆序记录，而快速排每次交换记录后，只能改变一对逆序记录，而快速排序则从待排序记录的两端开始进行比较和交换，并逐序则从待排序记录的两端开始进行比较和交换，并逐渐向中间靠拢，每经过一次交换，有可能改变几对逆渐向中间靠拢，每经过一次交换，有可能改变几对逆序记录，从而加快了排序速度。到目前为止快速排序序记录，从而加快了排序速度。到目前为止快速排序是平均速度最大的一种排序方法，但当原始记录排列是平均速度最大的一种排序方法，但当原始记录排列基本有序或基本逆序时，每一趟的基准记录有可能只基本有序或基本逆序时，每一趟的基准记录有可能只将其余记录分成一部分，这样就降低了时间效率，

34、所将其余记录分成一部分，这样就降低了时间效率，所以快速排序适用于原始记录排列杂乱无章的情况。以快速排序适用于原始记录排列杂乱无章的情况。 快速排序是一种不稳定的排序，在递归调用时需快速排序是一种不稳定的排序，在递归调用时需要占据一定的存储空间用来保存每一层递归调用时的要占据一定的存储空间用来保存每一层递归调用时的必要信息。必要信息。 选择排序是指在排序过程序中，依次从待排序的选择排序是指在排序过程序中，依次从待排序的记录序列中选择出关键字值最小的记录、关键字值次记录序列中选择出关键字值最小的记录、关键字值次小的记录、小的记录、，并分别将它们定位到序列左侧的第，并分别将它们定位到序列左侧的第1个

35、位置、第二个位置、个位置、第二个位置、，最后剩下一个关键字值，最后剩下一个关键字值最大的记录位于序列的最后一个位置，从而使待排序最大的记录位于序列的最后一个位置，从而使待排序的记录序列成为按关键字值由小到大排列的的有序序的记录序列成为按关键字值由小到大排列的的有序序列。列。 8.4.1 8.4.1 简单选择排序简单选择排序1. 1. 简单选择排序的基本思想简单选择排序的基本思想 简单选择排序的基本思想是：每一趟在简单选择排序的基本思想是：每一趟在n-i+1(i=1,2,3,.,n-1)个记录中选取关键字最小的记录作为个记录中选取关键字最小的记录作为有序序列中的第有序序列中的第i个记录。它的具体

36、实现过程为：个记录。它的具体实现过程为： (1) 将整个记录序列划分为有序区域和无序区域，将整个记录序列划分为有序区域和无序区域，有序区域位于最左端，无序区域位于右端，初始状态有序区域位于最左端，无序区域位于右端，初始状态有序区域为空，无序区域含有待排序的所有有序区域为空，无序区域含有待排序的所有n个记录。个记录。 (2) 设置一个整型变量设置一个整型变量index，用于记录在一趟的，用于记录在一趟的比较过程中，当前关键字值最小的记录位置。开始将比较过程中，当前关键字值最小的记录位置。开始将它设定为当前无序区域的第一个位置，即假设这个位它设定为当前无序区域的第一个位置，即假设这个位置的关键字最

37、小，然后用它与无序区域中其他记录进置的关键字最小，然后用它与无序区域中其他记录进行比较，若发现有比它的关键字还小的记录，就将行比较，若发现有比它的关键字还小的记录，就将index改为这个新的最小记录位置，随后再用改为这个新的最小记录位置，随后再用aindex.key 与后面的记录进行比较，并根据比较结果，与后面的记录进行比较，并根据比较结果，随时修改随时修改index的值，一趟结束后的值，一趟结束后index中保留的就是本中保留的就是本趟选择的关键字最小的记录位置。趟选择的关键字最小的记录位置。 (3) 将将index位置的记录交换到无序区域的第一个位置的记录交换到无序区域的第一个位置，使得有

38、序区域扩展了一个记录，而无序区域减位置，使得有序区域扩展了一个记录，而无序区域减少了一个记录。少了一个记录。 不断重复不断重复 (2)、(3)，直到无序区域剩下一个记录为，直到无序区域剩下一个记录为止。此时所有的记录已经按关键字从小到大的顺序排止。此时所有的记录已经按关键字从小到大的顺序排列就位。列就位。3. 3. 简单选择排序算法简单选择排序算法简单选择排序的整体结构应该为：简单选择排序的整体结构应该为：for (i=1;in;i) 第第i趟简单选择排序；趟简单选择排序； 下面我们进一步分析一下下面我们进一步分析一下“第第i 趟简单选择排序趟简单选择排序”的算法实现。的算法实现。 （1）初始

39、化：假设无序区域中的第一个记录为关键）初始化：假设无序区域中的第一个记录为关键字值最小的元素，即将字值最小的元素，即将index=i; （2）搜索无序区域中关键字值最小的记录位置：）搜索无序区域中关键字值最小的记录位置：for (j=i+1;j =n;j+)if (aj.keya.index.ke) index=j; （3）将无序区域中关键字最小的记录与无序区域的）将无序区域中关键字最小的记录与无序区域的第一个记录进行交换，使得有序区域由原来的第一个记录进行交换，使得有序区域由原来的i-1个个记录扩展到记录扩展到i个记录。个记录。 完整算法：完整算法：void selecsort ( Data

40、Type a, int n) for( i=1; in; i+) /对对n个记录进行个记录进行n-1趟的简单选择排序趟的简单选择排序 index=i; /初始化第初始化第i趟简单选择排序的最小记录指针趟简单选择排序的最小记录指针 for (j=i+1;j=n;j+) /搜索关键字最小的记录位置搜索关键字最小的记录位置 if (aj.keyai.key) index=j; if (index!=i) temp=ai; ai=aindex; aindex=temp; 简单选择排序算法简单，但是速度较慢，并且是简单选择排序算法简单，但是速度较慢，并且是一种不稳定的排序方法一种不稳定的排序方法.，但在

41、排序过程中只需要一个，但在排序过程中只需要一个用来交换记录的暂存单元。用来交换记录的暂存单元。 8.4.2 8.4.2 堆排序堆排序1. 1. 堆排序的基本思想堆排序的基本思想 堆排序是另一种基于选择的排序方法。下面我们堆排序是另一种基于选择的排序方法。下面我们先介绍一下什么是堆？然后再介绍如何利用堆进行排先介绍一下什么是堆？然后再介绍如何利用堆进行排序。序。 堆定义：由堆定义：由n个元素组成的序列个元素组成的序列k1，k2，kn-1，kn，当且仅当满足如下关系时，称之为，当且仅当满足如下关系时，称之为堆堆。例如序列（例如序列（47，35，27，26，18，7，13，19）满足：）满足： 若将

42、堆看成是一棵以若将堆看成是一棵以k1为根的完全二叉树，则这为根的完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不大于（或棵完全二叉树中的每个非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此可以看出，若不小于）其左、右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，则根结点一定是这一棵完全二叉树是堆，则根结点一定是这n个结点中的个结点中的最小者或最大者。下面给出两个堆的示例。最小者或最大者。下面给出两个堆的示例。图图 8-11 下面我们讨论一下如何利用堆进行排序？下面我们讨论一下如何利用堆进行排序？ 从堆的定义可以看出，若将堆用一棵完全二叉树从堆的定义可以看出，若将堆用一棵完

43、全二叉树表示，则根结点是当前堆中所有结点的最小者（或最表示，则根结点是当前堆中所有结点的最小者（或最大者）。堆排序的基本思想是：首先将待排序的记录大者）。堆排序的基本思想是：首先将待排序的记录序列构造一个堆，此时，选出了堆中所有记录的最小序列构造一个堆，此时，选出了堆中所有记录的最小者或最大者，然后将它从堆中移走，并将剩余的记录者或最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小（或次大）的记录，再调整成堆，这样又找出了次小（或次大）的记录，以此类推，直到堆中只有一个记录为止，每个记录出以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。堆的顺序就是一

44、个有序序列。 3. 3. 堆排序算法堆排序算法 假设当前要进行筛选的结点编号为假设当前要进行筛选的结点编号为k，堆中最，堆中最后一个结点的编号为后一个结点的编号为m，且，且ak+1至至am之间的结之间的结点都已经满足堆的条件，则调整过程可以描述为：点都已经满足堆的条件，则调整过程可以描述为： (1) 设置两个指针设置两个指针i和和j： i指向当前（要筛选）的结点：指向当前（要筛选）的结点：i=k; j指向当前结点的左孩子结点：指向当前结点的左孩子结点：j=2*i; (2) 比较当前结点的左右孩子的关键字值，并比较当前结点的左右孩子的关键字值，并用用j指向关键字值较大的孩子结点。指向关键字值较大

45、的孩子结点。 if (jm & aj.keyaj.key) break; /结束筛选操作结束筛选操作 else temp=ai; ai=aj; aj=temp; /交换结点内容交换结点内容 i=j;j=2*i; /准备继续筛选准备继续筛选 可以将交换改进为：可以将交换改进为：if (ai.keyaj.key) break; else ai=aj; i=j; j=2*i; 堆排序的筛选算法：堆排序的筛选算法：void sift (DataType a,int k,int m) i=k;；j=2*i；temp=ai； while (j=m) / if ( j m & aj.key

46、aj .key) break； else ai=aj ；i=j；j=2*i； ai = temp；堆排序完整的算法。堆排序完整的算法。void heapsort (DataType a, int n) h=n/2 ; /最后一个非终端结点的编号最后一个非终端结点的编号 for ( i=h ; i=1; i-) /初建堆。从最后一个非终端结点至根结点初建堆。从最后一个非终端结点至根结点 sift ( a, i, n ) ; for ( i=n ; i1 ; i- ) /重复执行移走堆顶结点及重建堆的操作重复执行移走堆顶结点及重建堆的操作 temp=a1 ; a1=ai; ai=temp ; si

47、ft ( a , 1 , i-1 ); 在堆排序中，除建初堆以外，其余调整堆的过程在堆排序中，除建初堆以外，其余调整堆的过程最多需要比较树深次，因此，与简单选择排序相比时最多需要比较树深次，因此，与简单选择排序相比时间效率提高了很多；另外，不管原始记录如何排列，间效率提高了很多；另外，不管原始记录如何排列，堆排序的比较次数变化不大，所以说，堆排序对原始堆排序的比较次数变化不大，所以说，堆排序对原始记录的排列状态并不敏感。记录的排列状态并不敏感。 在堆排序算法中只需要一个暂存被筛选记录内容在堆排序算法中只需要一个暂存被筛选记录内容的单元和两个简单变量的单元和两个简单变量h和和i，所以堆排序是一种

48、速度，所以堆排序是一种速度快且省空间的排序方法。堆排序是一种不稳定的。快且省空间的排序方法。堆排序是一种不稳定的。 8.5.1 8.5.1 归并排序的基本思想归并排序的基本思想 归并排序是一种另一类排序方法。所谓归并是指归并排序是一种另一类排序方法。所谓归并是指将两个或两个以上的有序表合并成一个新的有序表。将两个或两个以上的有序表合并成一个新的有序表。归并排序的基本思想是将一个具有归并排序的基本思想是将一个具有n个待排序记录的序个待排序记录的序列看成是列看成是n个长度为个长度为1的有序列，然后进行两两归并，的有序列，然后进行两两归并，得到得到n/2 个长度为个长度为2的有序序列，再进行两两归并

49、，的有序序列，再进行两两归并，得到得到n/4 个长度为个长度为4的有序序列，如此重复，直至得的有序序列，如此重复，直至得到一个长度为到一个长度为n的有序序列为止。的有序序列为止。 8.5.3 8.5.3 归并排序算法归并排序算法 通常，我们将两个有序段合并成一个有序段的过通常，我们将两个有序段合并成一个有序段的过 程称为程称为2-路归并。路归并。 1.2-1.2-路归并算法路归并算法 假设记录序列被存储在一维数组假设记录序列被存储在一维数组a中，且中，且asam 和和am+1at 已经分别有序，现将它们已经分别有序，现将它们合并为一个有序段，并存入数组合并为一个有序段，并存入数组a1中的中的a

50、1sa1t之间。之间。 合并过程：合并过程： (1) 设置三个整型变量设置三个整型变量k、i、j，用来分别指向，用来分别指向a1s.t中当前应该放置新记录的位置，中当前应该放置新记录的位置，asam和和am+1at中当前正在处理的记录位置。初始值应中当前正在处理的记录位置。初始值应该为：该为：i=s; j=m+1; k=s; (2) 比较两个有序段中当前记录的关键字，将比较两个有序段中当前记录的关键字，将关键字较小的记录放置关键字较小的记录放置a1k，并修改该记录所属有，并修改该记录所属有序段的指针及序段的指针及a1中的指针中的指针k。重复执行此过程直到。重复执行此过程直到其中的一个有序段内容

51、全部移至其中的一个有序段内容全部移至a1中为止，此时需中为止，此时需要将另一个有序段中的所有剩余记录移至要将另一个有序段中的所有剩余记录移至a1中。其中。其算法实现如下：算法实现如下： while (i=m &j=t) if (ai.key=aj.key) a1k+=ai+; else a1k+=aj+; if (i=m) while (i=m) a1k+=ai+; else while (j=t) a1k+=aj+; 2-路归并的完整算法：路归并的完整算法：void merge (DataType a,DataType a1,int s,int m,int t)/asm和和am+1a

52、t已经分别有序，将它们归并已经分别有序，将它们归并至至a1sa1t中中 k=s; i=s; j=m+1; while(i=m & j=t) if (ai.key=aj.key) a1k+=ai+; else a1k+=aj+; if (i=m) /将剩余记录复制到数组将剩余记录复制到数组a1中中 while ( i=m) a1k+=ai+; if (j=t) while (j=t) a1k+=aj+;2. 2. 归并排序的递归算法归并排序的递归算法 归并排序方法可以用递归的形式描述，即首先将归并排序方法可以用递归的形式描述，即首先将待排序的记录序列分为左右两个部分，并分别将这两待排序的

53、记录序列分为左右两个部分，并分别将这两个部分用归并方法进行排序，然后调用个部分用归并方法进行排序，然后调用2-路归并算法，路归并算法，再将这两个有序段合并成一个含有全部记录的有序段。再将这两个有序段合并成一个含有全部记录的有序段。递归算法：递归算法：void mergesort (DataType a,DataType a1,int s,int t) if (s=t) a1s=as; else m= (s+t)/2; mergesort ( a, a2, s, m); mergesort (a, a2, m+1, t); merge (a2, a1, s, m, t); 2-路归并排序的递归算

54、法从程序的书写形式上看路归并排序的递归算法从程序的书写形式上看比较简单，但是在算法执行时，需要占用较多的辅助比较简单，但是在算法执行时，需要占用较多的辅助存储空间，即除了在递归调用时需要保存一些必要的存储空间，即除了在递归调用时需要保存一些必要的信息，在归并过程中还需要与存放原始记录序列同样信息，在归并过程中还需要与存放原始记录序列同样数量的存储空间，以便存放归并结果，但与快速排序数量的存储空间，以便存放归并结果，但与快速排序及堆排序相比，它是一种稳定的排序方法。及堆排序相比，它是一种稳定的排序方法。 8.6.1 8.6.1 基数排序的基本思想基数排序的基本思想 基数排序是一种基于多关键字的排

55、序方法。基数排序是一种基于多关键字的排序方法。1. 1. 多关键字排序多关键字排序 【举例】【举例】 将表将表8-1所示的学生成绩单按数学成绩的所示的学生成绩单按数学成绩的等级由高到低排序，数学成绩相同的学生再按英语成等级由高到低排序，数学成绩相同的学生再按英语成绩的高低等级排序。绩的高低等级排序。排序结果如表排序结果如表8-2所示。所示。 与前面几节所讲述的排序不同，在这个排序中，与前面几节所讲述的排序不同，在这个排序中，每个学生记录最终的位置由两个关键字决定。第每个学生记录最终的位置由两个关键字决定。第1关键关键字为数学成绩字为数学成绩k1，第二个关键字为英语成绩，第二个关键字为英语成绩k

56、2，则排，则排序后每一个学生成绩记录的位置由关键字序后每一个学生成绩记录的位置由关键字k1 k2决定，决定，我们将它称之为复合关键字，即多关键字排序是按照我们将它称之为复合关键字，即多关键字排序是按照复合关键字的大小排序。复合关键字的大小排序。 现在我们讨论一下多关键字排序的方法。下面我现在我们讨论一下多关键字排序的方法。下面我们以学生成绩单为例，给出通常采用的两种方法。第们以学生成绩单为例，给出通常采用的两种方法。第一种方法是先按数学等级由高到低将学生记录分成一种方法是先按数学等级由高到低将学生记录分成A、B、C、D、E五个子序列，然后再分别对每个子序列五个子序列，然后再分别对每个子序列按英

57、语成绩由高到低排序，这样就会得到一个优先按按英语成绩由高到低排序，这样就会得到一个优先按数学等级排序，在数学等级相同的情况下，再按英语数学等级排序，在数学等级相同的情况下，再按英语等级排序；第二种方法是先将学生记录按英语等级由等级排序；第二种方法是先将学生记录按英语等级由高到低分成高到低分成A、B、C、D、E 五个组：五个组：表表 8-3关键类别ABCDEAAABBCCDEABBCB各组成员DB 然后按从左向右，从上向下的顺序将它们收集然后按从左向右，从上向下的顺序将它们收集起来得到关键字序列：起来得到关键字序列：AA，EA，AB，BB，CB，DB，BC，CD 再按数学成绩由高到低分成再按数学

58、成绩由高到低分成A、B、C、D、E五五个组：个组： 表表 8-4关键类别ABCDEAABBCBDBEA各组成员ABBCCD 再按由高到低的顺序将它们收集起来，得到关再按由高到低的顺序将它们收集起来，得到关键字序列：键字序列：AA，AB，BB，BC，CB，CD，DB，EA 可以看出，这个关键字序列已经是有序的了。可以看出，这个关键字序列已经是有序的了。 在上述两种基于多关键字的排序方法中，第一种在上述两种基于多关键字的排序方法中，第一种方法是先按高位关键字进行排序，被称之为方法是先按高位关键字进行排序，被称之为“最高位最高位优先优先”法，简称法，简称MSD法；第二种方法是先按低位关键法；第二种方

59、法是先按低位关键字排序，被称之为字排序，被称之为“最低位优先最低位优先”法，简称为法，简称为LSD。从上面的例子可以看出：在从上面的例子可以看出：在MSD法中，先按高位关键法中，先按高位关键字将待排序数据分成子序列，然后再对各子序列按下字将待排序数据分成子序列，然后再对各子序列按下一个关键字排序；而使用一个关键字排序；而使用LSD法进行排序时，对每个法进行排序时，对每个关键字都是将整个序列按关键字分组，然后按顺序收关键字都是将整个序列按关键字分组，然后按顺序收集，显然集，显然LSD法，操作比较简单。法，操作比较简单。 2. 2. 基数排序基数排序 基数排序是借助于多关键字排序思想进行排序的基数排序是借助于多关键字排序思想进行排序的一种排序方法。该方法将排序关键字一种排序方法。该方法将排序关键字K看作是由多个看作是由多个关键字组成的组合关键字，即关键字组成的组合关键字，即K=k1k2kd。每个关键。每个关键字字ki表示关键字的一位，其中表示关键字的一位，其中k1为最高位，为最高位，kd为最低位，为最低位，d为关键字的位数。例如，对于关键字序列（为关键字的位数。例如，对于关键字序列（101，203 567，2