数据结构(C语言版)：第10章排序

1、内部排序,教学内容 1、插入排序（直接插入排序、折半插入排序、 希尔排序）； 2、交换排序（起泡排序、快速排序）； 3、选择排序（直接选择排序、堆排序）； 4、归并排序； 5、基数排序；,排序：将数据元素的一个任意序列，重新排列成一个按关键 字有序的序列。,10.1 概述,例：将关键字序列：52, 49, 80, 36, 14, 58, 61, 23,调整为：14, 23, 36, 49, 52, 58, 61, 80,若按主关键字排序则结果惟一。,若按次关键字排序则结果可以不惟一（因有相同关键字）。,设 Ki、Kj (1in, 1jn, ij ) 分别为记录 Ri、Rj 的关键 字，且 Ki

2、 = Kj ，在排序前的序列中 Ri 领先于 Rj（即 i j ）。若 在排序后的序列中 Ri 仍领先于 Rj ，则称所用的排序方法是稳定 的；反之，则称所用的排序方法是不稳定的。,例：设排序前的关键字序列为：52, 49, 80, 36, 14, 58, 36, 23 若排序后的关键字序列为：14, 23, 36, 36, 49, 52, 58, 80， 则排序方法是稳定的。 若排序后的关键字序列为：14, 23, 36, 36, 49, 52, 58, 80， 则排序方法是不稳定的。,内部排序和外部排序,若整个排序过程不需要访问外存便能完成，则称此类排序 问题为内部排序；,反之，若参加排序

3、的记录数量很大，整个序列的排序过程 不可能在内存中完成，则称此类排序问题为外部排序。,排序方法分类：,1)、插入排序：直接插入排序、折半插入排序、希尔排序,2)、交换排序：冒泡排序、快速排序,3)、选择排序：简单选择排序、堆排序,4)、归并排序：2-路归并排序,5)、基数排序,10.2 插入排序,有序序列 R1 . i -1,Ri,无序序列 Ri . n,一趟直接插入排序的基本思想：,有序序列 R1 . i,无序序列 Ri +1 . n,实现“一趟插入排序”可分三步进行：,3将 Ri 插入（复制）到 R j+1 的位置上。,2将 R j+1 . i -1 中的所有记录均后移一个位置；,1在 R

4、1 . i -1 中查找 Ri 的插入位置， R1 . j.key Ri.key R j+1 . i -1.key；,10.2.1 直接插入排序,i =2,38,49,38,7 趟 排序,1 趟 排序,2 趟 排序,void InsertSort ( SqList + i ) if (L.ri.key L.ri -1.key) / InsertSort,排序过程：先将序列中第 1 个记录看成是一个有序子序列， 然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。,在 R1. i-1中查找 Ri 的插入位置; 对于在查找过程中找到的那些关键字 不小于 Ri.key 的记录，在查找的同 时实

5、现记录向后移动； 插入 Ri ;,L.r0 = L.ri; / 复制为监视哨 L.ri = L.ri -1; for ( j = i - 2; L.r0.key L.r j .key; - - j ) L.r j + 1 = L.r j ; / 记录后移 L.r j + 1 = L.r0; / 插入到正确位置,比较次数和移动次数均约为：,T(n)=O(n),算法评价,时间复杂度：,比较次数：,移动次数：0,最好的情况：待排序记录按关键字从小到大排列（正序）,比较次数：,移动次数：,最坏的情况：待排序记录按关键字从大到小排列（逆序）,一般情况：待排序记录是随机的，取平均值。,空间复杂度：S(n)

