数据结构 Data Structure CSU 主讲人：王国军，郑瑾 中南大学信息院计科系 {csgjwang,zhengjin}@csu.edu.cn http://trust.csu.edu.cn/ 电话：0731-88877711 手机：13508486821 办公室：校本部计算机楼406-B 本PPT根据《数据结构》教材（清华大学）制作，仅供中南大学计算机科学与技术专业及相关专业11级本科生和任课老师使用。

提 纲 10.1 概述 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较讨论

10.1 概述 排序定义——将一组数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列（升序或降序）。 排序是计算机程序设计中的一种重要运算，是计算机处理数据时一种频繁要做的工作。 关键字将随着用户的要求不同而不同。如：人事档案文件可按年龄、工资或文化水平进行排序，从而获得不同的有序文件。

排序分类 按排序后得到的结果 稳定的排序方法：结果唯一 不稳定的排序方法：结果不唯一

排序的稳定性 若序列中关键字值相等的节点经过某种 排序方法进行排序之后，仍能保持它们 在排序前的相对顺序，则称这种排序方 法是稳定的；否则，称这种排序方法是 不稳定的。 稳定性例 待排序列： 34 12   34’ 08   96 稳定： 08   12   34 34’ 96 不稳定： 08   12   34’ 34  96  3

排序分类 按待排序记录所在位置 内部排序：待排序记录存放在内存中进行的排序 外部排序：待排序记录的数量很大，以至于内存中一次不能容纳全部记录，在排序过程中需对外存进行访问的排序

按排序依据原则 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 基数排序

先进的排序方法：T(n)=O(nlogn) 基数排序：T(n)=O(d·n) 按排序所需工作量 简单的排序方法：T(n)=O(n²) 先进的排序方法：T(n)=O(nlogn) 基数排序：T(n)=O(d·n) n为记录的个数，d为关键字的位数

排序的两个基本操作 (1)比较两个关键字的大小 (2)将记录从一个位置移动到另一个位置 评价一个排序方法好坏的标准 排序所需比较关键字的次数 排序所需移动记录的次数 排序过程中所需的辅助空间的大小 ——少 ——少 ——小

10.2 插入排序 插入排序的准则：在有序序列中插入新的记录以达到扩大有序区的长度的目的。 直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。

插入排序 (insertion sort) 7

插入排序过程 D A A D T D C A T S R D S T R T S R R T S U T C U T T U U R U E 9

例1 i=1 ( ) 49 38 65 97 76 13 27 i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27 i=5 76 (38 49 65 76 97) 13 27 i=6 13 (13 38 49 65 76 97) 27 i=7 (13 38 49 65 76 97) 27 27 27 38 49 65 76 97 j j j j j j 监视哨 L.r[0] (13 27 38 49 65 76 97) 排序结果：

