排序概念、种类和方法讲解

1、排序概念、种类和方法讲解第8章 排 序学习目的要求:掌握排序的概念和排序的种类。熟练掌握五类基本排序:插入排序、交换排序、选择排序、归并排序和基数排序的算法思想、算法实现和性能分析。8.1 排序的基本概念8.2 插入排序8.3 选择排序8.4 交换排序8.5 归并排序8.6 基数排序8.7 几种排序方法的比较第8章 排 序8.1 排序的基本概念假设含有n个记录的序列为R1，R2，Rn其相应的关键字序列为K1，K2，Kn一种排列P1，P2， ，Pn，使其相应的关键字满足如下非递减关系（满足非递增关系时，将“”号改为“”号）Kp1Kp2Kpn使n个记录的无序序列成为一个按关键字有序的序列Rp1 ，

2、Rp2 ，Rpn这样一种操作过程称为排序。排序：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。学生档案表学号姓名年龄性别99001王晓佳18男99002林一鹏19男99003谢宁17女99004张丽娟18女99005周涛20男99006李小燕16女8.1 排序的基本概念8.1 排序的基本概念排序过程中依据的不同原则，内部排序方法可大致分为插入排序、交换排序、选择排序、归并排序和基数排序等五类。评价排序算法优劣的标准：一是算法执行时所需的时间二是执行算法时所需要的附加空间执行排序的时间复杂性是算法优劣的重要的标志。影响时间复杂性的主要因素又可以用算法执行中的比较次数和移动

3、次数来衡量。在排序的过程中常需进行两种基本操作: 比较两个关键字的大小; 将记录从一个位置移动至另一个位置。8.1 排序的基本概念待排序的记录序列存储方式: 存放在地址连续的一组存储单元上，类似于线性表。排序时必须移动记录; 存放在静态链表中，记录之间的次序关系由指针指定，排序时不需要移动记录，仅需修改指针; 记录本身存储在一组地址连续的存储单元内，另设一个指示各个记录存储位置的地址向量，排序时仅需移动地址向量排序后再按照地址向量中的值调整记录的存储位置。8.1 排序的基本概念8.1 排序的基本概念若在排序期间具有相同键值的记录的相对位置不变，则称此排序方法是稳定的，否则称为不稳定的。8.2

4、插入排序插入排序（Insertion Sort）的基本思想:每次将一个待排序的记录，按其关键字的大小插入到前面已经排好序的有序序列中的适当位置上，直到全部记录插入完成为止。直接插入排序折半插入排序2路插入排序希尔排序8.2.1 直接插入排序直接插入排序（Straight Insertion Sort）是一种最简单的排序方法。基本操作：依次将记录序列中的每一个记录插入到有序序列中，使有序序列的长度不断地扩大。8.2 插入排序有序序列R1.i-1Ri无序序列 Ri.n一趟直接插入排序的基本思想：有序序列R1.i无序序列 Ri+1.n一共需要经过n-1趟就可以将初始序列的n个记录重新排列成按关键字值

5、大小排列的有序序列。过程如下:先将待排序记录序列中的第一个记录作为一个有序序列，将记录序列中的第二个记录插入到上述有序序列中形成由两个记录组成的有序序列，再将记录序列中的第三个记录插入到这个有序序列中，形成由三个记录组成的有序序列，如此进行下去，直到最后一个记录也插入完成。8.2 插入排序 初始关键字： (49) 38 65 97 76 13 27 49 i=2 (38) (38 49) 65 97 76 13 27 49 i=3 (65) (38 49 65) 97 76 13 27 49 i=4 (97) (38 49 65 97) 76 13 27 49 i=5 (76) (38 49

6、65 76 97) 13 27 49 i=6 (13) (13 38 49 65 76 97) 27 49 i=7 (27) (13 27 38 49 65 76 97) 49 i=8 (49) (13 27 38 49 49 65 76 97) 监视哨L.r0直接插入排序是稳定的。注意:第二条记录和第八条记录的相对位置在排序后没有发生变化，此排序算法是稳定的。8.2 插入排序直接插入排序算法简单、易实现，其算法的时间复杂度是O（n2）。从空间复杂度来看，只需要一个记录大小的辅助空间用于暂存待插入的记录。当待排序记录较少时，排序速度较快，反之，当待排序的记录数量较大时，大量的比较和移动操作将使

7、直接插入排序算法的效率降低;另外，若当待排序的数据元素基本有序时，排序过程中的记录移动次数会大大减少，从而效率会有所提高。直接插入排序是一种稳定的排序方法。8.2.2 折半插入排序折半插入排序是对直接插入排序的改进算法，它是利用折半查找来实现插入位置的定位，可减少排序过程中的比较次数。适用于待排序的记录数量较大的情况。8.2 插入排序一趟折半插入排序的步骤为: （1）初始化 将待插入的记录存入r0中:r0ri; 给指定查找区间上下界指针赋值:low1，high i-1; （2）折半查找插入位置; （3）将插入位置后面的记录依次后移一个位置; （4）将暂存在r0中的待插入记录放入找到的位置上。8

