数据结构与算法分析第九章排序

1、Chapter 9Sorting第九章 排序排序定义排序定义将一个数据元素（或记录）的任意序列，将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫重新排列成一个按关键字有序的序列叫排序分类排序分类按待排序记录所在位置按待排序记录所在位置内部排序：待排序记录存放在内存内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序外部排序：排序过程中需对外存进行访问的排序按排序依据原则按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、

2、堆排序选择排序：简单选择排序、堆排序归并排序：归并排序：2-路归并排序路归并排序基数排序基数排序按排序所需工作量按排序所需工作量简单的排序方法：简单的排序方法：T(n)=O(n)先进的排序方法：先进的排序方法：T(n)=O(nlogn)基数排序：基数排序：T(n)=O(d.n) 排序基本操作排序基本操作 比较两个关键字大小比较两个关键字大小 将记录从一个位置移动到另一个将记录从一个位置移动到另一个位置位置排序方法插入排序选择排序交换排序归并排序直接插入排序折半插入排序简单选择排序堆排序起泡排序快速排序 插入排序 直接插入、折半插入1、直接插入排序:基本思想：从数组的第2号元素开始，顺序从数组中

3、取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。 插入排序 直接插入、折半插入该算法适合于n 较小的情况，时间复杂度为O(n2).1、直接插入排序:基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上待排元素序列：待排元素序列：53 27 36 15 69 42第一次排序：第一次排序： 27 53 36 15 69 42第二次排序：第二次排序： 27 36 53 15 69 42第三次排序：第三次排序： 15 27 36 53 69 42第四次排序：第四次排序： 15 27 36 53 69 42第五次排序：第五次排序： 15 2

4、7 36 42 53 69 直接插入排序示例直接插入排序示例对于有n个数据元素的待排序列，插入操作要进行n-1次template void InsertionSort ( datalist & list ) /按关键码按关键码 Key 非递减顺序对表进行排序非递减顺序对表进行排序 for ( int i = 1; i list.CurrentSize; i+ ) Insert ( list, i );template viod Insert ( datalist & list, int i ) Element temp = list.Vectori; int j = i; /从