6、=O(1),直接插入排序是稳定排序,10.2.2 其他插入排序,1、折半插入排序：用折半查找方法确定插入位置的排序。,void BInsertSort ( SqList / 插入 /for / BInsertSort,i =1 (30) 13 70 85 39 42 6 20,i =7 6 (6 13 30 39 42 70 85 ) 20,i =8 20 (6 13 20 30 39 42 70 85 ),T(n)=O(n),时间复杂度：,空间复杂度：S(n)=O(1),折半插入排序是稳定排序,仅减少了比较次数， 移动次数不变。,第二趟希尔排序,第三趟分组，设 d3 = 1,10.2.3 希

7、尔排序（缩小增量排序）,基本思想：对待排序列先作“宏观”调整，再作“微观”调整。,排序过程：先取一个正整数 d1 n，把所有相隔 d1 的记录放 在一组内，组内进行直接插入排序；然后取 d2 d1，重复上述分 组和排序操作；直至 di = 1，即所有记录放进一个组中排序为止。 其中 di 称为增量。,例：,第一趟希尔排序,第三趟希尔排序,第一趟分组，设 d1 = 5,49 38 65 97 76 13 27 49 55 04,13 27 49 55 04 49 38 65 97 76,第二趟分组，设 d2 = 3,希尔排序特点：,分组不是简单的“逐段分割”，而是将相隔某个增量的记录组成 一个子

8、序列。,增量序列取法 希尔最早提出的选法是 d1 = n/2，di +1 = di /2。 克努特 (Knuth) 提出的选法是 di +1 =(di-1) /3。 还有其他不同的取法。 如何选择增量序列以产生最好的排序效果，至今仍没有从数学 上得到解决。 1)、没有除 1 以外的公因子； 2)、最后一个增量值必须为 1。,希尔排序可提高排序速度 1)、记录跳跃式前移，在进行最后一趟排序时，已基本有序。 2)、分组后 n 值减小，n2 更小，而 T(n)=O(n2)，所以 T(n) 从 总体上看是减小了。,3、重复直到 “在一趟排序 过程中没有进行过交换记录的操 作” 或“仅第一二个交换过”

9、为止。, 冒泡排序算法,10.3 交换排序,1、冒泡排序,1、比较第一个记录与第二个 记录，若关键字为逆序则交换；然 后比较第二个记录与第三个记录； 依次类推，直至第 n -1 个记录和第 n 个记录比较为止第一趟冒泡 排序，结果关键字最大的记录被安 置在最后一个记录上。,2、对前 n-1 个记录进行第二 趟冒泡排序，结果使关键字次大的 记录被安置在第 n-1 个记录位置。,第 一 趟 排 序,49,38,49,97,76,97,97,13,97,97,27,97,97,49,97,38 49 65 76 13 27 49 97,38 49 65 13 27 49 76,第 二 趟 排 序,3

