第十章内部排序 概述 插入排序 快速排序 选择排序 归并排序 基数排序

概 述 排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。 数据表(datalist): 它是待排序数据对象的有限集合。 概 述 排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。 数据表(datalist): 它是待排序数据对象的有限集合。 主关键字(key): 数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分对象, 作为排序依据，称为关键字。也称为排序码。

排序方法的稳定性: 如果在对象序列中有两 个对象r[i]和r[j], 它们的排序码 k[i] == k[j] , 且在排序之前, 对象r[i]排在r[j]前面。如果在排序之后, 对象r[i]仍在对象r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。 内排序与外排序: 内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。

排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。

内排序分类 依不同原则 插入排序、交换排序、选择排序、归并排序、和计数排序等。 依所须工作量 简单排序---时间复杂度o(n2) 先进排序方法---时间复杂度o(n logn) 基数排序---时间复杂度o(d.n)

插入排序 (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]插入, 原来位置上的对象向后顺移。

直接插入排序过程 0 1 2 3 4 5 temp 21 08 25 49 25* 16 i = 1 0 1 2 3 4 5 temp 21 25 49 25* 16 08 25 21 25 08 49 25* 16 i = 2 21 25 08 49 25* 16 21 25 49 25* 16 08 i = 3 21 25 49 25* 16 08 25* 21 25 25* 49 16 08

21 25 08 49 25* 16 i = 4 21 25 08 49 25* 16 i = 5

