第九章 排序 概述 插入排序 交换排序 选择排序 归并排序 基数排序 外排序

概述 排序：将一组杂乱无章的数据按一定的规律顺次排列起来。 数据表(datalist): 它是待排序数据对象的有限集合。 排序码(key): 通常数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分对象, 作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。

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

排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。 算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。 算法执行时所需的附加存储: 评价算法好坏的另一标准。

待排序数据表的类定义 #include <iostream.h> const int DefaultSize = 100; template <class Type> class dataList { template <class Type> class Element { friend class dataList<Type>; private: Type key; //排序码 field otherdata; //其它数据成员 public: Element ( ) : key(0), otherdata(NULL) { }

void setKey ( const Type x ) { key = x; } //修改 Type getKey ( ) { return key; } //提取排序码 void setKey ( const Type x ) { key = x; } //修改 Element<Type> & operator = //赋值 ( Element<Type>& x ) { key = x->key; otherdata = x->otherdata; } int operator == (Element<Type>& x ) { return key == x->key; } //判this == x int operator <= (Element<Type>& x ) { return key <= x->key; } //判this  x int operator < (Element<Type>& x ) { return key < x->key; } //判this < x

int operator > (Element<Type>& x ) { return key > x->key; } //判this > x } template <class Type> class dataList { private: Element <Type> * Vector; //存储向量 int MaxSize, CurrentSize; //最大与当前个数public: datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element <Type> [MaxSz]; }

void sort ( ); //排序 void swap ( Element <Type> & x, //对换 Element <Type> & y ) { Element<Type> temp = x; x = y; y = temp; }