5、后向前顺序比较从后向前顺序比较 while ( j 0 & temp.getKey ( ) list.Vectorj-1.getKey ( ) ) list.Vectorj = list.Vectorj-1; j-; list.Vectorj = temp; 111122142221nininnniRMNnnniKCN/)()( ,/)(22算法评价时间复杂度若待排序记录按关键字从小到大排列(正序) 关键字比较次数：112nni 记录移动次数：) 1( 222nni若待排序记录按关键字从大到小排列(逆序) 关键字比较次数：2) 1)(2(2nnini 记录移动次数：2) 1)(4()

6、1(2nnini若待排序记录是随机的，取平均值 关键字比较次数：42n 记录移动次数：42n空间复杂度：S(n)=O(1) 时间复杂度： T(n)=O(n)2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置 。待排序元素越多，改进效果越明显。折半插入排序的条件： 在有序序列中插入一个关键字。2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。例：有6个记录，前5 个已排序的基础上，对第6个记录排序。 15 27 36 53 69 42 low mid high 15 27 3

7、6 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42 53 69 (high36 )( 4253 )算法评价:时间复杂度：T(n)=O(n)空间复杂度：S(n)=O(1)template void BinaryInsertSort ( datalist & list ) for ( int i = 1; i list.CurrentSize; i+) BinaryInsert ( list, i );template void BinaryInsert ( datalist & list, int i )

8、int left = 0, Right = i-1; Element temp = list.Vectori; while ( left = Right ) int middle = ( left + Right )/2; if ( temp.getKey ( ) = left; k- ) list.Vectork+1 = list.Vectork; list.Vectorleft = temp;nnnnnkkkikkkiikikikkiikiikikikijjkkkknik221111111111112121222222112log1log)12(222)12(2)221(222)22()2

9、22()2221(44332211log13210 希尔排序希尔排序(缩小增量法缩小增量法)排序过程：排序过程： 先取一个正整数先取一个正整数d1n， 把所有相把所有相隔隔d1的记录放一组，组内进行直接的记录放一组，组内进行直接插入排序；然后取插入排序；然后取d2d1，重复上，重复上述分组和排序操作；直至述分组和排序操作；直至di=1，即，即所有记录放进一个组中排序为止所有记录放进一个组中排序为止取d3=1三趟分组：13 27 48 55 4 49 38 65 97 76三趟排序：4 13 27 38 48 49 55 65 76 97例 初始：49 38 65 97 76 13 27 48

10、55 4一趟排序：13 27 48 55 4 49 38 65 97 76二趟排序：13 4 48 38 27 49 55 65 97 76取d1=5一趟分组：49 38 65 97 76 13 27 48 55 4取d2=3二趟分组：13 27 48 55 4 49 38 65 97 76希尔排序特点子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列希尔排序可提高排序速度，因为分组后n值减小，n更小，而T(n)=O(n),所以T(n)从总体上看是减小了关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序增量序列取法无除1以外的公因子最后一个增

11、量值必须为1template void Shellsort ( datalist & list ) int gap = list.CurrentSize / 2; / gap 是子序列间隔是子序列间隔 while ( gap ) /循环循环,直到直到gap为零为零 ShellInsert ( list, gap ); /一趟直接插入排序一趟直接插入排序gep = gep = 2 ? 1 : ( int ) ( gap/2.2 ); /修改修改 template voidshellInsert ( datalist & list; const int gep ) /一趟希尔排序,

12、按间隔gap划分子序列 for ( int i = gap; i list.CurrentSize; i+) Element temp = list.Vectori;int j = i;while ( j = gap & temp.getKey ( ) list.Vectorj-gap.getKey ( ) ) list.Vectorj = list.Vectorj-gap; j -= gap; list.Vectorj = temp; 交 换 排 序交换排序的特点在于交换。有冒泡和快速排序两种。 1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。从左端开始比较。第一趟：第1个与第2个

13、比较，大则交换；第2个与第3个比较， 大则交换，关键字最大的记录交换到最后一个位置上；第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换 到第n-1个位置上； 依次类推，则完成排序。正序：时间复杂度为O(n) 逆序：时间复杂度为O(n2) 适合于数据较少的情况。 排序n个记录的文件最多需要n-1趟冒泡排序。第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始关键字思 想 ： 小 的浮 起 ， 大 的沉底。4936416511783665364156364165413641561178363641491156492525251149495611111125252

14、525算法评价:时间复杂度最好情况（正序） 比较次数：n-1 移动次数：0最坏情况（逆序） 比较次数：)(21)(211nninni 移动次数：)(23)(321nninni空间复杂度：S(n)=O(1)T(n)=O(n) 11111233121nininninRMNnninKCN)()()()(2、快速排序 (对冒泡排序的改进）思想：通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。关键字通常取第一个记录的值为基准值。做法：附设两个指针low和high ，初值分别指向第一个记录和最后一个记录，设关键字为 key ，首先从 hi

15、gh所指位置起向前搜索，找到第一个小于基准值的记录与基准记录交换，然后从low 所指位置起向后搜索，找到第一个大于基准值的记录与基准记录交换，重复这两步直至low=high为止。时间复杂度：O(nlog2n) 快速排序过程示意图：有序序列 6 18 23 52 67key初始序列 23 52 6 67 18lowhigh一次交换 18 52 6 67 23 lowhigh二次交换 18 23 6 67 52high 三次交换 18 6 23 67 52/ 完成一趟排序后分别进行快速排序lowhigh算法评价时间复杂度最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)最坏情况（每次

16、总是选到最小或最大元素作枢轴）T(n)=O(n)空间复杂度：需栈空间以实现递归最坏情况：S(n)=O(n)一般情况：S(n)=O(logn)T(n)=O(n) QuickSort ( List ) if ( List的长度大于1) 将序列List划分为两个子序列 LeftList 和 Right List; QuickSort ( LeftList );QuickSort ( RightList ); 将两个子序列 LeftList 和 RightList 合并为一个序列List; template void QuickSort ( datalist &list, const int

17、left, const int right ) /在待排序区间在待排序区间 left right 中递归地进行快速排序中递归地进行快速排序 if ( left right) int pivotpos = Partition ( list, left, right ); /划分划分 QuickSort ( list, left, pivotpos-1); /在左子区间递归进行快速排序在左子区间递归进行快速排序 QuickSort ( list, pivotpos+1, right ); /在左子区间递归进行快速排序在左子区间递归进行快速排序 template int Partition ( da

18、talist &list, const int low, const int high ) int pivotpos = low; /基准位置 Element pivot = list.Vectorlow; for ( int i = low+1; i = high; i+ ) if ( list.Vectori.getKey ( ) pivot.getKey( ) & +pivotpos != i ) Swap ( list.Vectorpivotpos, list.Vectori ); /小于基准对象的交换到区间的左侧去 Swap ( list.Vectorlow, lis

19、t.Vectorpivotpos ); return pivotpos; 2125*25490816。2121211nnninni)()(用第一个对象作为基准对象 用居中关键码对象作为基准对象 1 1template void SelectSort ( datalist & list ) for ( int i = 0; i list.CurrentSize- -1; i+ ) SelectExchange ( list, i );template void SelectExchange ( datalist & list, const int i ) int k = i; f

20、or ( int j = i+1; j list.CurrentSize; j+) if ( list.Vectorj.getKey ( ) list.Vectork.getKey ( ) ) k = j; /当前具最小关键码的对象 if ( k != i ) /对换到第 i 个位置 Swap ( list.Vectori, list.Vectork ); 20211ninninKCN)()( 形成初始胜者树（最小关键码上升到根）输出冠军并调整胜者树后树的状态输出亚军并调整胜者树后树的状态输出第三名并调整胜者树后树的状态输出第四名并调整胜者树后树的状态全部比赛结果输出时树的状态template

21、 class DataNode public: Type data; /数据值数据值 int index; /结点在满二叉树中顺序号结点在满二叉树中顺序号 int active; /参选标志：参选标志：=1, 参选参选, =0, 不参选不参选template void TournamentSort ( Type a , int n ) DataNode *tree; DataNode item; int bottomRowSize = PowerOfTwo ( n ); /乘幂值 int TreeSize = 2*bottomRowSize-1; /总结点个数 int loadindex =

22、bottomRowSize-1; /内结点个数 tree = new DataNodeTreeSize; int j = 0; /从 a 向胜者树外结点复制数据 for ( int i = loadindex; i TreeSize; i+) treei.index = i; if ( j n ) treei.active = 1; treei.data = aj+; else treei.active = 0; i = loadindex; /进行初始比较选择最小的项 while ( i ) j = i; while ( j 2*i ) if ( !treej+1.active| /胜者送入

23、双亲 treej.data = treej+1.data ) tree(j-1)/2 = treej; else tree(j-1)/2 = treej+1; j += 2; i = (i-1)/2; / i 退到双亲, 直到 i=0为止 for ( i = 0; i n-1; i+) /处理其它n-1个数据 ai = tree0.data; /送出最小数据 treetree0.index.active = 0; /失去参选资格 UpdateTree ( tree, tree0.index ); /调整调整 an-1 = tree0.data; template void UpdateTree

24、 ( DataNode *tree, int i ) if ( i % 2 = 0 ) tree(i-1)/2 = treei-1; /i偶数偶数, 对手左结点对手左结点 else tree(i-1)/2 = treei+1; /i奇数奇数, 对手右结点对手右结点 i = (i-1) / 2; /向上调整向上调整 while ( i ) /直到 i=0 if ( i %2 = 0) j = i-1; else j = i+1; if ( !treei.active | !treej.active ) if ( treei.active ) tree(i-1)/2 = treei; /i可参选,

25、 i上 else tree(i-1)/2 = treej; /否则, j上 else/两方都可参选 if ( treei.data treej.data ) tree(i-1)/2 = treei; /关键码小者上 else tree(i-1)/2 = treej; i = (i-1) / 2; / i上升到双亲 堆排序 (Heap Sort)利用堆及其运算，可以很容易地实现选择排序的思路。堆排序分为两个步骤：第一步，根据初始输入数据，利用堆的调整算法 FilterDown( ) 形成初始堆，第二步，通过一系列的对象交换和重新调整堆进行排序。堆排序堆排序堆的定义：堆的定义：n个元素的序列个元素

26、的序列(k1,k2,kn)，当且仅当满足下列，当且仅当满足下列关系时，称之为堆关系时，称之为堆或(i=1,2,.n/2)kik2ikik2i+1kik2ikik2i+1例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值堆排序：堆排序： 将无序序列建成一个堆，得到关键字将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的小（大）值后，使剩余的n

27、-1个元素重个元素重又建成一个堆，则可得到又建成一个堆，则可得到n个元素的次个元素的次小值；重复执行，得到一个有序序列，小值；重复执行，得到一个有序序列，这个过程叫这个过程叫堆排序需解决的两个问题：堆排序需解决的两个问题：如何由一个无序序列建成一个堆如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆剩余元素，使之成为一个新的堆？第二个问题解决方法第二个问题解决方法筛选筛选方法方法： 输出堆顶元素之后，以堆中最后一输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左个元素替代之；然后将根结点值与左、右子树的根结点值进行比较

28、，并与、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为个从堆顶至叶子的调整过程为“筛选筛选”例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出：13 27 384965502738769713输出：13 27 387665502738499713输出：13 27

29、 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 509765762738495013输出：13 27 38 49 50 657665972738495013输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输出：13 27 38 49 50 65 76 97第一个问题解决方法方法： 从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最 后

30、一个非终端结点）起，至第一个元素止，进行反复筛选例 含8个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097template void MaxHeap :FilterDown ( const int i, const int EndOfHeap ) int current = i; int child = 2*i+1; Type temp = heapi; while ( child = EndOfHeap ) if (

31、child +1 EndOfHeap & heapchild.getKey( ) = heapchild.getKey( ) ) break; else heapcurrent = heapchild; current = child; child = 2*child+1; heapcurrent = temp;for ( int i = ( CurrentSize-2)/2 ; i = 0; i- ) FilterDown ( i, CurrentSize-1 );012345025431012345025431012345025431012345025431012345025431

32、template void MaxHeap : HeapSort ( ) /对表对表heap0到到heapn- -1进行排序进行排序, 使得表中各使得表中各/个对象按其关键码非递减有序。个对象按其关键码非递减有序。 for ( int i = ( CurrentSize-2 ) / 2; i = 0; i- ) FilterDown ( i, CurrentSize-1 ); /初始堆初始堆 for ( i = CurrentSize-1; i = 1; i-) Swap ( heap0, heapi ); /交换交换 FilterDown ( 0, i-1 ); /重建最大堆重建最大堆 20

33、22kiiik1 1njnjjikkjkjjjkkjjkkii4 411111111202222222122)( 归并排序归并排序归并将两个或两个以上的有序表组合成一个新的有序表，叫2-路归并排序排序过程设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1两两合并，得到n/2个长度为2或1的有序子序列再两两合并，如此重复，直至得到一个长度为n的有序序列为止例初始关键字： 49 38 65 97 76 13 27一趟归并后： 38 49 65 97 13 76 27二趟归并后： 38 49 65 97 13 27 76三趟归并后： 13 27 38 49 65 76 97算法评价

34、时间复杂度：T(n)=O(nlogn)空间复杂度：S(n)=O(n)template void merge ( datalist & initList, datalist & mergedList, const int l, const int m, const int n ) int i = 0, j = m+1, k = 0; while ( i = m & j = n ) /两两比较两两比较 if ( initList.Vectori.getKey ( ) = initList.Vectorj.getKey ( ) ) mergedList.Vectork = i

35、nitList.Vectori; i+; k+; else mergedList.Vectork = initList.Vectorj; j+; k+; if ( i = m ) for ( int n1 = k, n2 = i; n1 = n & n2 = m; n1+, n2+ ) mergedList.Vectorn1 = initList.Vectorn2; else for ( int n1 = k, n2 = j; n1 = n & n2 = n; n1+, n2+) mergedList.Vectorn1 = initList.Vectorn2;template

36、void MergePass ( datalist & initList, datalist & mergedList, const int len ) int i =0; while ( i+2*len = initList.CurrentSize-1 ) merge ( initList, mergedList, i, i+len-1, i+2*len-1); i += 2 * len; if ( i+len = initList.CurrentSize-1 ) merge ( initList, mergedList, i, i+len-1, initList.Curre

37、ntSize-1 ); else for ( int j=i; j = initList.CurrentSize-1; j+ ) mergedList.Vectorj = initList.Vectorj; template void MergeSort ( datalist & list ) /按对象关键码非递减的顺序对表按对象关键码非递减的顺序对表list中对象排序中对象排序 datalist & tempList ( list.MaxSize ); int len = 1; while ( len list.CurrentSize ) MergePass ( list,

38、tempList, len ); len *= 2;MergePass ( tempList, list, len ); len *= 2; delete tempList; 基数排序基数排序 （多关键字排序）（多关键字排序）例 对52张扑克牌按以下次序排序：23A23A23A23A两个关键字：花色（ ） 面值（23A）并且“花色”地位高于“面值”多关键字排序方法 最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后

39、将所有子序列依次连接在一起成为一个有序序列最低位优先法最低位优先法(LSD)：从最低位关键字：从最低位关键字kd起进起进行排序，然后再对高一位的关键字排序，行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字依次重复，直至对最高位关键字k1排序排序后，便成为一个有序序列后，便成为一个有序序列MSD与与LSD不同特点不同特点按按MSD排序，必须将序列逐层分割成排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排若干子序列，然后对各子序列分别排序序按按LSD排序，不必分成子序列，对每个排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且关键字都是整个序列参加排序；并且可不

40、通过关键字比较，而通过若干次可不通过关键字比较，而通过若干次分配与收集实现排序分配与收集实现排序链式基数排序链式基数排序基数排序：借助基数排序：借助“分配分配”和和“收集收集”对单逻辑关键字进行排对单逻辑关键字进行排序的一种方法序的一种方法链式基数排序：用链表作存储链式基数排序：用链表作存储结构的基数排序结构的基数排序链式基数排序步骤链式基数排序步骤设置设置10个队列，个队列，fi和和ei分别为第分别为第i个队列的个队列的头指针和尾指针头指针和尾指针第一趟分配对最低位关键字（个位）进行，第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至改变记录的指针值，将链表中记录分配

41、至10个链队列中，每个队列记录的关键字的个链队列中，每个队列记录的关键字的个位相同个位相同第一趟收集是改变所有非空队列的队尾记录第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队的指针域，令其指向下一个非空队列的队头记录，重新将头记录，重新将10个队列链成一个链表个队列链成一个链表重复上述两步，进行第二趟、第三趟分配和重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到收集，分别对十位、百位进行，最后得到一个有序序列一个有序序列例初始状态：2781090639305891845052690080831095892692780639300831845

42、05008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集：008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f

43、2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集：算法评价时间复杂度：分配：T(n)=O(n)收集：T(n)=O(rd) T(n)=O(d(n+rd)其中：n记录数 d关键字数 rd关键字取值范围 空间复杂度：S(n)=2rd个队列指针+n个指针域空间template void RadixSort ( staticlinklist &list, const int d, const int radix ) int rearradix, frontradix; for ( int i = 1;

44、i = 0; i- ) /做做 d 趟分配趟分配.收集收集 for ( int j = 0; j radix; j+ ) frontj = 0; while ( current != 0 ) /逐个对象分配逐个对象分配 int k = list.Vectorcurrent.getKey(keyi); /取当前对象关键码的第 i 位 if ( frontk = 0) /原链表为空,对象链入 frontk = current; else /原链表非空,链尾链入 list.Vectorreark.setLink (current); reark = current; /修改链尾指针 current

45、= list.Vectorcurrent.getLink ( ); j = 0; /从0号队列开始收集 while ( frontj = 0 ) j+; /空队列跳过 current = frontj; list.Vector0.setLink (current); int last = rearj; for ( k = j+1; k radix; k+) /逐个队列链接 if ( frontk ) list.Vectorlast.setLink(frontk); last = reark; list.Vectorlast.setLink(0); 内部排序方法的选择各种排序方法各有优缺点，故在

46、不同情况下可作不同的选择。通常需考虑的因素有：待排序的记录个数；记录本身的大小；记录的键值分布情况等。 若待排序的记录个数n较小时，可采用简单排序方法。 若n 较大时，应采用快速排序或堆排序。 若待排序的记录已基本有序，可采用起泡排序。 各种内排序方法的比较和选择 一 各种内排序方法的比较1从时间复杂度比较从平均时间复杂度来考虑，直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法，时间复杂度都为O(n2)，而快速排序、堆排序、二路归并排序的时间复杂度都为O(nlog2n)，希尔排序的复杂度介于这两者之间。若从最好的时间复杂度考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它

47、的最好情形同平均情形相同。若从最坏的时间复杂度考虑，则快速排序的为O(n2)，直接插入排序、冒泡排序、希尔排序同平均情形相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情形对直接选择排序、堆排序和归并排序影响不大。2从空间复杂度比较归并排序的空间复杂度最大，为O(n)，快速排序的空间复杂度为O(log2n)，其它排序的空间复杂度为O（1）。 3.从稳定性比较直接插入排序、冒泡排序、归并排序是稳定的排序方法，而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序方法。4从算法简单性比较直接插入排序、冒泡排序、直接选择排序都是简单的排序方法，算法简单，易于理解，而希尔排序、快速排序、堆排序

48、、归并排序都是改进型的排序方法，算法比简单排序要复杂得多，也难于理解。 二 各种内排序方法的选择1从时间复杂度选择对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。2从空间复杂度选择尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O（n）二路归并排序的排序方法。 3一般选择规则（1） 当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。（2)当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。（3）当待排序元素的个数n大，排序码分

49、布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。（4)当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。 (5)当待排序元素的个数n小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。 比比较较次次数数 移移动动次次数数附附加加存存储储排排 序序 方方 法法最最好好最最差差最最好好最最差差稳稳定定 性性最最好好最最差差直直接接插插入入排排序序nn2 0n2 1折折半半插插入入排排序序n log2n 0n2 1起起泡泡排排序序nn2 0n2 1快快速速排排序序n

50、log2nn2n log2nn2 log2nn2简简单单选选择择排排序序n2 0n 1锦锦标标赛赛排排序序n log2nn log2n n堆堆排排序序n log2nn log2n 1归归并并排排序序n log2nn log2n n内部排序方法的比较内部排序方法的比较当当n很大时用线性链表代替数组来排序很大时用线性链表代替数组来排序*为未解决的数学问题比较排序算法的下界比较排序算法的下界n个元素排成一个序列，共有个元素排成一个序列，共有n!种不同的排法。种不同的排法。从一个序列出发排序，总共就会有从一个序列出发排序，总共就会有n!种不同的变换种不同的变换次序。次序。每一次比较交换可以得到两种不同

51、的次序，可以将每一次比较交换可以得到两种不同的次序，可以将不同的比较排成判定二叉树。不同的比较排成判定二叉树。每个叶子都是得到的序列，共n!个每个二度结点都是一次比较交换，最小深度log(n!)比较排序算法的下界比较排序算法的下界log(n!) log(n/2)n/2)log(n!)log(nn) (n/2)log(n/2)log(n!)nlogn (n/2)log(n/2)=(n/2)(logn-1) =(n/2)logn-n/2=O(nlogn) log(n!)=O(nlogn)外排序的基本过程tiotseektlatencytrwR1 750 R2 750 R3 750 R4 750 R