8、.2 插入排序14 36 49 52 8058 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置折半插入排序只减少关键字间的比较次数，而记录的移动次数不变。故折半插入排序的时间复杂度仍为 O（n2）。从空间复杂度来看，折半插入排序只需要一个记录大小的辅助空间用于暂存待插入的记录，这与直接插入排序相同。折半插入排序是一种稳定的排序方法。8.2 插入排序8.2.3 2-路插入排序2-路插入排序是对折半插入排序的改进算法，它是利用增加辅助空间来减少排序过程

9、中移动记录的次数，即“以空间换时间”。8.2 插入排序具体做法是:建立一个和待排序序列rn同类型的数组dn作为辅助空间。先将r0的值赋给d0，将d0看成是处于最后有序序列中处于中间位置的记录，再从r1开始依次将记录插入到d0之前或之后的有序序列中。将数组d看成是一循环向量（既首尾相连的环状空间），并设置两个指针first和final分别指向有序序列的第一条和最后一条记录，将当前待插入记录ri与d0比较，若riri+1），则交换其位置，经过多趟排序，最终使整个序列有序。假设在排序过程中,记录序列R1.n的状态为:第 i 趟起泡排序无序序列R1.n-i+1有序序列 Rn-i+2.nn-i+1无序序

10、列R1.n-i有序序列 Rn-i+1.n比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上8.4 交换排序处理过程为:第一趟:从第一条记录r1开始，直到最后一条记录rn，对两两相邻的记录依此比较，若发现为逆序，则立即交换其位置，最后使这n条记录中关键字最大的记录“下沉”到最底部，既被交换到第n个位置上，它不参与下一趟排序; 第二趟:从第一条记录r1开始，直到第n-1条记录rn-1，对两两相邻的记录依此比较，若发现为逆序，则立即交换其位置，最后使这n-1条记录中关键字最大的记录“下沉”到次底部，既被交换到第n-1个位置上，它不参与下一趟排序;如此反复，最多经过（n-1）趟冒泡排序，就可

11、以使整个序列成为有序序列。49 38 65 97 76 13 27 30 初始关键字38 49 65 76 13 27 30 97 第一趟38 49 65 13 27 30 76 第二趟38 49 13 27 30 65 第三趟38 13 27 30 49 第四趟13 27 30 38 第五趟13 27 30 第六趟38497697139727979730137676761365273065276530134949492730133827383038例如，一组待排序的记录的关键字如下，要求按照关键字由小到大进行排序。 42 36 56 78 67 11 27 368.4 交换排序初始状态423

12、656786711273678i=13642566711273667i=23642561127365678i=33642112736426778i=43611273636566778i=51127363642566778i=61127273642566778i=711363642566778冒泡排序的时间复杂度为O（n2），由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。冒泡排序只需要一个记录的辅助空间，用来作为记录交换的中间暂存单元。冒泡排序是一种稳定的排序方法。8.4 交换排序8.4.2 快速排序快速排序（Quick Sort）是对冒泡排序的一种改进。基本思想:通过一趟排序

13、将待排序记录划分成两部分，使得其中一部分记录的关键字比另一部分记录的关键字小;然后再分别对这两部分记录进行这种排序，直到每个部分为空或只包含一个记录时，整个快速排序结束。8.4 交换排序8.4 交换排序待排序的序列:（rs，rs-1，rt）先任意选取一个记录（通常可选第一个记录rs作为基准记录或称为支点），然后重新排列这些记录。将所有关键字较它小的记录都排到它的位置之前，将所有关键字较它大的记录都排到它的位置之后。由此可以将该基准记录所在的位置i作为分界线，将待排序记录序列划分成两个子序列（rs，ri-1）和（ri+1，rt）。这个过程称为一趟快速排序。一趟快速排序完成后得到前后两个子序列，可

14、再分别对分割后的两个子序列进行快速排序。整个快速排序过程结束。stlowhigh设 Rs=52 为支点 将 Rhigh.key 和 支点的关键字进行比较，要求Rhigh.key 支点的关键字 将 Rlow.key 和 支点的关键字进行比较，要求Rlow.key 枢轴的关键字high23low80high14low52例如R052lowhighhighhighlow例如，待排序记录的关键字为: 42 36 56 78 67 11 27 368.4 交换排序8.4 交换排序 首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无 序 的 记 录 序 列无序记录子

15、序列(1)无序子序列(2)支点一次划分分别进行快速排序例初始关键字： 49 38 65 97 76 13 27 50 ij支点ji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij快速排序的时间复杂度平均为 O（nlog2n），当n较大时， 这种算法是平均速度最快的排序算法，因此称为快速排序。快速排序是一种不稳定的排序方法。8.4 交换排序8.5 归并排序归并排序（M