算法描述 void InsertSort ( SqList &L) {// 对顺序表L作直接插入排序 for ( i=2; i<=L.length; ++i ) 　if ( L.r[i].key < L.r[i-1].key ) { // 将 L.r[i] 插入有序子表 　　L.r[0] = L.r[i]; L.r[i]=L.r[i-1]; 　　for ( j=i-2; L.r[0].key < L.r[j].key; --j ) 　　　L.r[j+1] = L.r[j]; // 记录后移 　　L.r[j+1] = L.r[0]; // 插入到正确位置 　} // if } // InsertSort

算法评价 时间复杂度 T(n)=O(n²) 若待排序记录按关键字从小到大排列(正序) 关键字比较次数： 记录移动次数： 0 记录移动次数： 0 若待排序记录按关键字从大到小排列(逆序) 关键字比较次数： 记录移动次数：

若待排序记录是随机的，取上述最大最小的平均值 关键字比较次数：≈ 记录移动次数：≈ 空间复杂度： S(n)=O(1)

希尔排序(缩小增量法) 排序过程：先取一个正整数d1<n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。

例3 初始： 49 38 65 97 76 13 27 48 55 4 取d1=5 一趟分组： 49 38 65 97 76 13 27 48 55 4 一趟排序： 13 27 48 55 4 49 38 65 97 76 取d2=3 二趟分组： 13 27 48 55 4 49 38 65 97 76 二趟排序： 13 4 48 38 27 49 55 65 97 76 取d3=1 三趟分组： 13 4 48 38 27 49 55 65 97 76 三趟排序： 4 13 27 38 48 49 55 65 76 97

算法描述 void ShellInsert ( SqList &L，int dk) 　{　// 对顺序表L作一趟增量为dk的希尔排序 　for ( i=dk+1; i<=L.length; ++i ) if ( L.r[i].key < L.r[i-dk].key ) { // 将L.r[i]插入有序子表 　L.r[0] = L.r[i]; L.r[i]=L.r[i-dk]; 　for ( j=i-2*dk; j>0 && L.r[0].key < L.r[j].key; j-=dk ) 　　　　　L.r[j+dk] = L.r[j]; 　　// 记录后移 　L.r[j+dk] = L.r[0]; 　　// 插入到正确位置 　　　} // if 　} // ShellInsert 由于没有"负数"的下标，在dk>1时需对j循环中以防"出界"另作"j>0"的判别，即L.r[0] 不再起到"监视哨"的作用，而仅仅作为一个暂存记录的空间。

void ShellSort (SqList &L, int dlta[], int t) { // 按增量序列 dlta[0 void ShellSort (SqList &L, int dlta[], int t) 　{ 　　// 按增量序列 dlta[0..t-1] 对顺序表L作希尔排序 　　for (k=0; k<t; ++t) 　　　ShellInsert(L, dlta[k]); // 一趟增量为 dlta[k] 的插入排序 　} // ShellSort

希尔排序特点 子序列的构成不是简单地“逐段分割”，而是将相隔某个增量的记录组成一个子序列。 希尔排序可提高排序速度。因为分组后n值减小，而n值小时效率高(T(n)=O(n²) ) ，所以T(n)从总体上看是关键字较小的记录跳跃式前移（不是一步一步往前挪动），在进行最后一趟增量为1的插入排序时，序列已“基本有序”。

希尔排序的时间复杂度和所取增量序列相关，例如已有学者证明，当增量序列为 2t-k-1 (k= 0, 1, …，t-1)时，希尔排序的时间复杂度为O (n3/2)。 增量序列取法 无除1以外的公因子 采用缩小增量法 最后一个增量值必须为1

11.3 交换排序 基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。 两种交换排序: 11.3 交换排序 基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。 两种交换排序: 冒泡排序 快速排序

冒泡排序 最简单的一种交换排序方法 排序过程（从左到右） 将第一个记录的关键字与第二个记录的关键字进行比较，若逆序则交换；然后比较第二个记录与第三个记录；依此类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。

冒泡排序 算法步骤： 待排序记录S={r1,r2…,rn},假设待排序记录长为n 第一趟：比较记录r1与r2的关键字，若r1.key>r2.key，则将两个记录交换，紧接着依次比较r2和r3，直至rn-1与rn为止。这样一趟将关键字值最大的记录移至rn位置， 第二趟：比较r1至让rn-1，关键字值次大的记录移动到第n-1位置，方法同第一趟 依次完成第3趟，第4趟，…n-1趟，直到所有记录都完成排序

9.3.1 冒泡排序 举例 75 87 68 92 88 61 77 96 80 72 75 87 68 92 88 61 77 96 80 72 68 87 87 88 92 61 92 77 92 92 96 80 96 72 96 61 68 72 75 77 80 87 88 92 96 61 68 72 75 77 80 87 88 92 96 61 68 72 75 77 80 87 88 92 96 61 68 72 75 77 80 87 88 92 96 68 61 75 77 80 72 87 88 92 96 68 75 87 61 77 88 80 72 92 96 68 75 61 77 87 80 72 88 92 96 61 68 75 77 72 80 87 88 92 96 61 68 75 72 77 80 87 88 92 96

算法描述 void BubbleSort(SqList &L) 　{ // 对顺序表L作冒泡排序 　　for (i=L.length, change=TRUE; i>1 && change; --i) { change = FALSE; 　　　 for (j=1; j<i; ++j) 　　　　if (L.r[j].key > L.r[j+1].key) 　　　　　{ L.r[j]←→L.r[j+1]; change = TRUE; } 　　}// for i 　} // BubbleSort

算法评价 时间复杂度： T(n)=O(n²) 最好情况（正序） 比较次数：n-1 移动次数：0 最坏情况（逆序） 比较次数： 空间复杂度： S(n)=O(1)

快速排序 算法思想： 将一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字比另一部分记录的关键字小，然后分别对这两部分记录继续使用该方法排序，以达到整个序列有序。 13 43 31 57 26 65 81 92 75 13 81 92 43 65 31 57 26 75 0 0 13 26 31 43 57 65 75 81 92 0 13 26 31 43 57 65 75 81 92

int Partition ( RcdType R[], int low, int high) –实现2 　{// 对记录子序列 R[low..high] 进行一趟快速排序，并返回枢轴记录 　　// 所在位置，使得在它之前的记录的关键字均不大于它的关键字， 　　// 而在它之后的记录的关键字均不小于它的关键字 　　R[0] = R[low];　　// 将枢轴记录移至数组的闲置分量 　　pivotkey = R[low].key; 　// 枢轴记录关键字 　　while (low<high) {　// 从表的两端交替地向中间扫描 　　　while (low<high && R[high].key>=pivotkey) 　　　　--high; 　　　R[low++] = R[high];　// 将比枢轴记录小的记录移到低端 　　　while (low<high && R[low].key<=pivotkey) 　　　　++low; 　　　R[high--] = R[low];　// 将比枢轴记录大的记录移到高端 　　} // while 　　R[low] = R[0];　　　// 枢轴记录移到正确位置 　　return low; 　　　// 返回枢轴位置 　} // Partition

void partion(int r[], int s, int t) { int i=s, j=t, x=r[s]; //用辅助变量x存储参考元 while(i<j){ while (i<j && r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;} while (i<j && r[i]<x) i=i+1; if (i<j) {r[j]=r[i];j=j-1;} } r[i]=x; Return i ;

> < < < > > > < >= 快速排序 举例： > < < < > > > < >= 49 49 27 14 38 8 74 49 96 65 96 8 49 55 27 74 1 2 3 4 5 6 7 8 9 10 low low low low low high high high high high high 27 14 38 8 49 65 96 55 74

快速排序的过程 21 25 49 25* 16 08 prikey 初始关键字 j i 21 08 25 49 25* 16 一次交换 i 二次交换 08 49 25* 16 25 i j 25 三次交换 08 16 49 25* j i 四次交换 08 16 25* 49 25 i j 完成一趟排序 08 16 21 25* 49 25 i j

08 16 21 25* 49 25 完成一趟排序 分别进行快速排序 08 16 21 25 25* 49 有序序列 08 16 21 25 25* 49

算法描述 void QSort (RcdType R[], int s, int t ) 　{ // 对记录序列 R[s..t] 进行快速排序 　　if (s < t) { 　　　　　　　// 长度大于1 　　　pivotloc = Partition(R, s, t); 　　　　 // 对 R[s..t] 进行一趟快排，并返回枢轴位置 　　　QSort(R, s, pivotloc-1); // 对低子序列递归进行排序 　　　QSort(R, pivotloc+1, t); // 对高子序列递归进行排序 　　} // if 　} // QSort

void QuickSort( SqList &L) { // 对顺序表 L 进行快速排序 QSort(L. r, 1, L void QuickSort( SqList &L) 　{ 　　// 对顺序表 L 进行快速排序 　　QSort(L.r, 1, L.length); 　} // QuickSort

算法评价 时间复杂度： T(n)=O(n²) 最好情况（每次总是选到中间值作枢轴） T(n)=O(nlog2n) 为避免出现枢轴记录关键字为"最大"或"最小"的情况，通常进行的快速排序采用"三者取中"的改进方案，即以 R[s]、R[t] 和 R[(s+t)/2] 三者中关键字介于中值者为枢轴。只要将它和 R[s] 互换，一次划分的算法仍不变。

可以证明，快速排序的平均时间复杂度为O (nlogn)，并且在所有平均时间复杂度为O (nlogn)的算法中它是最快的。在三者取中的前提下，对随机的关键字序列，快速排序是目前被认为是最好的排序方法。如果借用冒泡排序中设置记录“交换与否”的布尔变量的作法，快速排序也适用于已经有序的记录序列。

空间复杂度：需栈空间以实现递归 最坏情况： 一般情况： S(n)=O(n) S(n)=O(log2n)

11.4 选择排序 基本思想：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。 11.4 选择排序 基本思想：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。 两种交换排序: 直接选择排序(或称简单选择排序) 堆排序

简单选择排序 排序过程 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换；

算法描述 void SelectSort (SqList &L) 　{// 对顺序表L作简单选择排序 　　for (i=1; i<L.length; ++i) { // 选择第 i 小的记录，并交换到位 　　　k= i; 　　　for ( j=i+1; j<=L.length; j++ ) 　　 if ( L.r[j].key < L.r[k].key ) k=j; // 在L.r[i..L.length]中选择关键字最小的记录 　　　if ( i!=k ) L.r[k] ←→L.r[i]; // 与第 i 个记录互换 　　}// for 　} // SelectSort

选择排序是否也和插入排序或冒泡排序相类似，在对"正序"和"逆序"的待排序列进行排序时，所需进行的"比较"和"移动"次数有很大差别？ 无论待排序列处于什么状态，选择排序所需进行的“比较”次数都相同，为 而"移动"次数在待排序列为"正序"时达最小为0，在"逆序"时达最大为3(n-1)。

例1： k k k i=1 初始： [ 49 38 65 97 76 13 27 ] 13 49 j j j j j j k k i=2 初始： [ 49 38 65 97 76 13 27 ] 13 49 j j j j j j k k i=2 一趟： 13 [38 65 97 76 49 27 ] 27 38 j j j j j 二趟： 13 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

算法评价 记录移动次数： 最好情况：0 最坏情况：3(n-1) 比较次数： 总时间复杂度： 时间复杂度： T(n)=O(n²) 空间复杂度： S(n)=O(1)

堆排序 堆的定义：n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆。 kik2i kik2i 或 (i=1,2,…...n/2) kik2i kik2i+1 kik2i kik2i+1 即堆是一个具有这样性质的完全二叉树：每个非终端结点（记录）的关键字大于等于（或小于等于）其孩子结点的关键字。 96 27 9 11 38 83 1 2 3 4 5 6 例2： （96，83，27，38，11，9）

1 例2： （96，83，27，38，11，9） 2 3 4 6 5 例3：（13，38，27，50，76，65，49，97） 大顶堆 96 堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值 堆中任何一个结点的非空左右子树都是一个堆 13 27 38 49 65 76 50 97 例3：（13，38，27，50，76，65，49，97） 小顶堆

堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（或最大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序。

堆排序需解决的两个问题： 如何由一个无序序列建成一个堆？ 第二个问题解决方法——筛选 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 第二个问题解决方法——筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。

例4： 97 27 38 49 65 76 50 13 输出：13 27 49 38 97 65 76 50 13 输出：13 13 27 38 49 65 76 50 97 97 49 38 27 65 76 50 13 输出：13 27 38 49 50 27 65 76 97 13 输出：13 27 65 49 50 27 38 76 97 13 输出：13 27 38

49 65 50 27 38 76 97 13 输出：13 27 38 76 65 50 27 38 49 97 13 输出：13 27 38 49 50 65 76 27 38 49 97 13 输出：13 27 38 49 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 97 76 27 38 49 50 13 输出：13 27 38 49 50 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65

76 65 97 27 38 49 50 13 输出：13 27 38 49 50 65 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 76 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 76 97

算法描述 void HeapAdjust (SqList &H, int s, int m) 　{ // 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义， 　　// 本函数依据关键字的大小对H.r[s]进行调整，使H.r[s..m]成为一 　　// 个大顶堆（对其中记录的关键字而言） 　　H.r[0] = H.r[s];　　　　　　　　// 暂存根结点的记录 　　for ( j=2*s; j<=m; j*=2 ) { // 沿关键字较大的孩子结点向下筛选 　　　if ( j<m && H.r[j].key<H.r[j+1].key ) 　　　　++j; 　　　　　　　// j 为关键字较大的孩子记录的下标 　　　if ( H.r[0].key >= H.r[j].key ) break; // 不需要调整，跳出循环 　　　H.r[s] = H.r[j]; s = j; 　　　// 将大关键字记录往上调 　　}// for 　　H.r[s] = H.r[0]; 　　　　　　　// 回移筛选下来的记录 　} // HeapAdjust

第一个问题解决方法 对待排序的记录，建成相应的完全二叉树 从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选

例5 含8个元素的无序序列（49，38，65，97，76，13，27，50） 49 65 38 27 13 76 50 97 49 13 38 27 65 76 50 97 49 65 38 27 13 76 97 50 49 13 38 27 65 76 50 97 13 27 38 49 65 76 50 97

算法描述 void HeapSort ( SqList &H ) 　{ // 对顺序表H进行堆排序 　　for ( i=H.length/2; i>0; --i ) // 将 H.r[1..H.length] 建成大顶堆 　　　HeapAdjust ( H, i, H.length ); 　　H.r[1] ←→ H.r[H.length]; 　　// 互换"堆顶"和"堆底"的记录 　　for ( i=H.length-1; i>1; --i ) { 　　　HeapAdjust(H, 1, i); // 从根开始调整，将 H.r[1..i] 重新调整为大顶堆 　　　H.r[1] ←→ H.r[i]; 　　// 互换"堆顶"和当前的"堆底"，使已有序的记录沉积在底部 　　}//for 　} // HeapSort

算法评价 时间复杂度： 最坏情况下： T(n)=O(nlogn) 空间复杂度： S(n)=O(1)

10.5 归并排序（分治法） 归并排序思路： 归并的含义是将两个或两个以上的有序表合并成一个有序表。利用归并的思想就可以实现排序。假设初始的序列含有n个记录，可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复直到得到一个长度为n的有序序列为止。这种排序方法称为二路归并排序。 1 3 5 7 9 2 4 6 8

Mergesort 的提出

Example : Whole Process A L G O R I T H M S Divide A L G O R | J T H M S Divide A L | G O R | J T | H M S Divide A | L | G | O R | J | T | H | M S Divide A | L | G | O | R | J | T | H | M | S Merge A | L | G | O R | J | T | H | M S Merge A L | G O R | J T | H M S Merge A G L O R | H J M S T Merge A G H J L M O R S T Key: Linear-time Merge subroutine

Mergesort 8 3 4 1 6 5 2 7 T(n/2) O(1) O(n) 8 3 4 1 6 5 2 7 T(1) = O(1) 8 3 4 1 6 5 2 7 T(n/2) O(1) O(n) 8 3 4 1 6 5 2 7 T(1) = O(1) T(n) = O(1)+2T(n/2)+O(n) T(n) = O(n log n) 8 3 4 1 8 3 4 1 3 8 1 4 6 5 6 5 2 7 2 7 5 6 1 3 4 8 2 5 6 7 1 2 3 4 5 6 7 8

归并排序 举例 75 87 68 92 88 61 77 96 80 72 75 87 68 92 61 88 77 96 72 80 归 并 过 程 68 75 87 92 61 77 88 96 72 80 61 68 75 77 87 88 92 96 72 80 61 68 72 75 77 80 87 88 92 96

归并过程

Merging two sorted arrays

Merging two sorted arrays

Merging two sorted arrays

Merging two sorted arrays

Merging two sorted arrays

Merging two sorted arrays

Merging two sorted arrays

Merging two sorted arrays

Merging two sorted arrays

算法描述 void Merge (RcdType SR[], RcdType TR[], int i, int m, int n) 　{ // 将有序的SR[ i..m ]和SR[ m+1..n ]归并为有序的TR[ i..n ] 　　for (j=m+1, k=i; i<=m && j<=n; ++k) 　　{ // 将SR中记录按关键字从小到大地复制到TR中 //k用来指示新表TR的当前元素下标 　　　if (SR[i].key<=SR[j].key) TR[k] = SR[i++]; 　　　else TR[k] = SR[j++]; 　　} 　　while (i<=m) TR[k++] = SR[i++]; // 将剩余的 SR[i..m] 复制到TR 　　while (j<=n) TR[k++] = SR[j++]; // 将剩余的 SR[j..n] 复制到TR 　} // Merge

void MSort ( RcdType SR[], RcdType TR1[], int s, int t ) { // 对SR[s void MSort ( RcdType SR[], RcdType TR1[], int s, int t ) 　{ // 对SR[s..t]进行归并排序，排序后的记录存入TR1[s..t] 　　if (s==t) TR1[s] = SR[s]; 　　else { 　　　m = (s+t)/2; // 将 SR[s..t] 平分为 SR[s..m] 和 SR[m+1..t] 　　　MSort (SR,TR2,s,m);　　 // 递归地将 SR[s..m] 归并为有序的 TR2[s..m] 　　　MSort (SR,TR2,m+1, t); // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] 　　　Merge (TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t] 归并到 TR1[s..t] 　　} // else 　} // MSort

算法评价 时间复杂度：T(n)=O(nlog2n) 空间复杂度：S(n)=O(n) MergeSort (A, left, right) { if (left < right) mid = INT ((left + right)/2); MergeSort(A, left, mid); MergeSort(A, mid+1, right); Merge(A, left, mid, right); } 算法评价 时间复杂度：T(n)=O(nlog2n) 空间复杂度：S(n)=O(n)

10.6 基数排序 前面讨论的排序主要是通过关键字之间的比较和移动记录来实现的，而基数排序不需要进行关键字之间的比较，它是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。

基数排序是一种借助“多关键字排序”的思想来实现“单关键 字排序”的内部排序算法。 第一关键字 K1 第二关键字 K2 基数排序是一种借助“多关键字排序”的思想来实现“单关键 字排序”的内部排序算法。 学号 数学 英语 其它 101 B C … 102 A 103 D 104 105 106 107 E 108 例：将右表所示的学生 成绩单按数学成绩 的等级由高到低排 序，数学成绩相同 的学生再按英语成 绩的高低等级排序。 特点：每个记录最终的 位置由两个关键 字 k1 k2 决定。 105 A A 102 A B 104 B B 101 B C 108 C B 103 C D 106 D B 107 E A 我们将它称之为复 合关键字，即多关键字 排序是按照复合关键字 的大小排序。

例：扑克牌中 52 张牌，可按花色和面值分成两个“关键字”，其 大小关系为：花色：  < < <  面值： 2<3<4<5<6<7<8<9<10<J<Q<K<A 若对扑克牌按花色、面值进行升序排序，得到如下序列： 2, 3, ..., A, 2, 3, ..., A, 2, 3, ..., A, 2, 3, ..., A 即两张牌，若花色不同，不论面值怎样，花色低的那张牌小 于花色高的，只有在同花色情况下，大小关系才由面值的大小确 定。这也是按照复合关键字的大小排序，即：多关键字排序。

链式基数排序 　　在计算机上实现基数排序时，为减少所需辅助存储空间， 应采用链表作存储结构，即链式基数排序，具体作法为： 1、以静态链表存储待排记录，并令表头指针指向第一个记录； 2、“分配” 时，按当前“关键字位”所取值，将记录分配到不同 的 “链队列” 中，每个队列中记录的 “关键字位” 相同； 3、“收集”时，按当前关键字位取值从小到大将各队列首尾相 链成一个链表； 4、对每个关键字位均重复 2 和 3 两步。

930 063 083 184 505 278 008 109 589 269 一趟收集： e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 二趟分配 109 930 269 589 278 008 184 505 063 083 505 008 109 930 063 269 278 083 184 589 二趟收集：

例2 初始状态： 278 109 063 930 589 184 505 269 008 083 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 一趟分配 930 083 184 505 008 269 589 063 278 109 930 063 083 184 505 278 008 109 589 269 一趟收集：

930 063 083 184 505 278 008 109 589 269 一趟收集： e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 二趟分配 109 930 269 589 278 008 184 505 063 083 505 008 109 930 063 269 278 083 184 589 二趟收集：

505 008 109 930 063 269 278 083 184 589 二趟收集： e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 三趟分配 083 184 278 589 930 063 008 109 269 505 008 063 083 109 184 269 278 505 589 930 三趟收集：

算法评价 时间复杂度： 分配：T(n)=O(n) 收集：T(n)=O(rd) 总时间复杂度： T(n)=O(d(n+rd)) 空间复杂度：S(n)=2rd个队列指针+n个指针域空间 基数

10.7 各种内部排序方法的比较讨论 直接插入排序、直接选择排序和冒泡排序是三种简单的排序方法，它们的时间复杂度均为O（n2），空间复杂度均为O（1）；但是，由于它们的时间复杂度的系数不同，所以直接插入排序快于直接选择排序，而直接选择排序又快于冒泡排序。 堆排序、快速排序和归并排序是三种较快的排序方法，它们的平均时间复杂度均为O（nlogn），但平均速度最快的是快速排序；它们的空间复杂度分别为 O（1）、O（logn）和O（n）。

本章讨论的排序算法多数是在顺序存储结构上实现的，因此在排序过程中需进行大量的记录移动。当n很大时，很耗费时间，此时宜采用静态链表作存储结构。如表插入排序、链式基数排序，以修改指针代替移动记录。 快速排序和堆排序无法实现链式排序。

若Ki=Kj，排序前i<j，排序后仍保持i<j，此排序方法属稳定排序。 一般来说，排序过程中的“比较”是在“相邻两个记录关键字”间进行的排序方法是稳定的。 基数排序，以及时间复杂度为O（n2）的简单排序方法是稳定的。 快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。