52、5 750 R6 750初始归并段R12 1500 R34 1500 R56 1500R1234 3000R123456 4500第一趟归并结果 第二趟归并结果 第三趟归并结果 输入缓冲区 2输入缓冲区 1输出缓冲区tES = m*tIS + d*tIO + S*u*tmg 2 132 33 108 2 6 72 1k路平衡归并路平衡归并 (k-way Balanced merging) 选中输出段1最小对象，段1下一对象参选，调整败者树选中 void kwaymerge ( Element *r ) r = new Elementk; /创建对象数组创建对象数组 int *key = new

53、 intk+1; /创建外结点数组创建外结点数组 int *loser = new intk; /创建败者树数组创建败者树数组 for ( int i = 0; i k; i+ ) /传送参选关键码传送参选关键码 InputRecord ( ri ); keyi = ri.key; for ( i = 0; i 0; t /= 2 ) / t是是q的双亲的双亲 if ( keylosert keyq) /败者记入败者记入losert, 胜者记入胜者记入q int temp = q; q = losert; losert = temp; /q与与losert交换交换 loser0 = q; 以后

54、每选出一个当前关键码最小的对象，就需要以后每选出一个当前关键码最小的对象，就需要在将它送入输出缓冲区之后，从相应归并段的在将它送入输出缓冲区之后，从相应归并段的输入缓冲区中取出下一个参加归并的对象，替输入缓冲区中取出下一个参加归并的对象，替换已经取走的最小对象，再从叶结点到根结点换已经取走的最小对象，再从叶结点到根结点，沿某一特定路径进行调整，将下一个关键码，沿某一特定路径进行调整，将下一个关键码最小对象的归并段号调整到最小对象的归并段号调整到loser0中。中。最后，段结束标志最后，段结束标志MaxNum升入升入loser0，排序，排序完成，输出一个段结束标志。完成，输出一个段结束标志。归并