16、erging Sort）:“归并”的含义是将两个或两个以上的有序序列合成一个新的有序序列。假设初始序列含有 n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到 n/2 个长度为2（最后一个序列长度可能小于2）的有序子序列;再两两归并，得到 n/2 /2 个长度为4（最后一个序列长度可能小于4）的有序序列;如此重复，直至得到一个长度为n的有序序列为止，每一次合并过程称为一趟归并排序，这种排序方法称为 2-路归并排序。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。有 序 序 列 Rl.n有序子序列 Rl.m有序子序

17、列 Rm+1.n这个操作对顺序表而言，是轻而易举的。例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23例如，设待排序的记录序列为: 42 36 56 78 67 11 27 36 2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。8.5 归并排序2-路归并排序算法的时间复杂度为 O（nlog2n）。 在排序时需利用一个与待排序数组同样大小的辅助数组，占用内存比前面介绍的算法多

18、。2-路归并排序算法是稳定的。8.5 归并排序8.6 基数排序基数排序（Radix Sorting）是和前面所述各类排序方法完全不同的一种排序方法。前面讨论的排序主要是通过关键字间的比较和移动记录这两种操作实现的，而基数排序不需要进行关键字间的比较。基数排序是借助多关键字排序的思想实现的。8.6.1 多关键字的排序8.6 基数排序例如，扑克牌中52张牌面的次序关系为: 2 3 A2 3 A 2 3 A 2 3 A 每一张牌有两个“关键字”:花色（ ）和面值（23A），且“花色”的地位高于“面值”，在比较任意两张牌面的大小时，必须先比较“花色”，若“花色”相同，则再比较面值。由此，将扑克牌整理成

19、如上所述次序关系时，通常采用的办法是:先按不同“花色”分成有次序的四堆，每一堆的牌均有相同的“花色”，然后分别对每一堆按“面值”大小整理有序。也可采用另一种办法:先按不同“面值”分成13堆，然后将这13堆牌自小至大叠在一起（“3”在“2”之上，“4”在“3”之上，最上面的是4张“A”）， 然后将这付牌整个颠倒过来再按不同“花色”分成4堆，最后将这4堆牌按自小至大的次序合在一起（ 在最下面，在最上面），此时同样得到一付满足如上次序的牌。这两种整理扑克牌的方法便是两种多关键字的排序方法。为了实现多关键字排序，通常有两种方法:第一种方法是先对最高位关键字K0进行排序，将序列分成若干子序列，每个子序列

20、中的记录都具有相同的K0值，然后分别对每个子序列按次高位关键字K1进行排序，按K1值不同再分成若干个更小的子序列，每个子序列中的记录都具有相同的K1值，依次重复，直至完成对Kd-1进行排序，最后将所有子序列依次连接在一起成为一个有序序列，这种方法称之为最高位优先 （Most Significant Digit First）法，简称MSD法;第二种方法是从最低位关键字Kd-1起进行排序，然后再对高一位的关键字Kd-2进行排序，依次重复，直到对K0进行排序后便成为一个有序序列。这种方法称之为最低位优先（Least Siginificant Digit First）法，简称LSD法。 8.6 基数排

21、序8.6 基数排序MSD和LSD只规定按什么样的“关键字次序”来进行排序，而未规定对每个关键字进行排序时所用的方法，比较这两种方法，LSD要比MSD简单，因为LSD是对每个关键字都是整个序列参加排序，通过若干次“分配”和“收集”来实现排序，执行的次数取决于d的大小;而MSD需要处理各序列与子序列的独立排序问题，通常是一个递归问题。8.6.2 链式基数排序基数排序是借助于多关键字排序思想进行排序的方法，其基本操作是按关键字位进行“分配”和“收集”。在基数排序的“分配”与“收集”操作过程中，为了避免数据元素的大量移动，通常采用链式存储结构存储待排序的记录序列。8.6 基数排序通常将关键字取值的数目

22、称为基数，用RADIX表示，按LSD进行排序，对待排序的记录序列按照复合关键字从低位到高位的顺序交替地“分配”到RADIX个队列中后再“收集”，如此重复d次，最终得到有序的记录序列。有些记录的关键字可以看成是由若干个关键字组合而成。即K=K0K1 .Kd-1。每个关键字Ki表示关键字的一位，其中K0为最高位，Kd-1为最低位，d为关键字的位数。8.6 基数排序下面举例说明基数排序过程。设待排序记录的关键字为:387，456，592，625，076，471，050，396，557，5228.6 基数排序8.6 基数排序8.6 基数排序从基数排序的算法中容易看出，对于n个记录（假设每个记录含d个关键字，每个关键字的取值范围为r），则采用基数排序需进行d趟关键字的分配和收集，每趟运算时间复杂度为O（n+r），所以基数排序的时间复杂度为O（d（n+r）。由于d、r是常数，当n较大时，基数排序的时间复杂度近似为O（n）。但n较小，d较大时，采用基数排序并不合 适;只有当n较大、d较小时，基数排序才最为有效。这种排序方法的缺点是占用的存储空间较多，每个待排序的记录都需要