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

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

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

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

§9.2 插入排序 (Insert Sorting) 基本方法 : 每步将一个待排序的对象, 按其排序码大小, 插入到前面已经排好序的一组对象的适当位置上, 直到对象全部插入为止。 1.直接插入排序 (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++ ) { if ( Vector[i] < Vector[i-1] ) { temp = Vector[i]; for ( j = i; j > 0; j-- ) //从后向前顺序比较 if ( temp < Vector[j-1] ) Vector[j] = Vector[j-1]; else break;

算法分析 Vector[j] = temp; } 排序码比较次数和对象移动次数与对象排序码的初始排列有关。 最好情况下, 排序前对象已按排序码从小到大有序, 每一个对象比较1次, 移动2次对象, 总的排序码比较次数为 n-1, 对象移动次数为2(n-1) 。

最坏情况下, 总排序码比较次数KCN和对象移动次数RMN分别为 平均情况下排序的时间复杂度为 O(n2)。 直接插入排序是一种稳定的排序方法。

2.折半插入排序 (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 较大时, 总排序码比较次数比直接插入排序的最坏情况要好得多, 但比其最好情况要差。 对象移动次数: 折半插入排序的对象移动次数与直接插入排序相同, 依赖于对象的初始排列。

4.希尔排序 (Shell Sort) 希尔排序方法又称为缩小增量排序。 基本思想 : 设待排序对象序列有 n 个对象, 首先取一个整数 gap < n 作为间隔, 将下标相差为gap的倍数对象放在一组。 在组内作插入排序。 然后缩小间隔 gap, 例如取 gap = gap/2，重复上述的组划分和排序工作。直到最后取 gap == 1, 将所有对象放在同一个组中进行排序为止。 例：99,14,28,31,2,7,46,70,62,180,30,82,170,5,9

希尔排序的算法 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 互质为好。 对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数。

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

§9.3 交换排序 (Exchange Sort) 1.起泡排序 (Bubble Sort) 基本方法：两两比较待排序对象的排序码,如果发生逆序，则交换之。直到所有对象都排好序为止。 1.起泡排序 (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为：

起泡排序需要一个额外空间以实现对象值的对换。 起泡排序是一个稳定的排序方法。

2.快速排序 (Quick Sort) 基本思想: 任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准, 按照该对象的排序码大小, 将整个对象序列划分为左右两个子序列：左侧子序列中所有对象的排序码都小于或等于基准对象的排序码 。右侧子序列中所有对象的排序码都大于基准对象的排序码。 基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。 递归地对这两个子序列进行快速排序，直到所有的对象都排在相应位置上为止。

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

快速排序的算法思想 分治法 分 （难） 合并（容易）

初始关键字： 28 19 27 48 56 12 10 25 20 50 完成第一趟后 20 19 27 25 10 12 28 56 48 50 完成第二趟 12 19 10 20 25 27 28 50 48 56 完成第三趟 10 12 19 20 25 27 28 50 48 56

快速排序的算法 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 ); }

int dataList<Type> :: Partition (int s, int t ) { int x, i, j; x=Vector[s]; i=s; j=t; while ( i < j) { while ( ( i < j) && (Vector[j]>=x) j=j-1; if (i<j) a[i]=a[j]; while ( ( i < j) && (Vector[i]<=x) i=i+1; if (i<j) a[j]=a[i]; } Vector[i] =x; return i;

算法分析 从快速排序算法的递归树可知, 快速排序的趟数取决于递归树的高度。 附加存储开销: 取决于最大递归调用层次数，与递归树的高度一致。 理想情况: log2(n+1) 。因此，附加存储开销为 O(log2n)。 最坏的情况: 待排序对象序列已经按其排序码从小到大排好序的情况下, 其递归树成为单支树, 每次划分只得到一个比上一次少一个对象的子序列。必须经过n-1 趟才能把所有对象定位，附加存储开销为 O(n)。

时间开销: 理想情况: O(nlog2n) 最坏的情况: O(n2) 待排序对象把所有对象定位, 而且第 i 趟需要经过 n-i 次排序码比较才能找到第 i 个对象的安放位置，总的排序码比较次数将达到 快速排序是一种不稳定的排序方法。 对于 n 较大的平均情况而言, 快速排序是“快速”的, 但是当 n 很小时, 这种排序方法往往比其它简单排序方法还要慢。

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

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] ); }

3.堆排序 (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 ); //重建最大堆 }

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

§9.4 归并排序 (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 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中。

1.迭代的归并排序算法 基本思想: 假设初始对象序列有 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; }

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