55、路数归并路数 k 的选择不是越大越好。归并路数的选择不是越大越好。归并路数 k增增大时，相应需增加输入缓冲区个数。如果可供大时，相应需增加输入缓冲区个数。如果可供使用的内存空间不变，势必要减少每个输入缓使用的内存空间不变，势必要减少每个输入缓冲区的容量，使内外存交换数据的次数增大。冲区的容量，使内外存交换数据的次数增大。(1) 初始状态 (2) 加入15, 29, 调整29151705101005172915317405210-1510205170315-2941(3) 加入10, 05, 调整 (4) 加入17, 调整输出输出(5) 输出05后调整 (6) 输出10后调整输入输入输出12输出

56、输出1输入输入输入输入输出17输出输出1输入输入(7) 输出12后调整 (8) 输出15后调整输入输入输出29输出21输入输入(9) 输出17后调整 (10) 输出21后调整 输入输入3输出44输出32输入输入(11) 输出29后调整 (12) 输出32后调整输出输出输出56输入输入输入输入(13) 输出44后调整 (14) 输出56后调整初始归并段的生成初始归并段的生成 (Run Generation) 1. 2. 3. 4. 6. 输输 入入 文文 件件 FI 内内存存数数组组 r 输输出出文文件件 FO1721 05 44 10 12 56 32 2944 10 12 56 32 29