直接插入排序的算法 typedef int SortData; void InsertSort ( SortData V[ ], int n ) { //按非递减顺序对表进行排序 SortData temp; int i, j; for ( i = 1; i < n; i++ ) { temp = V[i]; for ( j = i; j > 0; j-- ) //从后向前顺序比较 if ( temp < V[j-1] ) V[j] = V[j-1]; else break; V[j] = temp; }

算法分析 设待排序对象个数为 n, 则该算法的主程序执行n-1趟。 排序码比较次数和对象移动次数与对象排序码的初始排列有关。

最坏情况下, 第 i 趟时第 i 个对象必须与前面 i 个对象都做排序码比较, 并且每做1次比较就要做1次数据移动。则总排序码比较次数KCN和对象移动次数RMN分别为 在平均情况下的排序码比较次数和对象移动次数约为 n2/4。因此，直接插入排序的时间复杂度为 o(n2)。 直接插入排序是一种稳定的排序方法。

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

void BinInsSort ( SortData V[ ], int n ) { typedef int SortData; void BinInsSort ( SortData V[ ], int n ) { SortData temp; int Left, Right; for ( int i = 1; i < n; i++) { Left = 0; Right = i-1; temp = V[i]; while ( Left <= Right ) { int mid = ( Left + Right )/2; if ( temp < V[mid] ) Right = mid - 1; else Left = mid + 1; } for ( int k = i-1; k >= Left; k-- ) V[k+1] = V[k];// 记录后移 V[Left] = temp; //插入

折半插入排序 i = 1 i = 2 i = 3 i = 4 i = 5 0 1 2 3 4 5 temp 21 5 5 8 8 i = 5 3 4 5 8 21 16 16 3 4 5 8 16 21

算法分析 折半搜索比顺序搜索查找快, 所以折半插入排序就平均性能来说比直接插入排序要快。 它所需的排序码比较次数与待排序对象序列的初始排列无关, 仅依赖于对象个数。在插入第 i 个对象时, 需要经过 log2i +1 次排序码比较, 才能确定它应插入的位置。因此, 将 n 个对象(为推导方便, 设为 n=2k )用折半插入排序所进行的排序码比较次数为：

当 n 较大时, 总排序码比较次数比直接插入排序的最坏情况要好得多, 但比其最好情况要差。 在对象的初始排列已经按排序码排好序或接近有序时, 直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同, 依赖于对象的初始排列。 折半插入排序是一个稳定的排序方法。 折半插入排序的时间复杂度为o(n2)。

希尔排序 (Shell Sort) 基本思想设待排序对象序列有 n 个对象, 首先取一个整数 gap < n 作为间隔, 将全部对象分为 gap 个子序列, 所有距离为 gap 的对象放在同一个子序列中, 在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap, 例如取 gap = gap/2，重复上述的子序列划分和排序工作。直到最后取 gap == 1, 将所有对象放在同一个序列中排序为止。 希尔排序方法又称为缩小增量排序。

希尔排序过程 i = 3 i = 2 i = 1 Gap = 3 Gap = 2 Gap = 1 0 1 2 3 4 5 21 08 25 0 1 2 3 4 5 21 08 25 49 25* 16 i = 3 Gap = 3 0 1 2 3 4 5 21 08 25 49 25* 16 i = 2 21 16 08 25* 25 49 Gap = 2 21 08 25 49 25* 16 i = 1 21 08 25 49 25* 16 Gap = 1 21 08 25 49 25* 16

希尔排序的算法 typedef int SortData; void ShellSort ( SortData V[ ], int n ) { SortData temp; int gap = n / 2; //gap是间隔 while ( gap != 0 ) { //循环,直到gap为零 for ( int i = gap; i < n; i++) { temp = V[i]; //直接插入排序 for ( int j = i; j >= gap; j = j-gap ) if ( temp < V[j-gap] ) V[j] = V[j-gap]; else break; V[j] = temp; } gap = ( int ) ( gap / 2 );

开始时 gap 的值较大, 子序列中的对象较少, 排序速度较快; 随着排序进展, gap 值逐渐变小, 子序列中对象个数逐渐变多, 由于前面大多数对象已基本有序, 所以排序速度仍然很快。 Gap的取法有多种。 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。 对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数。 希尔排序所需的比较次数和移动次数约为n 1.3 当n趋于无穷时可减少到n(log2 n)2

快速排序 ( Exchange Sort ) 起泡排序 (Bubble Sort) 基本思想是两两比较待排序对象的排序码,如发生逆序(即排列顺序与排序后的次序正好相反)，则交换之,直到所有对象都排好序为止。 起泡排序 (Bubble Sort) 基本方法设待排序对象序列中的对象个数为n。一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录的关键字，如果发生逆序，则交换之，其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。

下起泡排序的过程 16 08 21 21 49 25 16 08 21 49 25 16 08 21 08 16 25 16 21 21 49 08 25 25 25 25 25 25 16 25 49 49 08 49 初 始 关 键 字 第 一 趟 排 序 第 二 趟 排 序 第 三 趟 排 序 第 四 趟 排 序 第 五 趟 排 序

上起泡排序的过程 08 08 08 21 08 08 21 16 16 25 16 16 25 21 49 21 21 21 49 25 25 25 25 25 25 16 49 25 25 25 08 16 25 49 49 49 初 始 关 键 字 第 一 趟 排 序 第 二 趟 排 序 第 三 趟 排 序 第 四 趟 排 序 第 五 趟 排 序

上起泡排序的算法 Swap ( V[j-1], V[j] ); //交换 exchange = 1; //标志置为1,有交换 typedef int SortData; void BubbleSort ( SortData V[ ], int n ) { int i = 1; int exchange = 1; while ( i < n && exchange ){ exchange = 0; //标志置为0,假定未交换 for ( int j = n-1; j >= i; j-- ) if ( V[j-1] > V[j] ) { //逆序 Swap ( V[j-1], V[j] ); //交换 exchange = 1; //标志置为1,有交换 } i++; 思考题：如何实现双起泡

第i趟对待排序对象序列V[i-1],V[i],,V[n-1]进行排序, 结果将该序列中排序码最小的对象交换到序列的第一个位置(i-1), 其它对象也都向排序的最终位置移动。。

最坏的情形是算法执行n-1趟起泡,第i趟 (1 i n) 做 n- i 次排序码比较, 执行 n-i 次对象交换。这样在最坏情形下总的排序码比较次数KCN和对象移动次数RMN为： 起泡排序是一个稳定的排序方法。

快速排序 (Quick Sort) 基本思想:任取待排序序列中的某个结点 (通常取第一个结点) 作为基准, 序列中所有其它结点与它比较，将较它小的结点放在它的前面；较它大的结点放在它的之后，这样可按该结点为界将序列分成两部分，然后再分别对这两部分重复上述过程，直至每一部分只剩一个元素为止。

分段算法： 所选结点送w，让i指向空位 在i空位情况下，把j指向元素与w比较，>=w时，推行j；>=w时，送i空位，并推进i,这时j所指是空位 在j空位情况下，把i指向元素与w比较，<=w时，推行i；>=w时，送j空位，并推进j,这时i所指是空位 交替②③重复，至i=j为止。

快速排序算法描述 QuickSort ( List ) { if ( List的长度大于1) { 将序列List划分为两个子序列 LeftList 和 Right List; QuickSort ( LeftList ); QuickSort ( RightList ); 将两个子序列 LeftList 和 RightList 合并为一个序列List; }

快速排序的过程 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 QuickSort ( SqList &L, int low, int high ){ //在序列lowhigh 中递归地进行快速排序 if ( low < high) { int pivotloc= Partition (L, low, high); //划分 QuickSort ( L, low, pivotloc-1); //对左序列同样处理 QuickSort ( L, pivotloc+1, high); //对右序列同样处理 }

int Partition ( SqList &L, int low, int high ) { L.r[0]=L.r[low];//子表的第一个记录作基准对象 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 25* 25 49 08 16

算法分析 快速排序的趟数取决于递归树的高度。 如果每次划分对一个对象定位后, 该对象的左侧子序列与右侧子序列的长度相同, 则下 一步将是对两个长度减半的子序列进行排序, 这是最理想的情况。 在 n个元素的序列中, 对一个对象定位所需时间为 O(n)。若设 t (n) 是对 n 个元素的序列进行排序所需的时间, 而且每次对一个对象正确定位后, 正好把序列划分为长度相等的两个子序列, 此时, 总的计算时间为：

T(n)  cn + 2T(n/2 ) // c 是一个常数  cn + 2 ( cn/2 + 2T(n/4) ) = 2cn + 4T(n/4)  2cn + 4 ( cn/4 +2T(n/8) ) = 3cn + 8T(n/8) ………  cn log2n + nT(1) = O(n log2n ) 可以证明, 函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明: 就平均计算时间而言, 快速排序是所有内排序方法中最好的一个。 快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。

最大递归调用层次数与递归树的高度一致,理想情况为 log2(n+1) 。因此，要求存储开销为 O(log2n)。 在最坏的情况, 即待排序对象序列已经按其排序码从小到大排好序的情况下, 其递归树成为单支树, 每次划分只得到一个比上一次少一个对象的子序列。总的排序码比较次数将达 快速排序是一种不稳定的排序方法。

选择排序 基本思想 每一趟 (例如第 i 趟, i = 0, 1, …, n-2) 在后面 n-i 个待排序 记录中选出排序码最小的记录, 作为 有序序列中的第 i 个记录。待到第 n-2 趟作完, 待排序记录只剩下1个, 就不用再选了。

直接选择排序 (Select Sort) 直接选择排序是一种简单的排序方法, 它的基本步骤是： 直接选择排序是一种简单的排序方法, 它的基本步骤是： 在一组对象 V[i]～V[n-1] 中选择具有最小排序码的对象； 若它不是这组对象中的第一个对象, 则将它与这组对象中的第一个对象对调; 在这组对象中剔除这个具有最小排序码的对象。在剩下的对象V[i+1]～V[n-1]中重复执行第①、②步, 直到剩余对象只有一个为止。

i = 0 i = 1 i = 2 初始 最小者 08 交换21,08 最小者 16 交换25,16 最小者 21 交换49,21 直接选择排序的过程 21 25 49 25* 16 08 0 1 2 3 4 5 i = 0 i = 1 i = 2 初始 最小者 08 交换21,08 最小者 16 交换25,16 最小者 21 交换49,21

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

直接选择排序的算法 typedef int SortData; void SelectSort ( SortData V[ ], int n ) { for ( int i = 0; i < n-1; i++ ) { int k = i; //选择具有最小排序码的对象 for ( int j = i+1; j < n; j++) if ( V[j] < V[k] ) k = j; //当前具最小排序码的对象 if ( k != i ) //对换到第 i 个位置 Swap ( V[i], V[k] ); }

直接选择排序的排序码比较次数 KCN 与对象的初始排列无关。设整个待排序对象序列有 n 个对象, 则第 i 趟选择具有最小排序码对象所需的比较次数总是 n-i-1 次。总的排序码比较次数为 对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其排序码从小到大有序的时候, 对象的移动次数RMN = 0，达到最少。 最坏情况是每一趟都要进行交换，总的对象移动次数为 RMN = 3(n-1)。 直接选择排序是一种不稳定的排序方法。

堆排序( Heap sort ) 堆 ( Heap )设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从 0开始连续编号。若满足 Ki  K2i+1 && Ki  K2i+2 或 Ki  K2i+1 && Ki  K2i+2, 则称该关键字集合构成一个堆。 前者成为最小堆，后者称为最大堆。

完全二叉树 顺序表示 Ki  K2i+1 & Ki  K2i+2 Ki  K2i+1 && Ki  K2i+2 09 87 78 45 65 31 53 23 17 完全二叉树 顺序表示 Ki  K2i+1 & Ki  K2i+2 Ki  K2i+1 && Ki  K2i+2

堆排序 (Heap Sort) 利用堆及其运算, 可以很容易地实现选择排序的思路。 堆排序分为两个步骤 根据初始输入数据，利用堆的调整算法 FilterDown( ) 形成初始堆; 通过一系列的对象交换和重新调整堆进行排序。

初始小顶堆的建立过程 自下向上逐步调整为小顶堆 53 17 78 09 23 45 65 87 i i = 4 i = 3

53 17 78 09 23 45 65 87 i i = 2

i 53 i 09 09 65 53 65 17 45 78 87 17 45 78 87 23 23 i = 1

09 09 17 65 17 65 i 53 45 78 87 23 45 78 87 i 23 53 建成堆

堆的建立 void Crt_MinHeap ( MinHeap *H, HeapData arr[ ], int n ) { //根据给定数组中的数据和大小,建立堆 for ( int i = 0; i < n; i++ ) H->data[i] = arr[i]; H->CSize = n; //数组传送及当前堆大小 int CPos = (H->CSize-2)/2; //最后分支结点 while ( CPos >= 0 ) { //从下到上逐步扩大堆 FilterDown ( &H, CPos, H->CSize-1 ); CPos--; }

最小堆的向下调整算法 void FilterDown ( MinHeap *H, int start, int EndOfHeap ) { int i = start, j = 2*i+1; // j 是 i 的左子女 HeapData temp = H->data[i]; while ( j <= EndOfHeap ) { if ( j < EndOfHeap && //两子女中选小者 H->data[j] > H->data[j+1] ) j++; if ( temp <= H->data[j] ) break; else { H->data[i] = H->data[j]; i = j; j = 2*j+1; } //向下滑动 } H->data[i] = temp;

初始大顶堆的建立过程 21 i i 21 1 1 2 2 25 49 25 49 3 4 5 3 4 5 25* 16 08 25* 16 08 初始排序码集合 i = 2 时的局部调整

i 21 49 1 1 2 2 25 49 25 21 3 4 5 3 4 5 25* 16 08 25* 16 08 i = 0 时的局部调整 形成最大堆 i = 1 时的局部调整

最大堆的向下调整算法 void FilterDown ( MaxHeap *H, int start, int EndOfHeap ) { int i = start; int j = 2*i+1; HeadData temp = H->data[i]; while ( j <= EndOfHeap ) { //最后位置 if ( j < EndOfHeap && H->data[j] < H->data[j+1] ) j = j+1; //选两子女的大者 if ( temp >= H->data[j] ) break; else {

H->data[i] = H->data[j]; //大子女上移 i = j; j = 2*j+1; //向下继续调整 } H->data[i] = temp; //回放到合适位置 将表转换成堆 for ( int i = ( H->CSize-2) / 2 ; i >= 0; i-- ) FilterDown ( H, i, H->CSize-1 );

基于初始堆(大顶堆)进行堆排序 最大堆堆顶V[0]具有最大的排序码, 将V[0]与 V[n-1]对调, 把具有最大排序码的对象交换到最后, 再对前面的n-1个对象, 使用堆的调整算法FilterDown(0, n-2), 重新建立最大堆, 具有次最大排序码的对象又上浮到V[0]位置。 再对调V[0]和V[n-2],调用FilterDown(0, n-3), 对前n-2个对象重新调整，…。 如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法，

基于初始堆进行堆排序 49 08 1 1 2 2 25 21 25 21 3 4 5 3 4 5 25* 16 08 25* 16 49 49 25 21 25* 16 08 08 25 21 25* 16 49 初始最大堆 交换 0 号与 5 号对象, 5 号对象就位

25 16 1 1 2 2 25* 21 25* 21 3 4 5 3 4 5 08 16 49 08 25 49 25 25* 21 08 16 49 16 25* 21 08 25 49 从 0 号到 4 号 重新 调整为最大堆 交换 0 号与 4 号对象, 4 号对象就位

25* 08 1 1 2 2 16 21 16 21 3 4 5 3 4 5 08 25 49 25* 25 49 25* 16 21 08 25 49 08 16 21 25* 25 49 从 0 号到 3 号 重新 调整为最大堆 交换 0 号与 3 号对象, 3 号对象就位

21 08 1 1 2 2 16 08 16 21 3 4 5 3 4 5 25* 25 49 25* 25 49 21 16 08 25* 25 49 08 16 21 25* 25 49 从 0 号到 2 号 重新 调整为最大堆 交换 0 号与 2 号对象, 2 号对象就位

16 08 1 1 2 2 08 21 16 21 3 4 5 3 4 5 25* 25 49 25* 25 49 16 08 21 25* 25 49 08 16 21 25* 25 49 从 0 号到 1 号 重新 调整为最大堆 交换 0 号与 1 号对象, 1 号对象就位

堆排序的算法 void HeapSort ( MaxHeap *H ) { //对表heap[0]到heap[n-1]进行排序, 使得表中 //各个对象按其排序码非递减有序。 for ( int i = ( H->CSize-2 ) / 2; i >= 0; i-- ) FilterDown ( H, i, H->CSize-1 ); //初始堆 for ( i = H->CSize-1; i >= 1; i--) { Swap ( H->data[0], H->data[i] ); //交换 FilterDown ( H, 0, i-1 ); //重建最大堆 }

堆排序的算法分析 若设堆中有 n 个结点, 且 2k-1  n  2k, 则对应的完全二叉树有 k 层。在第 i 层上的结点数  2i (i = 0, 1, …, k-1)。 在第一个形成初始堆的 for 循环中对每一个非叶结点调用了 一次堆调整算法FilterDown( ), 因此该循环所用的计算时间为： 其中, i 是层序号, 2i 是第 i 层的最大结点数, (k-i-1)是第 i 层结点能够移动的最大距离。

第二个for循环中调用了n-1次FilterDown( )算法, 该循环的计算时间为O(nlog2n)。因此, 堆排序的时间复杂性为O(nlog2n)。 该算法的附加存储主要是在第二个for循环中用来执行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为O(1)。 堆排序是一个不稳定的排序方法。

归并排序 (Merge Sort) 归并将两个或两个以上的有序表合并成一个新的有序表。 两路归并 (2-way merging)原始序列initList[ ]中两个有序表 initList[l] … initList[m]和initList[m+1] … initList[n]，它们可归并成一个有序表, 存于另一对象序列mergedList的 l … n 中。

设变量 i 和 j 是表initList[l … m]和initList [m+1… n]的当前检测指针。k 是存放指针。 left mid mid+1 right initList 08 21 25 25* 49 62 72 93 16 37 54 j i left right mergeList 08 16 21 25 25* 37 49 54 62 72 93 k 设变量 i 和 j 是表initList[l … m]和initList [m+1… n]的当前检测指针。k 是存放指针。 当 i 和 j 都在两个表的表长内变化时, 根据对应项的排序码的大小, 依次把排序码小的对象排放到新表 k 所指位置中； 当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中。

两路归并算法 typedef int SortData; void merge ( SortData InitList[ ], SortData mergedList[ ], int left, int mid, int right ) { int i = left, j = mid+1, k = left; while ( i <= mid && j <= right ) //两两比较将较小的并入 if ( InitList[i] <= InitList[j] ) { mergedList [k] = InitList[i]; i++; k++; } else { mergedList [k] = InitList[j]; j++; k++; } while ( i <= mid ) { mergedList[k] = InitList[i]; i++; k++; }//将mid前剩余的并入 while ( j <= right ) { mergedList[k] = InitList[j]; j++; k++; } //将mid后剩余的并入 }

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

迭代的归并排序算法 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

while (i+2*len-1 <= n-1) { merge( initList, mergedList, 归并排序的算法 void MergePass ( SortData initList[ ], SortData mergedList[ ], int len ) {将表initlist中两个长度为len的 有序表归并，结果放在mergedList中 int i = 0; while (i+2*len-1 <= n-1) { merge( initList, mergedList, i, i+len-1, i+2*len-1); i += 2 * len; //对长度为Len的子表两两归并，直到表中剩余元素个 数不足2×len } if ( i+len <= n-1 ) merge( initList, mergedList, i, i+len-1, n-1); //若仍然有一个长度为Len的子表，再作一次归并，另一表 长不足len else for ( int j = i; j <= n-1; j++) mergedList [j] = initList[j]; //若不能归并，复制 }

void MergeSort ( SortData initList[ ], int n ) { SortData tempList[n]; 归并排序的递归算法 void MergeSort ( SortData initList[ ], int n ) { //按对象排序码非递减的顺序对表中对象排序 SortData tempList[n]; int len = 1; while ( len < n ) { MergePass ( initList, tempList, len ); len *= 2; MergePass ( tempList, initList, len ); }

在迭代的归并排序算法中, 函数MergePass( ) 做一趟两路归并排序, 要调用merge ( )函数 n/(2 在迭代的归并排序算法中, 函数MergePass( ) 做一趟两路归并排序, 要调用merge ( )函数 n/(2*len)  O(n/len) 次, 函数MergeSort( )调用MergePass( )正好log2n 次,而每次merge( )要执行比较O(len)次, 所以算法总的时间复杂度为O(nlog2n)。 归并排序占用附加存储较多, 需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。 归并排序是一个稳定的排序方法。

基数排序 多关键字排序 例 对52张扑克牌按以下次序排序： 例 对52张扑克牌按以下次序排序： 2<3<……<A<2<3<……<A< 2<3<……<A<2<3<……<A 两个关键字：花色（ <<< ） 面值（2<3<……<A） 并且“花色”地位高于“面值” 多关键字排序方法 最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列

第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表 重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列

最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列