第9章 内部排序 概述 插入排序 （直接插入、折半插入、表插入排序、希尔排序） 交换排序 （起泡排序、快速排序） 第9章 内部排序 概述 插入排序 （直接插入、折半插入、表插入排序、希尔排序） 交换排序 （起泡排序、快速排序） 选择排序 （简单选择排序、树形选择排序、堆排序） 归并排序 基数排序 小结

概述 排序：将一组杂乱无章的数据排列成一个按关键字有序的序列。 数据表(datalist): 它是待排序数据对象的有限集合。 关键字(key): 通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键字。每个数据表用哪个属性域作为关键字，要视具体的应用需要而定。即使是同一个表，在解决不同问题的场合也可能取不同的域做关键字。

主关键字: 如果在数据表中各个对象的关键字互 不相同，这种关键字即主关键字。按照主关键字 进行排序，排序的结果是唯一的。 次关键字: 数据表中有些对象的关键字可能相 同，这种关键字称为次关键字。按照次关键字 进行排序，排序的结果可能不唯一。 排序算法的稳定性: 如果在对象序列中有两个对 象r[i]和r[j]，它们的关键字 k[i] == k[j]，且在 排序之前，对象r[i]排在r[j]前面。如果在排序 之后，对象r[i]仍在对象r[j]的前面，则称这个 排序方法是稳定的，否则称这个排序方法是不 稳定的。

内排序与外排序: 内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。 排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。各节给出算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象关键字序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。

静态排序: 排序的过程是对数据对象本身进行物理地重排，经过比较和判断，将对象移到合适的位置。这时，数据对象一般都存放在一个顺序的表中。 动态排序: 给每个对象增加一个链接指针，在排序的过程中不移动对象或传送数据，仅通过修改链接指针来改变对象之间的逻辑顺序，从而达到排序的目的。 算法执行时所需的附加存储: 评价算法好坏的另一标准。

衡量排序方法的标准 排序时所需要的平均比较次数 排序时所需要的平均移动 排序时所需要的平均辅助存储空间

待排记录的数据类型定义为： #define MAXSIZE 20 Typedef int KeyType Typedef struct {KeyType key; //关键字项 InfoType otherinfo; //其它数据项 }RedType; Typedef struct {RedType r[MAXSIZE+1] //r[0]闲置或用作哨兵 int length; }Sqlist;

插入排序 (Insert Sorting) 直接插入排序 (Insert Sort) 插入排序的基本方法是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。 直接插入排序 (Insert Sort) 直接插入排序的基本思想是：当插入第i (i  1) 个对象时，前面的V[0], V[1], …, v[i-1]已经排好序。这时，用v[i]的关键字与v[i-1], v[i-2], …的关键字顺序进行比较，找到插入位置即将v[i]插入，原来位置上之后的所有对象依次向后顺移。

各趟排序结果 49 25 25* 21 16 08 0 1 2 3 4 5 49 25 25* 25 21 16 i = 1 08 0 1 2 3 4 5 temp 49 49 25 25* 21 16 i = 2 08 0 1 2 3 4 5 temp

49 25 25* 25* 21 16 i = 3 08 0 1 2 3 4 5 49 25 25* 21 16 16 i = 4 08 0 1 2 3 4 5 temp 49 25 25* 21 16 i = 5 08 08 0 1 2 3 4 5 temp

49 25 25* 21 16 完成 08 0 1 2 3 4 5 i = 4 时的排序过程 49 i = 4 j = 3 16 25 25* 21 16 16 08 0 1 2 3 4 5 temp 49 49 i = 4 j = 2 16 25 25* 21 16 08 0 1 2 3 4 5 temp

i = 4 j = 1 49 16 25 25* 25* 21 16 08 0 1 2 3 4 5 i = 4 j = 0 49 16 25 25 25* 21 16 08 0 1 2 3 4 5 temp i = 4 j = -1 49 16 25 25* 21 21 16 08 0 1 2 3 4 5 temp

