第第3 3章章 排序基排序基础础广东工业大学广东工业大学计算机学院计算机学院数据结构3.1 排序的概念与分类3.1.1 排序的概念3.1.2 排序的分类3.2 直接插入排序3.3 希尔排序3.4 基数排序3.4.1 多关键字排序3.4.2 基数排序第第3章章 排序基础排序基础3.1 排序的概念与分类排序的概念与分类u含有多个域的数据元素称为记录。u用于对记录进行唯一标识的域称为关键字。u为了与元素类型ElemType区别，记录类型定义为RecordType。typedef int KeyType; / 关键字类型为整数类型typedef struct KeyType key; / 关键字项 / 其它数据项 RecordType, RcdType; / 记录类型3.1.1 排序的概念排序的概念u排序是将一组“无序”的记录序列调整为“有序”的记录序列。u例如，将下列关键字序列： （175, 85, 260, 63, 412, 504, 840, 518, 630, 950）u调整为有序序列： （63, 85, 175, 260, 412, 504, 518, 630, 840, 950）什么是排序什么是排序u假设含n个记录的序列为（r1, r2, , rn）其相应的关键字序列为 （k1, k2, , kn）u这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 kp1kp2kpnu按此固有关系将上式记录序列重新排列为 （rp1, rp2, ，rpn ）的操作称作排序排序。记录顺序表的类型定义记录顺序表的类型定义typedef struct RcdType *rcd; / 存储空间基址 int length; / 当前长度 int size; / 存储容量 RcdSqList; / 记录的顺序表u注意：顺序表的0号单元闲置或用作哨兵。u在后面的讨论中，前后文意思清楚的情况下，约定：n把“记录的关键字的大小”和“记录的关键字的比较”简称为“记录的大小”和“记录的比较”。n将“元素的关键字的大小”和“结点的关键字大小”简称为“元素的大小”和“结点的大小”。3.1.2 排序的分类排序的分类u根据在排序过程中涉及的存储器不同，可将排序方法分为两大类：内部排序和外部排序。u内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。u外部排序指的是大文件的排序，待排序的文件无法一次装入内存，将待排序的记录存储在外存储器上，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。内部排序的分类内部排序的分类u内部排序方法分为五类：交换排序、选择排序、插入排序、归并排序和基数排序。u其中交换排序、选择排序和插入排序是一个逐步扩大记录的有序序列长度的过程。有序序列区无 序 序 列 区有序序列区无 序 序 列 区排序的介绍排序的介绍u交换排序是对无序区中记录的关键字两两进行比较，若逆序则交换，直到关键字之间不存在逆序为止。冒泡排序和快速排序是交换排序中最典型的两个方法。u选择排序是在无序区中选出关键字最小的记录，置于有序区的最后，直到全部记录有序。简单选择排序和堆排序是选择排序中最典型的两个方法。2134521345排序的介绍排序的介绍u插入排序是将无序区中的一个记录插入至有序区，使得有序区的长度加1，直到全部记录有序。直接插入排序和希尔排序是插入排序中最具代表性的两个方法。u归并排序是不断将两个或两个以上有序区合并成一个有序区，直到全部记录有序。u基数排序是和前面所述各类排序方法完全不同的一种排序方法，不需要进行记录关键字的比较。21345排序算法的时间复杂度分类排序算法的时间复杂度分类u内部排序方法按时间复杂度分为三类：n简单的排序方法，时间复杂度为O(n2)；n先进的排序方法，时间复杂度为O(nlogn)；n基数排序，时间复杂度为O(n)。u希尔排序的算法时间复杂度与增量序列有关，还涉及到一些数学上尚未解决的难题，其算法时间复杂度不属于以上类别。u每一种排序方法都有各自的优缺点，适合于不同的应用场合。u为方便起见，若非特意强调，排序的实施均为非递减有序排序。直接插入排序直接插入排序u假如8个记录的关键字序列为（56, 68, 25, 45, 90, 38, 10, 72）,每一趟的排序过程可参看下图：u第i趟插入排序将记录L.rcdi+1插入到有序区L.rcd1.i中，插入前需要找到插入位置，移动记录空出插入位置。45 456890算法实现分析算法实现分析u查找插入位置从有序区的位置1到i，判断是否为记录L.rcdi+1的插入位置j，代码为：j = 1; while (L.rcdj.keyj) L.rcdk+1 = L.rcdk; k-; / 从后到前移动记录u若将判断插入位置的次序改为从i到1，则可将上述两步的代码合并为：L.rcd0 = L.rcdi+1; j = i; while(j0 & L.rcd0.key0”可以略去。L.rcd0起到了边界监视哨的作用，称为哨兵。直接插入排序直接插入排序void InsertSort (RcdSqList &L )u设置哨兵u查找插入位置，移动记录空出插入位置u插入记录void InsertSort(RcdSqList &L) / 对顺序表L作直接插入排序。int i, j;for(i = 1; iL.length; +i) if(L.rcdi+1.keyL.rcdi.key) / 需将L.rcdi+1插入有序序列L.rcd0 = L.rcdi+1; / 先将记录L.rcdi+1保存在空闲的0号单元j = i;while(L.rcd0.keyL.rcdj.key) L.rcdj+1 = L.rcdj; j-;/ 记录后移 ; / 判断是否需要继续移动 L.rcdj+1 = L.rcd0; / 插入 0381 jii+1254556689010723838直接插入排序算法性能分析直接插入排序算法性能分析u排序算法的时间耗费主要与关键字比较和记录移动的次数相关。u最好的情况（关键字在记录序列中顺序有序）“比较比较”的次数：的次数：“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：u直接插入排序的最好情况下时间复杂度为O(n)，最坏情况下时间复杂度为O(n2)。u最坏的情况（关键字在记录序列中逆序有序）u直接插入排序只需要一个记录的辅助空间，其空间复杂度为O(1)。希尔排序希尔排序u希尔排序希尔排序是将整个待排记录序列 （R1, R2, R3, , Rn）u按增量d划分成d个子序列，其中第i（1id）个子序列为 （Ri, Ri+d, Ri+2d, , Ri+kd）13553876270465494997123456789103.3 希尔排序希尔排序u分别对各子序列进行直接插入排序；u不断减小增量d，重复这一过程；u直到d减少到1，对整个序列进行一次直接插入排序。u增量d的取值序列称为增量序列。基于增量序列的降序特点，希尔排序也被称为“缩小增量排序”。希尔排序实例希尔排序实例u待排序列（49, 38, 65, 97, 76, 13, 27, 49, 55, 04）u第一趟排序的增量d1为5 u结果为（13, 27, 49, 55, 04, 49, 38, 65, 97, 76） 13492738 65499755760412345678910希尔排序实例希尔排序实例u第二趟希尔排序的增量d2为3u结果为（13, 04, 49, 38, 27, 49, 55, 65, 97, 76）u第三趟的增量d3为1，最后结果为（04, 13, 27, 38, 49, 49, 55, 65, 76, 97）1355387627046549499712345678910希尔排序与直接插入排序希尔排序与直接插入排序u直接插入排序每次对相邻记录进行比较，记录最多只移动了一个位置，希尔排序每次对相隔较远距离（即增量）的记录进行比较，使得记录移动时能跨过多个记录，实现宏观上的调整。 u希尔排序的最后一趟排序（增量为1 ），序列已基本有序，接近最好情况（微观调整）的直接插入排序。u可将前面各趟的“宏观”调整看成是最后一趟的预处理，实现比只做一次直接插入排序效率更高。 void ShellInsert(RcdSqList &L, int dk) / 对顺序表L作一趟希尔排序，增量为dk int i, j; for(i = 1; i=L.length-dk; +i) if(L.rcdi+dk.key 0 & L.rcd0.keyL.rcdj-dk.key); / 判断是否需要继续移动 L.rcdj = L.rcd0; / 插入 一趟希尔排序一趟希尔排序void ShellInsert(RcdSqList &L, int dk)u暂存待插入记录u按增量dk查找插入位置,移动记录空出插入位置u插入记录049i-3jii+31304495527653897763838希尔排序希尔排序void ShellSort(RcdSqList &L, int d, int t) / 按增量序列d0.t-1对顺序表L作希尔排序 int k; for( k = 0; kt; +k ) ShellInsert(L, dk); /一趟增量为dk的插入排序 希尔排序的时间复杂度分析希尔排序的时间复杂度分析u希尔排序的时间复杂度分析是一个复杂的问题，因为它的时间复杂度是所取增量序列的函数，这涉及到一些数学上尚未解决的难题。u有研究指出，当增量序列为dk=2t-k+1-1时，希尔排序的时间复杂度为O(n1.5)，其中t为排序趟数，1ktlog2(n+1) 。排序的稳定性排序的稳定性u假设ki = kj (1in,1jn,ij)，且在排序前的序列中ki领先于kj (即i j)。若在排序后的序列中ki仍领先于kj，则称所用的排序方法是稳定的稳定的；否则，排序方法是不稳定的不稳定的。u从希尔排序的例子可见，序列有两个49，后一个49在排序后排到了49前面，因此希尔排序是不稳定的排序算法。3.4 基数排序基数排序u前面介绍的排序方法都基于关键字比较，而基数排序不需要比较关键字。u基数排序借鉴多关键字排序的思想，把关键字看成由多个关键字复合而成。3.4.1 多关键字排序多关键字排序u一般情况下，多关键字排序的定义为：假设含有 n 个记录的序列为（r1, r2, , rn）u每个记录ri含有 m 个关键字（ki0，ki1，kim-1），如果对于序列中任意两个记录ri 和rj（1ijn）都满足下列有序关系：（ki0，ki1，kim-1）（kj0，kj1，kjm-1）u则称记录序列对这m个关键字有序。其中k0被称作最主位关键字，km-1被称作最次位关键字；u(a0, a1, , am-1) (b0, b1, , bm-1)是指必定存在l，使得：当s = 0, , l-1时，as=bs ， 而albl。实现多关键字排序策略实现多关键字排序策略u高位优先排序高位优先排序n先按最主位关键字k0进行排序，得到若干子序列，其中每个子序列中的记录都含相同的k0值；n接着分别就每个子序列按关键字k1进行排序，致使k1值相同的记录构成长度更短的子序列；n依次重复，直至就当前得到的各个子序列按km-1 进行从小到大进行排序；n最后由这些子序列依次相连所得序列便是排序的最后结果。u低位优先排序低位优先排序n先按最低位关键字进行排序 ；n接着按次低位关键字实施排序 ；n最后按最主位关键字进行排序。n与高位优先排序不同，其排序过程中不产生子序列，每趟都是对整个序列进行排序。实例实例u现需要学生实施多关键字的排序，其中年级、班别和学号为关键字序列，且年级为最主位关键字。u若采用低位优先排序法，先按学号进行排序u接着按班别进行排序u最后按年级进行排序u低位优先排序必须使用稳定的排序算法黄红黄红张晗张晗4444黄红黄红张晗张晗基数排序基数排序u将记录的关键字看成由m个关键字复合而成，每个关键字可能取r个值，则只要从最低位关键字起，先按关键字的不同值将记录“分配”到r个子序列，再按从小到大将各子序列依次首尾相接“收集”在一起，如此重复m趟，最终完成整个记录序列的排序。按这种方法实现的排序称为基数排序基数排序。u假设关键字k是十进制数，即r=10，且其值都在0到999的范围内，则可把k中的每一位数字看成一个关键字，即认为k由三个关键字（k0, k1, k2）组成，其中k0是个位数，k1是十位数，k2是百位数。u若关键字k是字符串，则可把字符串中的每一个字母看成一个关键字，即r = 26。基数排序的实现方法基数排序的实现方法u链式基数排序链式基数排序在链式存储结构中实现。在每一趟排序中，分配是按相应关键字的取值将记录加入到r个不同的队列；收集是从小到大依次将r个队列首尾相接成一个链表。u计数基数排序计数基数排序在顺序存储结构中实现。在每一趟排序中，分配是对相应关键字的每种取值计数（即统计r个子序列的长度），确定每个子序列的起始位置；收集是根据各子序列的起始位置将记录复制到合适位置。计数基数排序计数基数排序u数据类型定义typedef struct KeysType *keys; / 关键字 / 其它数据项 KeysRcdType; / 基数排序中的记录类型typedef struct KeysRcdType *rcd; / 0号位置空闲int length; / 顺序表长度int size; / 顺序表容量int digitNum; / 关键字位数int radix; / 关键字基数 KeysSqList; / 顺序表类型计数基数排序的实现计数基数排序的实现u引入三个数组n数组count用于统计关键字的r种取值的个数。counti是对值i的计数；n数组pos用于确定各子序列的起始位置。posi是值为i的子序列的起始位置。n数组rcd1与rcd类型相同。在各趟收集中，第一趟从数组rcd收集到rcd1，第二趟从rcd1收集到rcd，如此交替进行，若总趟数为奇数，最后还需将排序结果从数组rcd1复制回rcd。举例举例u对关键字为（337, 332, 132, 267, 262, 164, 260, 167）的8个记录序列需进行三趟“分配”和“收集”完成低位优先的计数基数排序。u第一趟对个位数排序，首先用数组count对个位数的每种取值计数，共有1个0、3个2、1个4和3个7，其余均为0个。u利用count数组统计第i个关键字各种取值的个数：for(j=0; jL.radix; +j) countj = 0; / 初始化for(k=1; k=n; k+) countrcdk.keysi+; / 对各种取值计数70000 12122723410173 2举例举例u利用count数组的结果，依次计算个位数从0到9的关键字存储的起始位置，存入数组pos。 pos0 = 1;for(j=1; jL.radix; +j) posj = posj-1+countj-1;1225566699count0count1count2count9pos0=1pos2= pos1+count1pos9= pos8+count8=pos0+count0pos1举例举例u第一趟收集u由337的个位数7取得其起始位置pos7的值6，将337放入rcd16中，并将pos7加1，令pos7指向下一个个位数为7的记录应放入的位置。u由332的个位数2取得其起始位置pos2的值2，将332放入rcd12中，并将pos2加1。u收集的代码for(k=1; k=n; +k) / 收集 j = rcdk.keysi; rcd1posj+ = rcdk; / 复制记录,对应的起始位置加1 256 7 8 93 4 561 22566993 3 7 3 3 21 6 72 6 01 6 42 6 22 6 71 3 2rcdposrcd13 3 7 3 3 2 1 3 2 2 6 7 2 6 2 1 6 4 2 6 0 1 6 7第二趟分配与收集第二趟分配与收集u第二趟对数组rcd1进行分配u第二趟收集，将记录从数组rcd1收集到rcd41666663330035rcd12 6 01 3 225 83 3 22 6 2 1 6 463 3 73472 6 791 6 711144999countposrcd第三趟分配与收集第三趟分配与收集u第三趟对数组rcd进行分配u第三趟收集，将记录从数组rcd收集到rcd1u由于趟数为奇数，需将数组rcd1复制回rcd。90011132223332 011479999993 3 2 1 6 7 8rcd1 3 2 23 3 7 42 6 0 52 6 2 61 6 4 32 6 7 7countposrcd1一趟计数基数排序一趟计数基数排序void RadixPass(KeysRcdType rcd, KeysRcdType rcd1, int n, int i, int count, int pos, int radix) int k, j; for(k=1; k=n; k+) countrcdk.keysi+; / 对各种取值计数pos0 = 1; for(j=1; jradix; +j) posj = countj-1+posj-1; / 求起始位置for(k=1; k=n; +k) / 收集 j = rcdk.keysi; rcd1posj+ = rcdk; / 复制记录，对应的起始位置加1计数基数排序的算法计数基数排序的算法Status RadixSort(KeysSqList &L) / 对顺序表 L 进行计数基数排序 KeysRcdType *rcd1; / 开设同等大小的辅助空间用于复制数据 int i = 0, j,*count, *pos; count = (int*)malloc(L.radix*sizeof(int); pos = (int*)malloc(L.radix*sizeof(int); rcd1 = (KeysRcdType*)malloc(L.length+1)*sizeof(KeysRcdType); if(NULL=count | NULL=pos | NULL= rcd1) return OVERFLOW; while(iL.digitNum) for(j=0; jL.radix; +j) countj = 0; / 初始化 if(0=i%2) / 对L.rcd进行一趟基数排序，结果存入rcd1 RadixPass(L.rcd, rcd1, L.length, i+, count, pos, L.radix); else / 对rcd1进行一趟基数排序，结果存入 L.rcd RadixPass(rcd1, L.rcd, L.length, i+, count, pos, L.radix); if(1=L.digitNum%2) / 排序后的结果在rcd1中，复制至L.rcd 中 for(j=1; j=L.length; +j) L.rcdj = rcd1j; free(count); free(pos); free(rcd1); return OK; 计数基数排序的性能分析计数基数排序的性能分析u计数基数排序算法无需比较关键字，主要操作是分配和收集。u对于n个记录，每个记录包含m个关键字，基数为r，分配过程统计r个值对应的记录数，收集过程根据统计的结果将记录复制到合适位置。u因此一趟分配与收集的时间复杂度为O(n)。u记录由m个关键字构成，则需要进行m趟分配与收集，因此时间复杂度为O(mn)。u计数基数排序算法是一种稳定的排序算法。u通常m远小于n，时间复杂度可视为O(n)。u由于采用了长度为n的辅助数组rcd1，算法的空间复杂度为O(n)。