10、8 49 13 27 49 65,第 三 趟 排 序,38 13 27 49 49,第 四 趟 排 序,13 27 38 49,第 五 趟 排 序,13 27 38,第 六 趟 排 序,for ( j = 1; j n ; j + +) if ( r j +1 r j ) r j r j + 1 ;,for ( j = 1; j n -1; j + +) if ( r j +1 r j ) r j r j + 1 ;,for ( i = n; i 1; i - - ),i ;,while ( i 1) , / while,i = n ;,i = k ;,Void BubbleSort(SqLi

11、st /交换的位置,k = 1 ;,排序过程,一般情况下每经过 一趟“起泡”，“ i 减 1”， 但并不是每趟都如此。,例：,i = 6,i = 2,i = 1,算法评价,时间复杂度：,最好情况（正序）,比较次数：n -1 移动次数：0 T(n) = O(n),最坏情况（逆序）,比较次数： 移动次数：,T(n) = O(n2),空间复杂度：S(n) = O(1),稳定性：稳定排序,s,一般取第一个记录,基本思想：任选一个记录，以它的关键字作为“枢轴”，凡关 键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录 均移至枢轴之后。,2、一趟快速排序（一次划分）,low,high,设 Rs=52

12、 为枢轴。,例：,52,t,附设两个指针 low 和 high，从 high 所指位置起向前搜索找 到第一个关键字小于枢轴的关键字的记录与枢轴记录交换，然后 从 low+1 所指位置起向后搜索找到第一个关键字大于枢轴的关键 字的记录与枢轴记录交换，重复这两步直至 low = high 为止。,high,23,low,low,80,high,high,high,high,14,low,low,52,快速排序过程,3、快速排序,首先对无序的记录序列进行“一次划分”，之后分别对分割 所得两个子序列“递归”进行一趟快速排序。,无 序 的 记 录 序 列,无序记录子序列 (1),无序子序列 (2),枢轴

13、,一次划分,分别进行一趟快速排序,有 序 的 记 录 序 列,若待排记录的初始状态为按关键字有序时，快速排序将蜕 化为起泡排序，其时间复杂度为 O(n2)。 所以快速排序适用于 原始记录排列杂乱无章的情况。,为避免出现蜕化情况，需在进行一次划分之前，进行“预 处理”，即：先对 R(s).key, R(t).key 和 R(s+t)/2.key，进行 相互比较，然后取关键字的大小为中间的记录为枢轴记录。,到目前为止快速排序是平均速度最大的一种排序方法。 时间复杂度为 O(n log n)。,快速排序是一种不稳定的排序，在递归调用时需要占据 一定的存储空间用来保存每一层递归调用时的必要信息。,10

14、.4 选择排序,10.4.1 简单选择排序,排序过程： 首先通过 n 1 次关键字比较，从 n 个记录中找出关键字最小 的记录，将它与第一个记录交换。 再通过 n 2 次比较，从剩余的 n 1 个记录中找出关键字次小 的记录，将它与第二个记录交换。 重复上述操作，共进行 n 1 趟排序后，排序结束。,j+,if (L.rj.key L.rk.key) k = j;,j = i+1;,for (i = 1; i L.length; + i) ,例：,初始： 49 38 65 97 76 13 27 ,i =1,13,49,一趟： 13 38 65 97 76 49 27 ,i =2,二趟： 13

15、 27 65 97 76 49 38 ,三趟： 13 27 38 97 76 49 65 ,四趟： 13 27 38 49 76 97 65 ,五趟： 13 27 38 49 65 97 76 ,六趟： 13 27 38 49 65 76 97 ,排序结束：六趟： 13 27 38 49 65 76 97,k = i;,for ( j = i+1; j = n; j+) if (L.rj.key L.rk.key) k = j;,if (i != k) L.riL.rk; / 与第 i 个记录交换,i =6,void SelectSort (SqList &L) / 对顺序表 L 作简单选择排

16、序。, / SelectSort,i =3,i =4,i =5,比较次数,n - 1,n - 2,n - 6,比较次数：,移动次数：,正序：最小值为 0；,最大值为 3(n-1) 。,例：前 n 1 个为正序，第 n 个记录的关键字最小。,时间复杂度：O(n2),空间复杂度：O(1),不稳定,10.4.3 堆排序,堆的定义：n 个元素的序列 (k1, k2, , kn)，当且仅当满足下 列关系时，称之为堆。,或,(i = 1, 2, , n/2),ki k2i ki k2i+1,ki k2i ki k2i+1,小顶堆,大顶堆,小根堆,正 堆,大根堆,逆 堆,例1： (96, 83, 27, 3

17、8, 11, 09),例2： (13, 38, 27, 49, 76, 65, 49, 97),可将堆序列看成完全二叉树，则： k2i 是 ki 的左孩子； k2i+1 是 ki 的右孩子。 所有非终端结点的值均不大（小）于其左右孩子结点的值。 堆顶元素必为序列中 n 个元素的最小值或最大值。,堆排序：,堆排序需解决的两个问题： 1、如何由一个无序序列建成一个堆？ 2、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？,将无序序列建成一个堆，得到关键字最小（大）的 记录；输出堆顶的最小（大）值后，将剩余的 n-1 个元 素重又建成一个堆，则可得到 n 个元素的次小值；如此 重复执行，直到堆中只

18、有一个记录为止，每个记录出堆 的顺序就是一个有序序列，这个过程叫堆排序。,堆,堆,筛选,所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉 树，“调整”根结点使整个二叉树也成为一个堆。,第二个问题解决方法筛选：,输出堆顶元素后，以堆中最后一个元素替代之；然后将根 结点值与左、右子树的根结点值进行比较，并与其中小（大） 者进行交换；重复上述操作，直至叶子结点，将得到新的堆， 称这个从堆顶至叶子的调整过程为“筛选”。,97,97,27,97,49,97,38,97,97,49,65,65,49,76,49,76,97,97,65,76,27,65,49,38,49,97,13,76,对深度为 k

19、 的堆，“筛选” 所需进行的关键字比较的次数 至多为 2(k-1)。,81,73,64,27,98,12,第一个问题解决方法： 从无序序列的第 n/2 个元素（即无序序列对应的完全二叉 树的最后一个内部结点）起，至第一个元素止，进行反复筛选。,建堆是一个从下往上进行“筛选”的过程。,例: 排序之前的关键字序列为：,40,55,49,36,12,36,73,49,98,81,98,49,40,现在，左/右子树都已经调整为堆，最后只要调整根结点，使 整个二叉树是个“堆”即可。,81,73,55,堆排序的时间复杂度和空间复杂度：,1. 对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多 为

20、2(k-1)；,3. 调整“堆顶” n-1 次，总共进行的关键字比较的次数不超过 2 (log2(n-1)+ log2(n-2)+ +log22) 2n(log2n),因此，堆排序的时间复杂度为 O(nlogn)，与简单选择排序 O(n2) 相比时间效率提高了很多。,2. 对 n 个关键字，建成深度为 h(=log2n+1) 的堆，所需进行的 关键字比较的次数至多 4n；,空间复杂度：S(n) = O(1),堆排序是一种速度快且省空间的排序方法。,不稳定。,10.5 归并排序,归并：将两个或两个以上的有序表组合成一个新的有序表。,在内部排序中，通常采用的是 2-路归并排序。即：将两个 位置相邻

21、的记录有序子序列归并为一个记录有序的序列。,初始关键字： 49 38 65 97 76 13 27,一趟归并后： 38 49 65 97 13 76 27,二趟归并后： 38 49 65 97 13 27 76,三趟归并后： 13 27 38 49 65 76 97,看成是 n 个有序的子 序列（长度为 1）， 然后两两归并。,得到 n/2 个长度为 2 或 1 的有序子序列。,空间复杂度为：O(n)。 时间复杂度为：O(nlog2n)。 稳定。,每趟归并的时间复杂度为O(n)，共需进行 log2n 趟。,10.6 基数排序,基数排序是一种借助“多关键字排序”的思想来实现“单关键 字排序”的内

22、部排序算法。,10.6.1 多关键字的排序,例：将右表所示的学生 成绩单按数学成绩 的等级由高到低排 序，数学成绩相同 的学生再按英语成 绩的高低等级排序。,105 A A 102 A B 104 B B 101 B C 108 C B 103 C D 106 D B 107 E A,特点：每个记录最终的 位置由两个关键 字 k1 k2 决定。,第二关键字 K2,第一关键字 K1,我们将它称之为复 合关键字，即多关键字 排序是按照复合关键字 的大小排序。,例：扑克牌中 52 张牌，可按花色和面值分成两个“关键字”，其 大小关系为：花色： 面值： 2345678910JQKA,若对扑克牌按花色、

23、面值进行升序排序，得到如下序列： 2, 3, ., A, 2, 3, ., A, 2, 3, ., A, 2, 3, ., A,即两张牌，若花色不同，不论面值怎样，花色低的那张牌小 于花色高的，只有在同花色情况下，大小关系才由面值的大小确 定。这也是按照复合关键字的大小排序，即：多关键字排序。,多关键字排序的方法：,n 个记录的序列 R1, R2, , Rn 对关键字 (Ki0, Ki1, , Kid-1) 有序是指：对于序列中任意两个记录 Ri 和 Rj (1i jn) 都满 足下列（词典）有序关系：(Ki0, Ki1, , Kid-1) (Kj0, Kj1, , Kjd-1),其中：K 0

24、 被称为 最主位关键字， Kd-1 被称为最次位关键字。,多关键字排序按照从最主位关键字到最次位关键字或从最次 位关键字到最主位关键字的顺序逐次排序，分两种方法：,最高位优先法，简称 MSD 法：先按 k 0 排序分组，同一组中 记录，关键字 k 0 相等，再对各组按 k 1 排序分成子组，之后，对 后面的关键字继续这样的排序分组，直到按最次位关键字 k d 对 各子组排序后，再将各组连接起来，便得到一个有序序列。,3,1,20,1,2,15,2,3,18,1,2,15,无序序列,3,2,30,最低位优先法，简称 LSD 法：先从 k d-1 开始排序，再对 k d-2 进行排序，依次重复，直

25、到对 k 0 排序后便得到一个有序序列。,例：学生记录含三个关键字： 系别、班号和班内的序列号， 其中以系别为最主位关键字。,对K2排序,对K1排序,对K0排序,3,1,20,2,1,20,2,3,18,3,1,20,2,1,20,3,2,30,2,1,20,1,2,15,3,2,30,2,3,18,1,2,15,2,1,20,2,3,18,3,1,20,3,2,30,LSD的排序过程如下：,对 Ki (0id -2) 进行排序时，只能用 稳定的排序方法。,例：先将学生记录按英语等级由高到低分成 A、B、C、D、E 五 个组：,用 LSD 法进行的排序，在一定的条件下（即对 Ki 的不同值 K

26、i+1 均取相同值），可通过若干次“分配”和“收集”来实现。,然后按从左向右，从上向下的顺序将 它们收集起来得到关键字序列： AA，EA，AB，BB，DB，CB，BC，CD,再按数学成绩由高到低分成 A、B、C、D、E 五个组：,可以看出，这个关键字序列已经是有序的了。,AA，AB，BB，BC，CB，CD，DB，EA,对每个关键字都是将整个序列按关键字分组，然后按顺序收 集，显然LSD法，操作比较简单。,按从上向下，从左向 右的顺序将其收集起 来得到关键字序列： AA，EA，AB，BB， DB，CB，BC，CD,按从上向下，从左向 右的顺序将其收集起 来得到关键字序列：,MSD 与 LSD 的

27、不同特点,必须将序列逐层分 割成若干子序列， 然后对各子序列分 别排序。,不必分成子序列， 对每个关键字都是 整个序列参加排序； 通过若干次分配与 收集实现排序。,LSD,MSD,基数排序：,是借助于多关键字排序思想进行排序的一种排序方法。该 方法将排序关键字K 看作是由多个关键字组成的组合关键字， 即：K=k0k1kd-1。每个关键字 ki 表示关键字的一位，其中 k0 为最高位，kd-1 为最低位，d 为关键字的位数。,例：对于关键字序列 (101, 203, 567, 231, 478, 352)，可以将每个 关键字 K 看成由三个单关键字组成，即 K= k1k2k3， 每个关键字 的取

28、值范围为 0ki9，所以每个关键字可取值的数目为 10。 通常将关键字取值的数目称为基数，用 r 表示，在本例中 r =10。,对于关键字序列（AB, BD, ED）可以将每个关键字看成是 由二个单字母关键字组成的复合关键字，并且每个关键字的取 值范围为 “AZ”，所以关键字的基数 r = 26。,基数排序可用多关键字的LSD方法排序，即对待排序的记 录序列按复合关键字从低位到高位的顺序交替地进行“分组”、 “收集”，最终得到有序的记录序列。在此我们将一次“分组”、 “收集”称为一趟。对于由 d 位关键字组成的复合关键字，需要 经过d 趟的“分配”与“收集”。 因此，若 d 值较大，基数排序的

29、 时间效率就会随之降低。,在计算机上实现基数排序时，为减少所需辅助存储空间， 应采用链表作存储结构，即链式基数排序，具体作法为：,10.6.2 链式基数排序,1、以静态链表存储待排记录，并令表头指针指向第一个记录；,2、“分配” 时，按当前“关键字位”所取值，将记录分配到不同 的 “链队列” 中，每个队列中记录的 “关键字位” 相同；,3、“收集”时，按当前关键字位取值从小到大将各队列首尾相 链成一个链表；,4、对每个关键字位均重复 2 和 3 两步。,例：,以静态链表存储待排记录，并令表头指针指向第一个记录。,“分配” 时，按当前“关键字位”所取值，将记录分配到不同的“链队列” 中，每个队列中记录的 “关键字位” 相同。,时间复杂度：,算法评价：,分配（每趟）：T(n)=O(n),收集（每趟）：T(n)=O(rd),T(n)=O(d(n+rd),空间复杂度：S(n)=2rd 个队列指针 + n 个指针域空间,假设：n 记录数 d 关键字数 rd 关键字取值范围 （如十进制为10）,一、时间性能,时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序，其中以