插入排序 (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

直接插入排序的算法 template <class Type> void dataList <Type> :: InsertSort ( ) { //按排序码 Key 非递减顺序对表进行排序 Element<Type> temp; int i, j; for ( i = 1; i < CurrentSize; i++ ) { temp = Vector[i]; for ( j = i; j > 0; j-- ) //从后向前顺序比较 if ( temp < Vector[j-1] ) Vector[j] = Vector[j-1]; else break; Vector[j] = temp;

} 算法分析 设待排序对象个数为currentSize = n, 则该算法的主程序执行n-1趟。 排序码比较次数和对象移动次数与对象排序码的初始排列有关。 最好情况下, 排序前对象已按排序码从小到大有序, 每趟只需与前面有序对象序列的最后一个对象比较1次, 移动2次对象, 总的排序码比较次数为 n-1, 对象移动次数为 2(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] 的插入位置。 折半插入排序的算法 template <class Type> void dataList<Type> :: BineryInsSort ( ) { Element<Type> temp; int Left, Right; for ( int i = 1; i < CurrentSize; i++) { Left = 0; Right = i-1; temp = Vector[i];

while ( Left <= Right ) { int middle = ( Left + Right )/2; if ( temp < Vector[middle] ) Right = middle - 1; else Left = middle + 1; } for ( int k = i-1; k >= Left; k-- ) Vector[k+1] = Vector[k]; Vector[Left] = temp; 算法分析

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

当 n 较大时, 总排序码比较次数比直接插入排序的最坏情况要好得多, 但比其最好情况要差。 在对象的初始排列已经按排序码排好序或接近有序时, 直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同, 依赖于对象的初始排列。

链表插入排序 基本思想是：在每个对象的结点中增加一个链接指针数据成员 link。 对于数组中的一组对象V[1], …, V[n], 若V[1], …,V[i-1]已经通过指针link, 按其排序码从小到大链接起来。现要插入V[i], i = 2, 3, …, n, 则必须在前面i-1个链接起来的对象当中, 循链检测比较, 找到 V[i] 应插入的位置，把V[i] 链入, 并修改相应链接指针。从而得到V[1], …, V[i]的一个通过指针排好的链表。 如此重复执行，直到把V[n]也插入到链表中排好序为止。

 初始 i = 2 i = 3 i = 4 49 25 25* 21 16 08 0 1 2 3 4 5 6 current pre i 0 1 2 3 4 5 6 初始 i = 2 current pre i i = 3 current pre i i = 4 pre current i

 49 25 25* 21 16 08 0 1 2 3 4 5 6 i = 5 pre current i i = 6 pre current i 结果

用于链表排序的静态链表的类定义 template <class Type> class staticlinklist; template <class Type> class Element { private: Type key; //结点的排序码 int link; //结点的链接指针 public: Element ( ) : key(0), link (NULL) { } Type getKey ( ) { return key; } void setKey ( const Type x ) { key = x; } int getLink ( ) { return link; } void setLink ( const int l ) { link = l; }

} template <class Type> class staticlinklist { private: Element <Type> * Vector; //存储向量 int MaxSize, CurrentSize; //向量中最大元素个数和当前元素个数public: dstaticlinklist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element <Type> [MaxSz]; }

链表插入排序的算法 template <class Type> int staticlinklis<Type> :: LinkedInsSort ( ) { Vector[0].key = MaxNum; Vector[0].link = 1; Vector[1].link = 0; //元素V[0]与V[1]形成循环链表 for ( int i = 2; i <= CurrentSize; i++ ) { int current = Vector[0].link; //检测指针 int pre = 0; //检测指针的前驱指针 while ( Vector[current].key <= Vector[i].key ) { //找插入位置 pre = current; //pre跟上, current向前走

current = Vector[current].link; } Vector[i].link = current; Vector[pre].link = i; //在pre与current之间链入 使用链表插入排序, 每插入一个对象, 最大排序码比较次数等于链表中已排好序的对象个数, 最小排序码比较次数为1。故总的排序码比较次数最小为 n-1，最大为

用链表插入排序时, 对象移动次数为0。但为 了实现链表插入, 在每个对象中增加了一个链域 link, 并使用了Vector[0] 作为链表的表头结点, 用了 n 个附加域和一个附加对象。 算法在Vector[pre].key == Vector[i].key时,将Vector[i]插在Vector[pre]的后面, 所以, 链表插入排序方法是稳定的。

希尔排序 (Shell Sort) 希尔排序方法又称为缩小增量排序。该方法的基本思想是 : 设待排序对象序列有 n 个对象, 首先取一个整数 gap < n 作为间隔, 将全部对象分为 gap 个子序列, 所有距离为 gap 的对象放在同一个子序列中, 在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap, 例如取 gap = gap/2，重复上述的子序列划分和排序工作。直到最后取 gap == 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 值逐渐变小, 子序列中对象个数逐渐变多, 由于前面工作的基础, 大多数对象已基本有序, 所以排序速度仍然很快。

希尔排序的算法 template <class Type> void dataList<Type> :: ShellSort ( ) { Element<Type> temp; int gap = CurrentSize / 2; //gap是子序列间隔 while ( gap != 0 ) { //循环,直到gap为零 for ( int i = gap; i < CurrentSize; i++) { temp = Vector[i]; //直接插入排序 for ( int j = i; j >= gap; j -= gap ) if ( temp < Vector[j-gap] ) Vector[j] = Vector[j-gap]; else break;

Vector[j] = temp; } gap = ( int ) ( gap / 2 ); Gap的取法有多种。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。knuth 提出取 gap = gap/3 +1。还有人提出都取奇数为好，也有人提出各 gap 互质为好。 对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数。

想要弄清排序码比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。 Knuth利用大量实验统计资料得出 : 当 n 很大时，排序码平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。

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

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

template <class Type> 49 i = 4 25 25* 21 16 08 Exchang=0 0 1 2 3 4 5 起泡排序的算法 template <class Type> void dataList<Type> :: BubbleSort ( ) { int pass = 1; int exchange = 1; while ( pass < CurrentSize && exchange ){ exchange = 0; //标志置为0,假定未交换 for ( int j = CurrentSize-1; j >= pass; j-- ) if ( Vector[j-1] > Vector[j] ) { //逆序

Swap ( Vector[j-1], Vector[j] ); //交换 exchange = 1; //标志置为1,有交换 } pass++; 第i趟对待排序对象序列V[i-1],V[i],,V[n-1]进行排序, 结果将该序列中排序码最小的对象交换到序列的第一个位置(i-1), 其它对象也都向排序的最终位置移动。在个别情形, 对象可能在排序中途向相反的方向移动。

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

快速排序 (Quick Sort) 起泡排序需要一个附加对象以实现对象值的对换。 起泡排序是一个稳定的排序方法。 基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准, 按照该对象的排序码大小, 将整个对象序列划分为左右两个子序列：

左侧子序列中所有对象的排序码都小于或等于基准对象的排序码 右侧子序列中所有对象的排序码都大于基准对象的排序码 基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。

算法描述 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

i = 1 划分 pivotpos 49 25 25* 21 16 08 0 1 2 3 4 5 i pivotpos 比较4次 0 1 2 3 4 5 i pivotpos 比较4次 交换25,16 49 21 25* 25 16 08 i 比较1次 交换49,08 pivotpos 49 25* 25 21 16 08 low pivotpos 49 25* 25 交换21,08 21 16 08

快速排序的算法 template <class Type> void dataList<Type> :: QuickSort ( const int left, const int right ) { //在序列 leftright 中递归地进行快速排序 if ( left < right) { int pivotpos = Partition ( left, right ); //划分 //对左序列同样处理 QuickSort ( left, pivotpos-1); //对右序列同样处理 QuickSort ( pivotpos+1, right ); }

template <class Type> int dataList<Type> :: Partition ( const int low, const int high ) { int pivotpos = low; //基准位置 Element<Type> pivot = Vector[low]; for ( int i = low+1; i <= high; i++ ) if ( Vector[i] < pivot ) { pivotpos++; if ( pivotpos != i ) Swap ( Vector[pivotpos], Vector[i] ); } //小于基准对象的交换到区间的左侧去 Swap ( Vector[low], Vector[pivotpos] ); return pivotpos; }

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

算法分析 从快速排序算法的递归树可知, 快速排序的趟数取决于递归树的高度。 如果每次划分对一个对象定位后, 该对象的左侧子序列与右侧子序列的长度相同, 则下 一步将是对两个长度减半的子序列进行排序, 这是最理想的情况。 在 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)。 在最坏的情况, 即待排序对象序列已经按其排序码从小到大排好序的情况下, 其递归树成为单支树, 每次划分只得到一个比上一次少一个对象的子序列。必须经过n-1 趟才能把所有对象定位, 而且第 i 趟需要经过 n-i 次排序码比较才能找到第 i 个对象的安放位置，总的排序码比较次数将达到

用第一个对象作为基准对象 快速排序退化的例子 初始 08 16 21 25 25* 49 08 i = 1 08 0 1 2 3 4 5 pivot 初始 08 16 21 25 25* 49 08 i = 1 08 16 21 25 25* 49 16 i = 2 08 16 21 25 25* 49 21 i = 3 08 16 21 25 25* 49 25 i = 4 08 16 21 25 25* 49 25* i = 5 08 16 21 25 25* 49 用第一个对象作为基准对象 快速排序退化的例子

其排序速度退化到简单排序的水平, 比直接插入排序还慢。占用附加存储(栈)将达到O(n)。 改进办法: 取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的 3 个对象，取其排序码居中者作为基准对象。 0 1 2 3 4 5 pivot 初始 08 16 21 25 25* 49 21 i = 1 08 16 21 25 25* 49 08 25* i = 2 08 16 21 25 25* 49 用居中排序码对象作为基准对象

Type mid ( Type a, Type b, Type c ) { Type first = a, second; //first记录最小 if ( b < first ) { second = first; first = b; } else second = b; //second记录次小 if ( c < first ) { second = first; first = c; } else if ( c < second ) second = c; return second; } 快速排序是一种不稳定的排序方法。 对于 n 较大的平均情况而言, 快速排序是“快速”的, 但是当 n 很小时, 这种排序方法往往比其它简单排序方法还要慢。

选择排序 基本思想是: 每一趟 (例如第 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 49 25* 21 16 08 0 1 2 3 4 5 49 最小者 08 交换21,08 i = 0 25 25* 21 16 08 49 最小者 16 交换25,16 i = 1 25 25* 21 16 08 49 最小者 21 交换49,21 25* 25 i = 2 21 16 08

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

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

i =1时选择排序的过程 49 25 25* 21 16 08 0 1 2 3 4 5 i k j 49  25 49 25 25* 21 16 08 i k j 25*  25 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 与对象的初始排列无关。设整个待排序对象序列有 n 个对象, 则第 i 趟选择具有最小排序码对象所需的比较次数总是 n-i-1 次。总的排序码比较次数为

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

锦标赛排序 (Tournament Tree 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 个。叶结点上面一层的非叶结点是叶结点排序码两两比较的结果。最顶层是树的根。

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

a[0] up 对手不参选 Winner (胜者) 08 21 08 21 08 63 21 25 49 25* 16 08 63 VS. 比较 Winner (胜者) 08 a[0] VS. 21 08 VS. VS. 21 25* 08 63 up VS. VS. VS. 21 25 49 25* 16 08 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 形成初始胜者树（最小排序码上升到根） 排序码比较次数 : 6

a[1] 输出冠军并调整胜者树后树的状态 up 对手不参选 Winner (胜者) 16 21 16 21 16 63 21 25 49 VS. 比较 Winner (胜者) 16 a[1] VS. 21 16 VS. 21 25* 16 63 up 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] 输出亚军并调整胜者树后树的状态 up 对手不参选 Winner (胜者) 21 21 63 21 63 21 25 49 25* VS. 比较 Winner (胜者) 21 a[2] VS. 21 63 up 21 25* 63 21 25 49 25* 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出亚军并调整胜者树后树的状态 排序码比较次数 : 1

a[3] 输出第三名并调整胜者树后树的状态 up 对手不参选 Winner (胜者) 25 25 63 25 63 25 49 25* 63 VS. 比较 Winner (胜者) 25 a[3] VS. 25 63 VS. 25 25* 63 up 25 49 25* 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出第三名并调整胜者树后树的状态 排序码比较次数 : 2

a[4] 输出第四名并调整胜者树后树的状态 up 对手不参选 Winner (胜者) 63 63 49 25* 63 排序码比较次数 : 1 VS. 比较 Winner (胜者) 25* a[4] VS. 25* 63 up 25* 63 49 25* 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出第四名并调整胜者树后树的状态 排序码比较次数 : 1

a[5] 输出第五名并调整胜者树后树的状态 up 对手不参选 Winner (胜者) 63 63 49 63 排序码比较次数 : 1 VS. 比较 Winner (胜者) 49 a[5] VS. 49 63 up 49 63 up 49 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 输出第五名并调整胜者树后树的状态 排序码比较次数 : 1

a[6] 全部比赛结果输出时树的状态 up 对手不参选 Winner (胜者) 63 63 63 63 排序码比较次数 : 0 VS. 比较 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 全部比赛结果输出时树的状态 排序码比较次数 : 0

锦标赛排序构成的胜者树是满的完全二叉树, 其深度为 log2n , 其中 n 为待排序元素个数。 除第一次选择具有最小排序码的对象需要进行 n-1 次排序码比较外, 重构胜者树选择具有次小、再次小排序码对象所需的排序码比较次数均为 O(log2n)。总排序码比较次数为O(nlog2n)。 对象的移动次数不超过排序码的比较次数，所以锦标赛排序总时间复杂度为O(nlog2n)。

这种排序方法虽然减少了许多排序时间, 但是使用了较多的附加存储。 如果有 n 个对象，必须使用至少 2n-1 个结点来存放胜者树。最多需要找到满足 2k-1 < n  2k 的k，使用 2*2k-1 个结点。 每个结点包括排序码、结点序号和比较标志三种信息。 锦标赛排序是一个稳定的排序方法。

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

建立初始的最大堆 21 i i 21 1 1 2 2 25 49 25 49 3 4 5 3 4 5 25* 16 08 25* 16 08 21 25 49 25* 16 08 21 25 49 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 21 25 49 25* 16 08 49 25 21 25* 16 08 i = 1 时的局部调整 i = 0 时的局部调整 形成最大堆

最大堆的向下调整算法 template <class Type> void MaxHeap<Type> :: FilterDown ( const int i, const int EndOfHeap ) { int current = i; int child = 2*i+1; Type temp = heap[i]; while ( child <= EndOfHeap ) { //最后位置 if ( child +1 < EndOfHeap && heap[child] < heap[child+1] ) child = child+1; //选两子女的大者 if ( temp >= heap[child] ) break; //temp排序码大, 不做调整 else {

heap[current] = heap[child]; //大子女上移 current = child; //向下继续调整 child = 2*child+1; } heap[current] = temp; //回放到合适位置 将表转换成堆 for ( int i = ( CurrentSize-2) / 2 ; i >= 0; i-- ) FilterDown ( i, CurrentSize-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 号对象就位

堆排序的算法 template <class Type> void MaxHeap<Type> :: HeapSort ( ) { //对表heap[0]到heap[n-1]进行排序, 使得表中 //各个对象按其排序码非递减有序。 for ( int i = ( CurrentSize-2 ) / 2; i >= 0; i-- ) FilterDown ( i, CurrentSize-1 ); //初始堆 for ( i = CurrentSize-1; i >= 1; i--) { Swap ( heap[0], heap[i] ); //交换 FilterDown ( 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) 归并 归并，是将两个或两个以上的有序表合并成一个新的有序表。 对象序列initList中两个有序表V[l] …V[m]和V[m+1] …V[n]。它们可归并成一个有序表, 存于另一对象序列mergedList的V[l] …V[n] 中。 这种归并方法称为两路归并 (2-way merging)。 设变量 i 和 j 分别是表V[l] …V[m]和V[m+1] …V[n]的当前检测指针。变量 k 是存放指针。

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

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

两路归并算法 template <class Type> void dataList<Type> :: merge ( dataList <Type> & mergedList, const int left, const int mid, const int right ) { int i = left, j = mid+1, k = left; while ( i <= mid && j <= right ) //两两比较 if ( Vector[i] <= Vector[j] ) { mergedList.Vector[k] = Vector[i]; i++; k++; } else { mergedList.Vector[k] = Vector[j];

j++; k++; } if ( i <= mid ) for ( int n1 = k, n2 = i; n2 <= mid; n1++, n2++ ) mergedList.Vector[n1] = Vector[n2]; else for ( int n1 = k, n2 = j; n2 <= right; n1++, n2++)

一趟归并排序的情形 设initList.Vector[0]到initList.Vector[n-1]中 n 个对象已经分为一些长度为 len 的归并项, 将这些归并项两两归并, 归并成长度为 2len 的归并项, 结果放到mergedList.Vector中。 如果n不是2len的整数倍, 则一趟归并到最后,可能遇到两种情形： 剩下一个长度为len的归并项和另一个长度不足len的归并项, 可用merge算法将它们归并成一个长度小于 2len 的归并项。 只剩下一个归并项，其长度小于或等于 len, 将它直接抄到MergedList.Vector中。

template <class Type> void datalist<Type> :: MergePass ( dataList<Type> & mergedList, const int len ) { int i = 0; while (i+2*len <= CurrentSize-1) { merge(mergedList, i, i+len-1, i+2*len-1); i += 2 * len; //循环两两归并 } if ( i+len <= CurrentSize-1 ) merge(mergedList, i, i+len-1, CurrentSize-1); else for ( int j = i; j <= CurrentSize-1; j++) mergedList.Vector[j] = Vector[j];

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

(两路)归并排序的主算法 template <class Type> void dataList<Type> :: MergeSort ( ) { //按对象排序码非递减的顺序对表中对象排序 dataList<Type> & tempList ( MaxSize ); int len = 1; while ( len < CurrentSize ) { MergePass ( tempList, len ); len *= 2; tempList.MergePass ( this, len ); len *= 2; } delete [ ] tempList;

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

递归的表归并排序 与快速排序类似，归并排序也可以利用划分为子序列的方法递归实现。 在递归的归并排序方法中，首先要把整个待排序序列划分为两个长度大致相等的部分，分别称之为左子表和右子表。对这些子表分别递归地进行排序，然后再把排好序的两个子表进行归并。 图示：待排序对象序列的排序码为 { 21, 25, 49, 25*,16, 08 }，先是进行子表划分，待到子表中只有一个对象时递归到底。再是实施归并，逐步退出递归调用的过程。

21 25 49 25* 16 08 递 归 21 25 49 25* 16 08 21 25 49 25* 16 08 21 25 49 25* 16 08 21 25 49 25* 16 08 回推 21 25 49 25* 16 08 21 25 49 25* 16 08 21 25 49 25* 16 08

静态链表的两路归并算法 template <class Type> int staticlinkList<Type> :: ListMerge ( const int start1, const int start2 ) { int k = 0, i = start1, j = start2; while ( i && j ) if ( Vector[i].key <= Vector[j].key ) { Vector[k].link = i; k = i; i = Vector[i].link; } else { Vector[k].link = j; k = j;

j = Vector[j].link; } if ( i == 0 ) Vector[k].link = j; else Vector[k].link = i; return Vector[0].link; 递归的归并排序算法 template <class Type> int staticlinkList<Type> :: MergeSort ( const int left, const int right ) { if ( left >= right ) return left;

int mid = ( left + right ) / 2; return ListMerge ( MergeSort ( left, mid ), MegerSort ( mid+1, right ) ); //以中点mid为界, 分别对左半部和右半部进 //行表归并排序 } 链表的归并排序方法的递归深度为O(log2n)，对象排序码的比较次数为O(nlog2n)。 链表的归并排序方法是一种稳定的排序方法。

基数排序 (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, …, 10, 分别用“分配”、“收集”的运算逐趟进行排序，在最后一趟“分配”、“收集” 完成后, 所有对象就按其排序码的值从小到大排好序了。 各队列采用链式队列结构, 分配到同一队列的排序码用链接指针链接起来。每一队列设置两个队列指针： 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] 第二趟收集 530 790 921 101 614 485 215 306 637 738

基数排序的“分配”与“收集”过程 第三趟 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] 第三趟收集 530 790 921 101 614 485 215 306 637 738

链表基数排序 template <class Type> void staticlinkList <Type> :: RadixSort ( const int d, const int radix ) { int rear[radix], front[radix]; for ( int i = 1; i < CurrentSize; i++ ) Vector[i].link = i+1; Vector[n].link = 0; //静态链表初始化 int current = 1; //链表扫描指针 for ( i = d-1; i >= 0; i-- ) { //d趟分配.收集 for ( int j = 0; j < radix; j++ ) front[j] = 0;

while ( current != 0 ) { //逐个对象分配 int k = Vector[current].key[i]; //取当前对象排序码的第 i 位 if ( front[k] == 0) //原链表为空 front[k] = current; //队头链入 else //原链表非空,链尾链入 Vector[rear[k]].link = current; rear[k] = current; //修改链尾指针 current = Vector[current].link; //下一对象 } j = 0; //从0号队列开始收集 while ( front[j] == 0 ) j++; //空队列跳过

Vector[0].link = current = front[j]; //新链头 int last = rear[j]; //新链尾 for ( k = j+1; k < radix; k++) //逐个队列链接 if ( front[k] ) { Vector[last].link = front[k]; last = rear[k]; } Vector[last].link = 0; //链收尾 } //下一趟

若每个排序码有 d 位, 需要重复执行d 趟“分配”与“收集”。每趟对 n 个对象进行“分配”，对radix个队列进行“收集”。总时间复杂度为O ( d ( n+radix ) )。 基数排序是稳定的排序方法。

各种排序方法的比较

外排序 当待排序的对象数目特别多时，在内存中不能一次处理。必须把它们以文件的形式存放于外存，排序时再把它们一部分一部分调入内存进行处理。这样，在排序过程中必须不断地在内存与外存之间传送数据。这种基于外部存储设备（或文件）的排序技术就是外排序。 外排序的基本过程 当对象以文件形式存放于磁盘上的时候, 通常是按物理块存储的。

物理块也叫做页块。每个页块可存放几个对象。操作系统按页块对磁盘信息进行读写。 磁盘通常是指由若干片磁盘组成的磁盘组, 各个盘片安装在同一主轴上高速旋转。各个盘面上半径相同的磁道构成了柱面。各盘面设置一个读写磁头，它们装在同一动臂上，可以径向从一个柱面移到另一个柱面上。 为了访问某一页块, 先寻找柱面: 移动动臂使读写磁头移到指定柱面上: 寻查(seek)。再根据磁道号(盘面号)选择相应读写磁头, 等待指定页块转到读写磁头下: 等待(latency)。 在磁盘组上存取一个页块的时间：

tio＝tseek＋tlatency＋trw 基于磁盘进行的排序多使用归并排序方法。其排序过程主要分为两个阶段： 建立用于外排序的内存缓冲区。根据它们的大小将输入文件划分为若干段, 用某种内排序方法对各段进行排序。经过排序的段叫做初始归并段或初始顺串 (Run)。当它们生成后就被写到外存中去。 仿照归并树模式, 把 ① 生成的初始归并段加以归并, 一趟趟地扩大归并段和减少归并段个数, 直到最后归并成一个大归并段(有序文件)为止。

示例：设有一个包含4500个对象的输入文件。现用一台其内存至多可容纳750个对象的计算机对该文件进行排序。输入文件放在磁盘上,磁盘每个页块可容纳250个对象, 这样全部对象可存储在 4500 / 250＝18 个页块中。输出文件也放在磁盘上, 用以存放归并结果。 由于内存中可用于排序的存储区域能容纳750 个对象, 因此内存中恰好能存3个页块的对象。 在外排序一开始, 把18块对象, 每3块一组, 读入内存。利用某种内排序方法进行内排序, 形成初始归并段, 再写回外存。总共可得到6个初始归并段。然后一趟一趟进行归并排序。

两路归并排序的归并树 初始 归并段 第一趟 归并结果 第二趟 归并结果 第三趟 归并结果 R1 750 R2 750 R3 750 R4 750 R5 750 R6 750 初始 归并段 R12 1500 R34 1500 R56 1500 第一趟 归并结果 R1234 3000 第二趟 归并结果 R123456 4500 第三趟 归并结果

输入缓冲区 1 输出缓冲区 输入缓冲区 2 若把内存区域等份地分为 3 个缓冲区。其中的两个为输入缓冲区, 一个为输出缓冲区, 可以在内存中利用简单 2 路归并函数 merge( ) 实现 2 路归并。 首先, 从参加归并排序的两个输入归并段 R1 和 R2 中分别读入一块, 放在输入缓冲区1 和输入缓冲区2 中。然后在内存中进行 2 路归并，归并结果顺序存放到输出缓冲区中。

tES = m*tIS + d*tIO + S*u*tmg 若总对象个数为 n，磁盘上每个页块可容纳 b 个对象，内存缓冲区可容纳 i 个页块，则每个初始归并段长度为 len = i * b，可生成 m = n / len 个等长的初始归并段。 在做 2 路归并排序时, 第一趟从 m 个初始归并段得到 m/2 个归并段，以后各趟将从 l (l >1) 个归并段得到 l/2 个归并段。总归并趟数等于归并树的高度 log2m。 估计 2 路归并排序时间 tES 的上界为： tES = m*tIS + d*tIO + S*u*tmg

对 4500 个对象进行排序的例子, 各种操作的计算时间如下： 读 18 个输入块, 内部排序6段, 写18个输出块 ＝6 tIS＋36 tIO 成对归并初始归并段 R1～R6 ＝36 tIO＋4500 tmg 归并两个具有 1500 个对象的归并段 R12和 R34 ＝24 tIO＋3000 tmg 最后将 R1234 和 R56 归并成一个归并段 ＝ 36 tIO＋4500 tmg 合计 tES＝6 tIS＋132 tIO＋12000 tmg

由于 tIO=tseek+tlatency+trw, 其中, tseek和tlatency是机械动作，而trw、tIS、tmg是电子线路的动作, 所以tIO远远大于tIS和tmg。想要提高外排序的速度，应着眼于减少 d。 若对相同数目的对象，在同样页块大小的情况下做 3 路归并或做 6 路归并(当然, 内存缓冲区的数目也要变化)，则可做大致比较： 归并路数 k 总读写磁盘次数 d 归并趟数 S 2 132 3 3 108 2 6 72 1

增大归并路数, 可减少归并趟数, 从而减少总读写磁盘次数d。 对 m 个初始归并段, 做 k 路平衡归并, 归并树可用正则 k 叉树 (即只有度为 k 与度为0的结点的 k 叉树) 来表示。 第一趟可将 m 个初始归并段归并为 l = m/k 个归并段，以后每一趟归并将 l 个归并段归并成 l = l / k 个归并段，直到最后形成一个大的归并段为止。树的高度＝ logkm ＝ 归并趟数S。

k路平衡归并 (k-way Balanced merging) 做 k 路平衡归并时, 如果有 m 个初始归并段, 则相应的归并树有 logkm +1 层, 需要归并logkm 趟。下图给出对有 36 个初始归并段的文件做 6 路平衡归并时的归并树。

做内部 k 路归并时, 在 k 个对象中选择最小者，需要顺序比较 k-1 次。每趟归并 u 个对象需要做(u-1) 做内部 k 路归并时, 在 k 个对象中选择最小者，需要顺序比较 k-1 次。每趟归并 u 个对象需要做(u-1)*(k-1)次比较, S 趟归并总共需要的比较次数为: S*(u-1)*(k-1) = logkm * (u-1) * (k-1) = log2m * (u-1) * (k-1) / log2k 在初始归并段个数 m 与对象个数 u 一定时, log2m*(u-1) = const, 而 (k-1) / log2k 在 k 增大时趋于无穷大。因此, 增大归并路数 k, 会使得内部归并的时间增大。

使用“败者树”从 k 个归并段中选最小者, 当 k 较大时 (k  6)，选出排序码最小的对象只需比较 log2k 次。 S*(u-1)*log2k = logkm * (u-1) * log2k = log2m * (u-1) * log2k / log2k = log2m * (u-1) 排序码比较次数与 k 无关, 总的内部归并时间不会随 k 的增大而增大。 下面讨论利用败者树在 k 个输入归并段中选择最小者，实现归并排序的方法。

败者树是一棵正则的完全二叉树。其中 每个叶结点存放各归并段在归并过程中当前参加比较的对象； 每个非叶结点记忆它两个子女结点中对象排序码小的结点(即败者)； 因此，根结点中记忆树中当前对象排序码最小的结点 (最小对象)。 败者树与胜者树的区别在于一个选择了败者(排序码大者), 一个选择了胜者(排序码小者)。 示例：设有 5 个初始归并段, 它们中各对象的排序码分别是：

Run0: {17, 21, ∞} Run1: {05, 44, ∞} Run2: {10, 12, ∞} ls0 1 冠军 (最小对象), 输出段1当前对象 ls1 4 ls2 选中 2 ls3 ls4 3 k0 k1 k2 17 05 10 17 21  05 44  10 12  k3 29 k4 15 29 32  15 56  Run0 Run1 Run2 Run3 Run4

次最小对象 ls0 2 输出段1最小对象， 段1下一对象参选， 调整败者树 ls1 4 ls2 1 ls3 ls4 3 k0 k1 k2 ls2 1 ls3 选中 ls4 3 k0 k1 k2 17 44 10 17 21  05 44  10 12  k3 29 k4 15 29 32  15 56  Run0 Run1 Run2 Run3 Run4

败者树的高度为 log2k，在每次调整, 找下 一个具有最小排序码对象时, 最多做 log2k 次排序码比较。 在内存中应为每一个归并段分配一个输入缓冲区, 其大小应能容纳一个页块的对象, 编号与归并段号一致。每个输入缓冲区应有一个指针, 指示当前参加归并的对象。 在内存中还应设立一个输出缓冲区, 其大小相当于一个页块大小。它也有一个缓冲区指针, 指示当前可存放结果对象的位置。每当一个对象 i 被选出, 就执行OutputRecord(i)操作, 将对象存放到输出缓冲区中。

在实现利用败者树进行多路平衡归并算法时, 把败者树的叶结点和非叶结点分开定义。 败者树叶结点key[ ]有k+1个, key[0]到key[k-1]存放各归并段当前参加归并的对象的排序码，key[k]是辅助工作单元, 在初始建立败者树时使用: 存放一个最小的在各归并段中不可能出现的排序码: -MaxNum。 败者树非叶结点loser[ ]有k个, 其中loser[1]到loser[k-1]存放各次比较的败者的归并段号, loser[0]中是最后胜者所在归并段号。另外还有一个存放各归并段参加归并对象的数组r[k]。

k 路平衡归并排序算法 void kwaymerge ( Element *r ) { r = new Element[k]; //创建对象数组 int *key = new int[k+1]; //创建外结点数组 int *loser = new int[k]; //创建败者树数组 for ( int i = 0; i < k; i++ ) //传送参选排序码 { InputRecord ( r[i] ); key[i] = r[i].key; } for ( i = 0; i < k; i++) loser[i] = k; key[k] = -MaxNum; //初始化 for ( i = k-1; i; i-- ) //调整形成败者树 adjust ( key, loser, k, i );

while ( key[loser[0]] != MaxNum ) { //选冠军 q = loser[0]; //最小对象的段号 OutputRecord ( r[q] ); //输出 InputRecord ( r[q] ); //从该段补入对象 key[q] = r[q].key; adjust ( key, loser, k, q ); //调整 } Output end of run marker; //输出段结束标志 delete [ ] r; delete [ ] key; delete [ ] loser;

自某叶结点key[q]到败者树根结点的调整算法 void adjust ( int key[ ]; int loser[ ]; const int k; const int q ) { //q指示败者树某外结点key[q], 从该结点起到 //根进行比较, 将最小 key 对象所在归并段的 //段号记入loser[0]。k是外结点key[ ]个数。 for ( int t = (k+q) / 2; t > 0; t /= 2 ) // t是q双亲 if ( key[loser[t]] < key[q]) { //败者记入loser[t], 胜者记入q int temp = q; q = loser[t]; loser[t] = temp; } //q与loser[t]交换 loser[0] = q; }

每选出一个当前排序码最小的对象, 就需要在将它送入输出缓冲区之后, 从相应归并段的输入缓冲区中取出下一个参加归并的对象,替换已经取走的最小对象, 再从叶结点到根结点, 沿某一特定路径进行调整, 将下一个排序码最小对象的归并段号调整到loser[0]中。 段结束标志MaxNum升入loser[0], 排序完成。 归并路数 k 不是越大越好。归并路数 k 增大, 相应需增加输入缓冲区个数。如果可供使用的内存空间不变, 势必要减少每个输入缓冲区的容量, 使内外存交换数据的次数增大。

利用败者树进行5路平衡归并的过程 (1) 初始状态 (2) 加入15, 29, 调整 ls0 ls0 5 5 ls1 ls1 5 5 ls2 4 5 k0 k1 k2 k0 k1 k2 ls4 ls4 5 17 05 10 3 17 05 10 k3 k4 k5 k3 k4 k5 29 15 - 29 15 - (1) 初始状态 (2) 加入15, 29, 调整

利用败者树进行5路平衡归并的过程 (3) 加入10, 05, 调整 (4) 加入17, 调整 ls0 ls0 输出05 5 1 ls1 2 2 k0 k1 k2 k0 k1 k2 ls4 ls4 3 17 05 10 3 17 05 10 k3 k4 k5 k3 k4 k5 29 15 - 29 15 - (3) 加入10, 05, 调整 (4) 加入17, 调整

利用败者树进行5路平衡归并的过程 (5) 输出05后调整 (6) 输出10后调整 ls0 输出10 ls0 输出12 2 2 ls1 ls1 4 4 ls2 ls3 ls2 ls3 1 1 k0 k1 k2 k0 k1 k2 ls4 ls4 3 17 44 10 3 17 44 12 k3 k4 k3 k4 输入44 输入12 29 15 29 15 (5) 输出05后调整 (6) 输出10后调整

利用败者树进行5路平衡归并的过程 (7) 输出12后调整 (8) 输出15后调整 ls0 输出15 ls0 输出17 4 ls1 ls1 1 ls1 ls1 1 1 ls2 ls3 ls2 ls3 2 3 2 k0 k1 k2 k0 k1 k2 ls4 ls4 3 17 44  4 17 44  k3 k4 k3 k4 输入 输入56 29 15 29 56 (7) 输出12后调整 (8) 输出15后调整

利用败者树进行5路平衡归并的过程 (9) 输出17后调整 (10) 输出21后调整 ls0 输出21 ls0 输出29 3 ls1 ls1 3 ls1 ls1 1 1 ls2 ls3 ls2 ls3 3 2 2 k0 k1 k2 k0 k1 k2 ls4 ls4 4 21 44  4  44  k3 k4 k3 k4 输入 输入21 29 56 29 56 (9) 输出17后调整 (10) 输出21后调整

利用败者树进行5路平衡归并的过程 (11) 输出29后调整 (12) 输出32后调整 ls0 输出32 ls0 输出44 3 1 ls1 2 2 k0 k1 k2 k0 k1 k2 ls4 ls4 4  44  3  44  k3 k4 k3 k4 输入32 输入 32 56  56 (11) 输出29后调整 (12) 输出32后调整

利用败者树进行5路平衡归并的过程 (13) 输出44后调整 (14) 输出56后调整 ls0 输出56 ls0 4 4 输出， 结束 2 2 k0 k1 k2 k0 k1 k2 ls4 ls4 3    3    k3 k4 k3 k4 输入 输入  56   (13) 输出44后调整 (14) 输出56后调整

初始归并段的生成 (Run Generation) 为减少读写磁盘次数, 除增加归并路数 k 外, 还可减少初始归并段个数m。在总对象数n 一定时, 要减少m, 必须增大初始归并段长度。 如果规定每个初始归并段等长, 则此长度应根据生成它的内存工作区空间大小而定, 因而m的减少也就受到了限制。 为了突破这个限制, 可采用败者树来生成初始归并段。在使用同样大内存工作区的情况下, 可以生成平均比原来等长情况下大一倍的初始归并段, 从而减少初始归并段个数。

设输入文件FI中各对象的排序码序列为 { 17, 21, 05, 44, 10, 12, 56, 32, 29 }。 选择和置换过程的步骤如下： 从输入文件FI中把 k 个对象读入内存中, 并构造败者树。(内存中存放对象的数组r可容纳的对象个数为 k ) 利用败者树在 r 中选择一个排序码最小的对象r[q], 其排序码存入LastKey作为门槛。以后再选出的排序码比它大的对象归入本归并段, 比它小的归入下一归并段。 将此r[q]对象写到输出文件FO中。(q 是叶结点序号)

若FI未读完, 则从FI读入下一个对象, 置换r[q]及败者树中的key[q]。 调整败者树, 从所有排序码比LastKey大的对象中选择一个排序码最小的对象r[q]作为门槛, 其排序码存入LastKey。 重复③～⑤, 直到在败者树中选不出排序码比LastKey大的对象为止。此时, 在输出文件FO中得到一个初始归并段, 在它最后加一个归并段结束标志。 重复②～⑥, 重新开始选择和置换, 产生新的初始归并段, 直到输入文件FI中所有对象选完为止。

若按在 k 路平衡归并排序中所讲的，每个初始归并段的长度与内存工作区的长度一致, 则上述9个对象可分成3个初始归并段： Run0 { 05, 17, 21 } Run1 { 10, 12, 44 } Run2 { 29, 32, 56 } 但采用上述选择与置换的方法, 可生成2个长度不等的初始归并段: Run0 { 05, 17, 21, 44, 56 } Run1 { 10, 12, 29, 32 }

在利用败者树生成不等长初始归并段的算法和调整败者树并选出最小对象的算法中，用两个条件来决定谁为败者，谁为胜者。 首先比较两个对象所在归并段的段号, 段号小者为胜者，段号大者为败者； 在归并段的段号相同时, 排序码小者为胜者，排序码大者为败者。 比较后把败者对象在对象数组 r 中的序号记入它的双亲结点中, 把胜者对象在对象数组 r 中的序号记入工作单元 s 中, 向更上一层进行比较, 最后的胜者记入 loser[0]中。

ls0 ls0 排序码 段号 1 ls1 ls1 k0 k0 ls2 ls2 2 k1 k2 k1 k2 17 1 17 (1) 初始化 (2) 输入17, 调整 { 17, 21, 05, 44, 10, 12, 56, 32, 29 }

ls0 ls0 选05 ls1 ls1 2 2 k0 k0 ls2 ls2 1 1 05 k1 k2 k1 k2 1 21 17 21 17 05 1 1 1 1 21 (3) 输入21,调整 (4) 输入05, 建败者树 { 17, 21, 05, 44, 10, 12, 56, 32, 29 }

(5) lastKey=05, 置换 (6) lastKey=17, 置换 k0, 选择17 k2, 段号加1, 选择21 k2 44 21 1 17 2 ls1 ls0 ls2 k0 k1 10 选21 选17 (5) lastKey=05, 置换 (6) lastKey=17, 置换 k0, 选择17 k2, 段号加1, 选择21 { 17, 21, 05, 44, 10, 12, 56, 32, 29 }

(7) lastKey=21, 置换 (8) lastKey=44, 置换 k1, 段号加1, 选择44 k0, 选择56 12 2 1 10 44 ls1 ls0 ls2 k2 k1 56 选56 选44 (7) lastKey=21, 置换 (8) lastKey=44, 置换 k1, 段号加1, 选择44 k0, 选择56 { 17, 21, 05, 44, 10, 12, 56, 32, 29 }

(9) lastKey=56, 置换 (10) 输出段结束标志, k0, 段号加1, 本段结束 选择10 ls2 32 12 2 1 10 ls1 ls0 k2 k0 k1 选10 (9) lastKey=56, 置换 (10) 输出段结束标志, k0, 段号加1, 本段结束 选择10 { 17, 21, 05, 44, 10, 12, 56, 32, 29 }

(11) lastKey=10, 置换 (12) lastKey=12, k1 置 k2, 选择12 虚段, 选择29 ls0 29 12 2 32 1 ls1 ls2 k2 k0 k1 3 选29 选12 虚段 (11) lastKey=10, 置换 (12) lastKey=12, k1 置 k2, 选择12 虚段, 选择29 { 17, 21, 05, 44, 10, 12, 56, 32, 29 }

(13) lastKey=29, k2 置 (14) lastKey=32, k0 置 虚段, 选择32 虚段, 本段结束 12 3 2 29 32 1 ls1 ls0 ls2 k2 k0 k1 选32 虚段 (13) lastKey=29, k2 置 (14) lastKey=32, k0 置 虚段, 选择32 虚段, 本段结束 { 17, 21, 05, 44, 10, 12, 56, 32, 29 }

当输入的对象序列已经按排序码大小排好序时，只生成一个初始归并段。 在一般情况下，若输入文件有 n 个对象，生成初始归并段的时间开销是O(nlog2k)，因为每输出一个对象，对败者树进行调整需要时间为O(log2k)。 ls0 段号 超出 1 ls1 k0 ls2 2 32 k1 k2 3 12 29 3 3 (15) 输出段结束标志, 结束

最佳归并树 归并树是描述归并过程的 m 叉树。因为每一次做 m 路归并都需要有 m 个归并段参加, 因此, 归并树是只有度为0和度为 m 的结点的正则 m 叉树。 示例: 设有13个长度不等的初始归并段, 其长度(对象个数)分别为 0, 0, 1, 3, 5, 7, 9, 13, 16, 20, 24, 30, 38 其中长度为 0 的是空归并段。对它们进行 3 路归并时的归并树如图所示。

16 20 1 3 5 24 30 36 38 9 7 9 13 54 83 29 166 此归并树的带权路径长度为 WPL＝(24+30+38+7+9+13)*2+ (16+20+1+3+5)*3 ＝377。

在归并树中 各叶结点代表参加归并的各初始归并段 叶结点上的权值即为该初始归并段中的对象个 数 根结点代表最终生成的归并段 叶结点到根结点的路径长度表示在归并过程中的读对象次数 各非叶结点代表归并出来的新归并段 归并树的带权路径长度 WPL 即为归并过程中的总读对象数。因而，在归并过程中总的读写对象次数为 2*WPL = 754。

不同的归并方案所对应的归并树的带权路径长度各不相同。 为了使得总的读写次数达到最少, 需要改变归并方案, 重新组织归并树。 可将霍夫曼树的思想扩充到 m 叉树的情形。在归并树中, 让对象个数少的初始归并段最先归并, 对象个数多的初始归并段最晚归并, 就可建立总读写次数达到最少的最佳归并树。 例如, 假设有11个初始归并段, 其长度(对象个数)分别为 1, 3, 5, 7, 9, 13, 16, 20, 24, 30, 38 做3路归并。

为使归并树成为一棵正则三叉树, 可能需要补入空归并段。补空归并段的原则为： 若参加归并的初始归并段有 n 个, 做 m 路平衡归并。因归并树是只有度为 0 和度为 m 的结点的正则 m 叉树, 设度为 0 的结点有 n0(= n) 个, 度为 m 的结点有 nm 个, 则有 n0 = (m-1)nm +1 nm = (n0 -1)／(m -1)。 若 (n0-1) % (m-1) = 0, 则说明这 n0 个叶结点正好可以构造 m 叉归并树。 若 (n0 -1) % (m-1) = u  0，则对于这 n0 个叶结点, 其中的 u 个不足以参加 m 路归并。

故除了有 nm 个度为 m 的内结点之外, 还需增加一个内结点。它在归并树中代替了 一个叶结点位置, 被代替的叶结点加上刚才多出的 u 个叶结点, 再加上 m-u-1 个对象个数为零的空归并段, 就可建立归并树。 在示例中, n0 = 11, m = 3, (11-1) % (3-1) = 0, 可以不加空归并段, 直接进行3路归并。 它的带权路径长度 WPL = 38*1+(13+16+20+24+30)*2+(7+9)*3 + (1+3+5)*4 = 328。

1 3 5 7 9 13 16 20 24 30 38 1 3 5 7 9 9 13 16 20 24 30 38 1 3 5 38 13 16 20 49 24 25 30 79 9 7 3 5 1 166 7 9 9 13 16 20 24 25 30 38 1 3 5 7 9 9 13 16 20 24 25 30 38 49

如果做5路归并，让 m = 5，则有 (11-1)／(5-1) = 2 表示有2个度为5的内结点；但是， u = (11-1) % (5-1) =2  0 需要加一个内结点,它在归并树中代替了一 个叶结点的位置, 故一个叶结点参加这个内结点下的归并, 需要增加的空初始归并段数为 m-u-1＝5-2-1 = 2 应当补充 2 个空归并段。则归并树如图所示。

1 3 5 7 9 9 13 16 20 24 30 38 1 3 5 7 9 9 13 16 20 24 30 38 54 166 带权路径长度 WPL＝(1+3+5)*3+(7+9+13+ +16)*2+(20+24+30+38)＝ 229