直接插入排序的算法 void InsertSort(SqList &L) { for (int i=2;i<=L.length;++i) if (LT(L.r[i].key,L.r[i-1].key)) { L.r[0]=L.r[i]; // L.r[0]为监视哨 for (int j=i-1; LT(L.r[0].key,L.r[j].key); --j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; }

算法分析 若设待排序的对象个数为L.length= n，则该算法的主程序执行n-1趟。 关键字比较次数和对象移动次数与对象关键字的初始排列有关。 最好情况下，排序前对象已经按关键字大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键字比较 1 次，移动 2 次对象，总的关键字比较次数为 n-1，对象移动次数为 2(n-1)。 直接插入排序是一种稳定的排序方法。 直接插入排序算法的时间复杂度为O(n2)

折半插入排序 (Binary Insertsort) 折半插入排序基本思想是：设在顺序表中有一 个对象序列 V[0], V[1], …, v[n-1]。其中，v[0], V[1], …, v[i-1] 是已经排好序的对象。在插入 v[i] 时，利用折半搜索法寻找 v[i] 的插入位置。

折半插入排序的算法 void BInsertSort(SqList &L) { int low,high,mid; for (int i=2;i<=L.length;++i) { L.r[0]=L.r[i]; low = 1; high=i-1; while (low <= high) { mid = (low+high)/2; if (LT(L.r[0].key,L.r[mid].key)) high=mid-1; else low=mid+1; } for (int j=i-1; j>=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; } 说明：low 或者 high+1为插入点 稳定排序

算法分析 对分查找比顺序查找快，所以对分插入排序就平均性能来说比直接插入排序要快。 它所需要的关键字比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。 当 n 较大时，总关键字比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。 对分插入排序是一个稳定的排序方法。

希尔排序 (Shell Sort) 希尔排序方法又称为“缩小增量”排序。 该方法的基本思想是：先将整个待排对象序列按照一定间隔分割成为若干子序列，分别进行直接插入排序，然后缩小间隔，对整个对象序列重复以上的划分子序列和分别排序工作，直到最后间隔为1，此时整个对象序列已 “基本有序”，进行最后一次直接插入排序。

49 25 25* 21 16 08 0 1 2 3 4 5 i = 1 49 gap = 3 25 25* 21 16 08 49 25 25* 21 16 08 49 25 25* 21 16 08

49 25* 25 21 16 08 0 1 2 3 4 5 i = 2 49 gap = 2 25* 25 21 16 08 49 25* 25 21 16 08 49 25* 25 21 16 08

49 25* 25 21 16 08 0 1 2 3 4 5 i = 3 49 gap = 1 25* 25 21 16 08 开始时 gap（间隔值） 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，gap 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。

希尔排序的算法 void ShellSort(SqList &L, int dlta[],int t){ for (int k=0;k<t;++k){ ShellInsert(L,dlta[k]); } 说明：dlta[3]={5，3，1}

//一趟希尔排序,按间隔dk划分子序列 void ShellInsert(SqList &L, int gap) { for (int i=gap+1;i<=L.length;++i) {if (LT(L.r[i].key,L.r[i-gap].key)) { L.r[0]=L.r[i]; for (int j=i-gap;j>0 && LT(L.r[0].key,L.r[j].key); j-=gap) L.r[j+gap]=L.r[j]; L.r[j+gap]=L.r[0]; }

算法分析 对特定的待排序对象序列，可以准确地估算关键字的比较次数和对象移动次数。 但想要弄清关键字比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。 gap的取法有多种。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。后来Knuth 提出取gap = gap/3 +1。还有人提出都取奇数为好，也有人提出各gap互质为好。

交换排序 ( Exchange Sort ) 起泡排序 (Bubble Sort) 交换排序的基本思想是两两比较待排序对象的关键字，如果发生逆序(即排列顺序与排序后的次序正好相反)，则交换之，直到所有对象都排好序为止。 起泡排序 (Bubble Sort) 起泡排序的基本方法是：设待排序对象序列中的对象个数为 n。最多作 n-1 趟排序。在第 i 趟中顺次两两比较r[j-1].Key和r[j].Key，j = i, i+1, , n-i-1。如果发生逆序，则交换r[j-1]和r[j]。

49 25 25* 21 16 08 0 1 2 3 4 5 49 i = 1 25 25* 21 16 08 chang=1 49 25 i = 2 21 25* 16 08 chang=1 49 i = 3 25 25* 21 16 08 chang=1

49 i = 4 25 25* 21 16 08 chang=1 0 1 2 3 4 5 49 i = 5 25 25* 21 16 08 chang=0 0 1 2 3 4 5

void BubbleSort(SqList &L) { int i, j, tag; j = L.length-1; 起泡排序的算法——1 void BubbleSort(SqList &L) { int i, j, tag; j = L.length-1; do{ tag=1; for(i=1; i<=j; i++) if( L.r[i+1].key< L.r[i].key ) { L.r[0]= L.r[i+1]; L.r[i+1]= L.r[i]; L.r[i]= L.r[0]; tag=0; } if( !tag ) j--; } while( !tag &&j ); return;

void BubbleSort(SqList &L) 起泡排序的算法——2 void BubbleSort(SqList &L) {for (int i=L.length, change=TRUE;i>1 && change; --i) { change = FALSE; for (int j=1; j<i; ++j) if (LT(L.r[j+1].key,L.r[j].key)) { ElemType temp=L.r[j]; L.r[j]=L.r[j+1]; L.r[j+1]=temp; change = TRUE; }

算法分析 在对象的初始排列已经按关键字从小到大排好序时，此算法只执行一趟起泡，做 n-1 次关键字比较，不移动对象。这是最好的情形。 最坏的情形是算法执行了n-1趟起泡，第 i 趟 (1 i n) 做了 n- i 次关键字比较，执行了n-i 次对象交换。这样在最坏情形下总的关键字比较次数KCN和对象移动次数RMN为：

起泡排序需要一个附加对象以实现对象值的对换。 起泡排序是一个稳定的排序方法。

快速排序 (Quick Sort) 快速排序方法的基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为枢轴(pivot)，按照该对象的关键字大小，将整个对象序列划分为左右两个子序列： 左侧子序列中所有对象的关键字都小于或等于枢轴对象的关键字 右侧子序列中所有对象的关键字都大于枢轴对象的关键字 枢轴对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。

然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。 算法描述 QuickSort ( List ) { if ( List的长度大于1) { 将序列List划分为两个子序列 LeftList 和 Right List; QuickSort ( LeftList ); QuickSort ( RightList ); 将两个子序列 LeftList 和 RightList 合并为一个序列List; }

i = 1 i = 2 i = 3 pivot 49 25 25* 21 16 08 0 1 2 3 4 5 pivot pivot 49 0 1 2 3 4 5 pivot pivot 49 i = 1 25* 25 21 16 08 pivot 49 i = 2 25 25* 21 16 08 49 i = 3 25 25* 21 16 08

快速排序的算法 void QSort(SqList &L, int low, int high){ if (low < high) { int pivotloc = Partition(L,low,high); QSort(L,low, pivotloc-1); QSort(L,pivotloc+1, high); } void QuickSort(SqList &L){ QSort(L,1,L.length);

int Partition(SqList &L, int low, int high) { L.r[0] = L.r[low]; int pivotkey = L.r[low].key; while (low < high) { while (low<high && L.r[high].key >= pivotkey) --high; L.r[low] = L.r[high]; while (low<high && L.r[low].key <= pivotkey) ++low; L.r[high] = L.r[low]; } L.r[low]=L.r[0]; return low;

算法quicksort是一个递归的算法，其递归树如图所示。 算法partition利用序列第一个对象作为枢轴，将整个序列划分为左右两个子序列。算法中执行了一个循环，只要是关键字小于枢轴对象关键字的对象都移到序列左侧，最后枢轴对象安放到位，函数返回其位置。 21 08 25* 25 16 49

算法分析 从快速排序算法的递归树可知，快速排序的趟数取决于递归树的深度。 如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。 可以证明，函数quicksort的平均计算时间也是o(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。

快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。 在最坏的情况，即待排序对象序列已经按其关键字从小到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过 n-1 趟才能把所有对象定位，而且第 i 趟需要经过 n-i 次关键字比较才能找到第 i 个对象的安放位置，总的关键字比较次数将达到

选择排序(Selection Sort) 简单选择排序 (Simple Selection Sort) 选择排序的基本思想是：每一趟 (例如第 i 趟，i = 1, …, n-1) 在后面的 n-i+1 个待排序对象中选出关键字最小的对象, 作为有序对象序列的第 i 个对象。待到第 n-1 趟作完，待排序对象只剩下1个，就不用再选了。 简单选择排序 (Simple Selection Sort) 基本步骤为：i从1开始，直到n-1，进行n-1趟排序，第i 趟的排序过程为： 在一组对象r[i]～r[n] (i=1,2,…,n-1)中选择具有最小关键字的对象；并和第 i 个对象进行交换；

简单选择排序的算法 void SelectSort(SqList &L) { for (int i=1; i<L.length;++i) { int k=i; for (int j=i+1;j<=L.length;++j) if (L.r[k].key > L.r[j].key) k=j; if (i!=k){ ElemType temp=L.r[i]; L.r[i]=L.r[k]; L.r[k]=temp; }

i = 1 i = 2 i = 3 初始 最小者 08 交换21,08 最小者 16 交换25,16 最小者 21 交换49,21 49 25* 21 16 08 0 1 2 3 4 5 49 最小者 08 交换21,08 i = 1 25 25* 21 16 08 49 最小者 16 交换25,16 i = 2 25 25* 21 16 08 49 最小者 21 交换49,21 25* 25 i = 3 21 16 08

i = 4 i = 5 最小者 25* 无交换 最小者 25 无交换 结果 各趟排序后的结果 49 25* 25 21 16 08 0 1 2 3 4 5 49 最小者 25 无交换 i = 5 25* 25 21 16 08 49 结果 25* 25 21 16 08 各趟排序后的结果

i =2时选择排序的过程 49 25 25* 21 16 08 0 1 2 3 4 5 49  25 i k j 49 25 25* 21 16 08 25*  25 i k j 49 25 25* 21 16 08 16 < 25 i k j

49 25 25* 21 16 08 0 1 2 3 4 5 21  16 i k j k 指示当前序列中最小者 算法分析 直接选择排序的关键字比较次数KCN与对象的初始排列无关。第 i 趟选择具有最小关键字对象所需的比较次数总是 n-i-1 次，此处假定整个待排序对象序列有 n 个对象。因此，总的关键字比较次数为

对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其关键字从小到大有序的时候，对象的移动次数RMN = 0，达到最少。 最坏情况是每一趟都要进行交换，总的对象移动次数为RMN = 3(n-1)。 直接选择排序是一种不稳定的排序方法。

锦标赛排序 (Tournament Tree Sort) 树形选择排序(Tree Selection Sort) 它的思想与体育比赛时的淘汰赛类似。首先取得 n 个对象的关键字，进行两两比较，得到 n/2 个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来。然后对这 n/2 个对象再进行关键字的两两比较，…，如此重复，直到选出一个关键字最小的对象为止。 在图例中，最下面是对象排列的初始状态，相当于一棵满二叉树的叶结点，它存放的是所有参加排序的对象的关键字。

Winner 08 21 08 21 25* 08 63 21 25 49 25* 16 08 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 如果 n 不是2的 k 次幂，则让叶结点数补足到满足 2k-1 < n  2k 的2k个。叶结点上面一层的非叶结点是叶结点关键字两两比较的结果。最顶层是树的根。

胜者树的概念 每次两两比较的结果是把关键字小者作为优胜者上升到双亲结点，称这种比赛树为胜者树。 位于最底层的叶结点叫做胜者树的外结点，非叶结点称为胜者树的内结点。每个结点除了存放对象的关键字 key 外，还存放了此对象是否要参选的标志 Active 和此对象在满二叉树中的序号index。 胜者树最顶层是树的根，表示最后选择出来的具有最小关键字的对象。

a[0] Winner (胜者) 08 21 08 21 08 63 21 25 49 25* 16 08 63 关键字比较次数 : 6 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 形成初始胜者树（最小关键字上升到根） 关键字比较次数 : 6

a[1] 输出冠军并调整胜者树后树的状态 Winner (胜者) 16 21 16 21 16 63 21 25 49 25* 16 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出冠军并调整胜者树后树的状态 关键字比较次数 : 2

a[2] 输出亚军并调整胜者树后树的状态 Winner (胜者) 21 21 63 21 63 21 25 49 25* 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出亚军并调整胜者树后树的状态 关键字比较次数 : 2

a[3] 输出第三名并调整胜者树后树的状态 Winner (胜者) 25 25 63 25 63 25 49 25* 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出第三名并调整胜者树后树的状态 关键字比较次数 : 2

a[4] 输出第四名并调整胜者树后树的状态 Winner (胜者) 63 63 49 25* 63 关键字比较次数 : 2 25* 25* tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出第四名并调整胜者树后树的状态 关键字比较次数 : 2

a[6] 全部比赛结果输出时树的状态 Winner (胜者) 63 63 63 63 关键字比较次数 : 2 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 全部比赛结果输出时树的状态 关键字比较次数 : 2

归并排序 (Merge Sort) 归并，是将两个或两个以上的有序表合并成一个新的有序表。 对象序列 initList 中有两个有序表V[l] …V[m]和V[m+1] …V[n]。它们可归并成一个有序表，存于另一对象序列 mergedList 的V[l] …V[n]中。 这种归并方法称为2-路归并 (2-way merging)。 其基本思想是：设两个有序表A和B的对象个数(表长)分别为 al 和 bl，变量 i 和 j 分别是表A和表B的当前检测指针。设表C是归并后的新有序表，变量 k 是它的当前存放指针。

当 i 和 j 都在两个表的表长内变化时，根据A[i]与B[j]的关键字的大小，依次把关键字小的对象排放到新表C[k]中； l m m+1 n initList 08 21 25 25* 49 62 72 93 16 37 54 i j l n mergeList 08 16 21 25 25* 37 49 54 62 72 93 k 当 i 和 j 都在两个表的表长内变化时，根据A[i]与B[j]的关键字的大小，依次把关键字小的对象排放到新表C[k]中； 当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表C[k]中。

归并排序算法 此算法的关键字比较次数和对象移动次数均为 (m - l + 1) + (n - m) = n - l + 1。 迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是： 假设初始对象序列有 n 个对象，首先把它看成是 n 个长度为 1 的有序子序列 (归并项)，先做两两归并，得到 n / 2 个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为1)；再做两两归并，…，如此重复，最后得到一个长度为 n 的有序序列。

void Merge(ElemType SR[],ElemType TR[],int i, int m,int n) 两路归并算法 void Merge(ElemType SR[],ElemType TR[],int i, int m,int n) //将有序表的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] { for (int j=m+1,k=i;i<=m && j<=n; ++k) if (LQ(SR[i].key ,SR[j].key)) TR[k] = SR[i++]; else TR[k] = SR[j++]; }

if (i<=m) for (int n1=k,n2=i;n1<=n && n2<=m;n1++,n2++) TR[n1]=SR[n2]; if (j<=n) for (int n1=k,n2=j;n1<=n && n2<=n;n1++,n2++) }

归并排序算法 21 25 49 25* 93 62 72 08 37 16 54 len=1 len=2 21 25 25* 49 62 93 08 72 16 37 54 len=4 21 25 25* 49 08 62 72 93 16 37 54 len=8 08 21 25 25* 49 62 72 93 16 37 54 len=16 08 16 21 25 25* 37 49 54 62 72 93

算法分析 归并排序占用附加存储较多，需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。 归并排序是一个稳定的排序方法。

基数排序 (Radix Sort) 多关键字排序 基数排序是采用“分配”与“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。 多关键字排序 以扑克牌排序为例。每张扑克牌有两个“关键字”：花色和面值。其有序关系为： 花色：       面值：2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A 如果我们把所有扑克牌排成以下次序：  2, …,  A,  2, …,  A,  2, …,  A,  2, …,  A

这就是多关键字排序。排序后形成的有序序列叫做词典有序序列。 对于上例两关键字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。 一般情况下，假定有一个 n 个对象的序列 {V0, V1, …, Vn-1 }，且每个对象Vi 中含有 d 个关键字 如果对于序列中任意两个对象 Vi 和 Vj ( 0  i< j  n-1 ) 都满足：

则称序列对关键字 (K1, K2, …, Kd) 有序。其中，K1 称为最高位关键字，Kd 称为最低位关键字。 如果关键字是由多个数据项组成的数据项组，则依据它进行排序时就需要利用多关键字排序。 实现多关键字排序有两种常用的方法 最高位优先MSD (Most Significant Digit first) 最低位优先LSD (Least Significant Digit first) 最高位优先法通常是一个递归的过程： 先根据最高位关键字K1排序,得到若干对象组，对象组中每个对象都有相同关键字K1。

再分别对每组中对象根据关键字K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。 依此重复，直到对关键字Kd完成排序为止。 最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。 最低位优先法首先依据最低位关键字Kd对所有对象进行一趟排序，再依据次低位关键字Kd-1对上一趟排序的结果再排序，依次重复，直到依据关键字K1最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键字进行排序时，不需要再分组，而是整个对象组都参加排序。

链式基数排序 LSD和MSD方法也可应用于对一个关键字进行的排序。此时可将单关键字 Ki 看作是一个子关键字组： 基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键字进行排序。在这种方法中，把单关键字 Ki 看成是一个d元组： 其中的每一个分量 ( 1 j  d ) 也可看成是一个关键字。

分量 (1  j  d ) 有radix种取值，则称radix为基数。例如，关键字984可以看成是一个3元组(9, 8, 4)，每一位有0, 1, …, 9等10种取值，基数radix = 10。关键字‘data’可以看成是一个4元组(d, a, t, a)，每一位有‘a’, ‘b’, …, ‘z’等26种取值，radix = 26。 针对d元组中的每一位分量，把对象序列中的所有对象, 按 的取值，先“分配”到rd个队列中去。然后再按各队列的顺序，依次把对象从队列中“收集”起来，这样所有对象按取值 排序完成。

如果对于所有对象的关键字K0, K1, …, Kn-1，依次对各位的分量，让 j = d, d-1, …, 1，分别用这种“分配”、“收集”的运算逐趟进行排序，在最后一趟“分配”、“收集” 完成后，所有对象就按其关键字的值从小到大排好序了。 各队列采用链式队列结构，分配到同一队列的关键字用链接指针链接起来。每一队列设置两 个队列指针： int front [radix]指示队头， int rear [radix] 指向队尾。 为了有效地存储和重排 n 个待排序对象，以静态链表作为它们的存储结构。在对象重排时不必移动对象，只需修改各对象的链接指针即可。

基数排序的“分配”与“收集”过程 第一趟 614 738 921 485 637 101 215 530 790 306 第一趟分配（按最低位 i = 3 ） re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9] 790 101 215 530 921 614 485 306 637 738 fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9] 第一趟收集 530 790 921 101 614 485 215 306 637 738

基数排序的“分配”与“收集”过程 第二趟 530 790 921 101 614 485 215 306 637 738 第二趟分配（按次低位 i = 2 ） re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9] 738 306 215 637 101 614 921 485 790 530 fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9] 第二趟收集 101 306 614 215 921 530 637 738 485 790

基数排序的“分配”与“收集”过程 第三趟 101 306 614 215 921 530 637 738 485 790 第三趟分配（按最高位 i = 1 ） re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9] 637 790 101 215 306 485 530 614 738 921 fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9] 第三趟收集 101 215 306 485 530 614 637 738 790 921

小结 需要复习的知识点 排序的基本概念 关键字、初始关键字排列 关键字比较次数、数据移动次数 稳定性 附加存储 插入排序 小结 需要复习的知识点 排序的基本概念 关键字、初始关键字排列 关键字比较次数、数据移动次数 稳定性 附加存储 插入排序 直接插入排序、折半插入排序的过程 直接插入排序和折半插入排序的算法

排序的性能分析 当待排序的关键字序列已经基本有序时，用直接插入排序最快 选择排序 直接选择排序、锦标赛排序、堆排序的过程 直接选择排序和堆排序的算法 三种选择排序的性能分析 用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，不是顺次后移。这导致方法不稳定。

交换排序 起泡排序和快速排序的过程 起泡排序的算法 快速排序的递归算法和用栈实现的非递归算法 快速排序是一个递归的排序法 当待排序关键字序列已经基本有序时，快速排序显著变慢。

二路归并排序 二路归并排序的过程 二路归并排序的非递归算法 该算法的性能分析 归并排序可以递归执行 归并排序需要较多的附加存储。 归并排序对待排序关键字的初始排列不敏感，故排序速度较稳定。

思考题： 1、已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用下列排序时每一趟的排序结果： 1）直接插入排序 2）快速排序法 3）归并排序法 2、试以单链表为存储结构实现简单选择排序的算法。