57、17 21 0510 12 56 32 29 17 21 44 0512 56 32 29 10 21 44 05 1756 32 29 10 12 44 05 17 2132 29 10 12 56 05 17 21 4429 10 12 32 05 17 21 44 5629 10 12 32 05 17 21 44 56 29 10 12 32 29 12 32 10 29 32 10 12 32 10 12 29 10 12 29 32 10 12 29 32 void generateRuns ( Element *r ) r = new Elementk; int *key = n

58、ew intk; /参选对象关键码数组参选对象关键码数组 int *rn = new intk; /参选对象段号数组参选对象段号数组 int *loser = new intk; /败者树败者树 for ( int i = 0; i 0; i- ) /输入首批对象输入首批对象 if ( end of input ) rni = 2; /中途结束中途结束 else InputRecord ( ri ); /从缓冲区输入从缓冲区输入 keyi = ri.key; rni = 1; SelectMin ( key, rn, loser, k, i, rq ); /调整调整 q = loser0; /

59、 q是最小对象在是最小对象在 r 中的序号中的序号 int rq = 1; / rq的归并段段号的归并段段号 int rc = 1; /当前归并段段号当前归并段段号 int rmax = 1; /下次将要产生的归并段段号下次将要产生的归并段段号 int LastKey = MaxNum; /门槛门槛while (1) /生成一个初始归并段生成一个初始归并段 if ( rq != rc ) /当前最小对象归并段大当前最小对象归并段大 Output end of run marker; /加段结束符加段结束符 if ( rq rmax ) return; /处理结束处理结束 else rc = r

60、q; /否则置当前段号等于否则置当前段号等于rq OutputRecord ( rq ); / rc=rq，输出 LastKey = Keyq; /置新的门槛 if ( end of input ) rnq = rmax + 1; /虚设对象 else /输入文件未读完 InputRecord ( rq ); /读入到刚才位置 keyi = ri.key; if ( keyq 0; t /= 2 ) if ( rnlosert rq | rnlosert = rq & keylosert keyq ) /先比较段号再比较关键码先比较段号再比较关键码, 小者为胜者小者为胜者 int temp = q; q = losert; losert = temp; /败者记入败者记入losert, 胜者记入胜者记入q rq = rnq; loser0 = q; /最后的胜者