当前位置： >>
第 10 章 排序
数据结构第十章 内部排序数据结构第十章 内部排序教学内容1、插入排序（直接插入排序、折半插入排序、 、插入排序（直接插入排序、折半插入排序、 希尔排序）； 希尔排序）； 2、交换排序（起泡排序、快速排序）； 、交换排序（起泡排序、快速排序）； 3、选择排序（直接选择排序、堆排序）； 、选择排序（直接选择排序、堆排序）； 4、归并排序； 、归并排序； 5、基数排序； 、基数排序；数据结构第十章 内部排序10.1 概述 排序：将数据元素的一个任意序列，重新排列成一个按关键 排序：将数据元素的一个任意序列，重新排列成一个按关键 字有序的序列 的序列。 字有序的序列。 R1, R2, R3, R4, R5, R6, R7, R8 例：将关键字序列：52, 49, 80, 36, 14, 58, 61, 23 将关键字序列： K1, K2, K3, K4, K5, K6, K7, K8 Kp1 ≤Kp2 ≤Kp3 ≤Kp4 ≤Kp5 ≤ Kp6 ≤Kp7 ≤Kp8 调整为：14, 23, 36, 49, 调整为： Rp1, Rp2, Rp3, Rp4, 52, 58, Rp5, Rp6, 61 , 80 Rp7, Rp8一般情况下， 个记录的序列为{ 一般情况下，假设含 n 个记录的序列为 R1, R2, …, Rn }， ， 其相应的关键字序列为 { K1, K2, …, Kn } 这些关键字相互之间可以进行比较， 这些关键字相互之间可以进行比较，即在它们之间存在着这 Kp1≤Kp2≤…≤Kpn 样一个关系 ： 按此固有关系将上式记录序列重新排列为{ 按此固有关系将上式记录序列重新排列为 Rp1, Rp2, …, Rpn } 排序。 的操作称作排序 的操作称作排序。数据结构第十章 内部排序若 Ki 为记录 Ri 的主关键字，则排序结果惟一。 关键字，则排序结果惟一 结果惟一。 关键字，则排序结果可以不惟一 结果可以不惟一（ 若 Ki 为记录 Ri 的次关键字，则排序结果可以不惟一（因为 会有相同的关键字）。 会有相同的关键字）。 设 Ki = Kj (1≤i≤n, 1≤j≤n, i≠j )，且在排序前的序列中 Ri ， ）。若在排序后的序列中 领先于 Rj（即 i & j ）。若在排序后的序列中 Ri 仍领先于 Rj，则 称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳 排序方法是稳定的； 称所用的排序方法是稳定的 反之，则称所用的排序方法是不稳 定的。 定的。 36, 例：设排序前的关键字序列为：52, 49, 80, 36, 14, 58, 36 23 设排序前的关键字序列为： 若排序后的关键字序列为： 36, 若排序后的关键字序列为：14, 23, 36, 36 49, 52, 58, 80， ， 排序方法是稳定的。 则排序方法是稳定的。 若排序后的关键字序列为： 36, 若排序后的关键字序列为：14, 23, 36 36, 49, 52, 58, 80， ， 排序方法是不稳定的。 则排序方法是不稳定的。数据结构 内部排序和外部排序第十章 内部排序整个排序过程不需要访问外存便能完成， 便能完成 若整个排序过程不需要访问外存便能完成，则称此类排序问 为内部排序； 题为内部排序； 反之，若参加排序的记录数量很大，整个序列的排序过程不 反之，若参加排序的记录数量很大，整个序列的排序过程不 可能在内存中完成，则称此类排序问题为外部排序。 可能在内存中完成，则称此类排序问题为外部排序。 为外部排序 内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列的过程。 内部排序的过程是一个逐步扩大记录的有序序列的过程。 有序序列区 无 序 序 列 区 经过一趟排序 有序序列区 无 序 序 列 区数据结构 排序方法分类： 排序方法分类：第十章 内部排序将无序子序列中的一 个或几个记录“插入” 个或几个记录“插入”到 通过“交换” 通过“交换”无序序列中的记录从而 有 得到其中关键字最小 最大的记录 关键字最小或 的记录， 得到其中关键字最小或最大的记录， 基于不同的“扩大” 有序序列长度的方法， ”并 基于不同的“扩大” 有序序列长度的方法，内部排序 从记录的无序子序列中“选择” 从记录的无序子序列中“选择 序序列中， 序序列中，从而增加记录 ，以此方法增 将它加入到有序子序列 加入到有序子序列中 将它加入到有序子序列中 关键字最小或最大的记录 的记录， 关键字最小或最大的记录，并将它 方法大致可分下列几种类型： 方法大致可分下列几种类型： 的有序子序列的长度。 的有序子序列的长度。 通过“归并” 通过“归并”两个 加记录的有序子序列的长度。 加记录的有序子序列的长度。 加入到有序子序列中 加入到有序子序列中，以此方法增 或两个以上的记录有 1)、插入排序加记录的有序子序列的长度。 、希尔排序 、插入排序：直接插入排序、折半插入排序 ：直接插入排序、折半插入排序、 基数排序是一种基于多 加记录的有序子序列的长度。 序子序列， 序子序列，逐步增加 关键字排序的思想， 关键字排序的思想，将单关 2)、交换排序：冒泡排序、快速排序 、交换排序：冒泡排序、 记录有序序列的长度。 记录有序序列的长度。 多关键字” 键字按基数分成 “多关键字” 3)、选择排序：简单选择排序、堆排序 、选择排序：简单选择排序、 进行排序的方法。 进行排序的方法。 4)、归并排序：2-路归并排序 、归并排序： 路归并排序 5)、基数排序 、数据结构 10.2 插入排序 一趟直接插入排序的基本思想： 一趟直接插入排序的基本思想： 有序序列 R[1 .. i -1] R[i] 有序序列 R[1 .. i]第十章 内部排序无序序列 R[i .. n]无序序列 R[i +1 .. n]实现“一趟插入排序”可分三步进行： 实现“一趟插入排序”可分三步进行： 三步进行 1．在 R[1 .. i -1] 中查找 R[i] 的插入位置， ． 的插入位置， R[1 .. j].key ≤ R[i].key & R[ j+1 .. i -1].key； ； 2．将 R[ j+1 .. i -1] 中的所有记录均后移一个位置； ． 中的所有记录均后移一个位置； 3．将 R[i] 插入（复制）到 R[ j+1] 的位置上。 ． 插入（复制） 的位置上。数据结构 10.2.1 直接插入排序 void InsertSort ( SqList &L ) { R0 初始状态 i =2 i =3 i =4 i =5 76 38第十章 内部排序// 对顺序表 L 作直接插入排序。 作直接插入排序。 R1 R2 R3 R4 R5 R6 for ( i = 2; i &= L. ++ i ) 49 if 38 65 & L.r[i -1].key) 13 (L.r[i].key 97 76 {38 49 38 381趟 R7 R8 排序 2趟 27 49 排序 L.r[0] = L.r[i]; 的插入位置; 在 R[1.. i-1]中查找 R[i] 复制为监视哨 中查找 // 的插入位置 49 65 38 97 76 13 27 49L.r[i] = L.r[i -1]; 对于在查找过程中找到的那些关键字 for = L.r[0].key &13 ]. - 不小于 i - 2;97 的记录， L.r[ j 27 49 ( j65R[i].key 的记录，在查找的同 49 j ) 76 时实现记录向后移动； L.r[ j + 1] = L.r[ j ]; 时实现记录向后移动； // 记录后移 49 jR[i1];= L.r[0];76 //13 27 49 65 97 L.r[ + 插入 R[i] 插入到正确位置49 } // InsertSort 7趟 i =6 13 13 38 49 65 76 97 27 49 排序 排序过程： 个记录看成是一个有序子序列， 排序过程：先将序列中第 1 个记录看成是一个有序子序列， i =7 27 13 27 38 49 65 76 97 49 个记录开始，逐个进行插入，直至整个序列有序。 然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。 i =8 49 13 27 38 49 49 65 76 9738 } 496576971327数据结构 算法评价 比较次数： 比较次数：第十章 内部排序最好的情况：待排序记录按关键字从小到大排列（正序） 最好的情况：待排序记录按关键字从小到大排列（正序）∑n1 = n ? 1i=2移动次数： 移动次数：0最坏的情况：待排序记录按关键字从大到小排列（逆序） 最坏的情况：待排序记录按关键字从大到小排列（逆序） n ( n + 2 )( n ? 1 ) 比较次数： ∑ i = 比较次数： 2 i=2 n ( n + 4 )( n ? 1 ) 移动次数： 移动次数： ∑ ( i + 1 ) = 2 i= 2 一般情况：待排序记录是随机的，取平均值。 一般情况：待排序记录是随机的，取平均值。 n2 比较次数和移动次数均约 比较次数和移动次数均约为： 直接插入排序是稳定排序 4 时间复杂度： 时间复杂度： T(n)=O(n?) 空间复杂度： 空间复杂度：S(n)=O(1) 5 4 3 2 1数据结构 10.2.2 其他插入排序void BInsertSort ( SqList &L ) { for ( i = 2; i &= L. ++ i ) { 时间复杂度： 时间复杂度： T(n)=O(n?) L.r[0] = L.r[i]; low = 1; high = i -1; 仅减少了比较次数， 仅减少了比较次数， while (low &= high) { m = (low+high)/2; // 折半 移动次数不变。 移动次数不变。 if (L.r[0].key & L.r[m].key) 空间复杂度： -1; 空间复杂度：S(n)=O(1) high = m else low = m +1; } //while 折半插入排序是稳定排序 --j ) for ( j = i -1; j &= high +1; L.r[j +1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入 } //for for } // BInsertSort第十章 内部排序1、折半插入排序：用折半查找方法确定插入位置的排序。 、折半插入排序：用折半查找方法确定插入位置的排序。i =1 … i =7 6 (6 i =8 20 (6 l i =8 20 (6 l i =8 20 (6 i =8 20 (6 i =8 20 (6 13 30 39 42 70 85 ) 20 13 30 39 42 70 85 ) 20 m h 13 30 39 42 70 85 ) 20 m h 13 30 39 42 70 85 ) 20 l mh 13 30 39 42 70 85 ) 20 h l 13 20 30 39 42 70 85 ) (30) 13 70 85 39 42 6 20数据结构 10.2.3 希尔排序（缩小增量排序） 希尔排序（缩小增量排序）第十章 内部排序基本思想：对待排序列先作“宏观”调整，再作“微观”调 基本思想：对待排序列先作“宏观”调整，再作“微观” 整。排序过程：先取一个正整数 d & n，把所有相隔 d 的记录放 排序过程： ，1 1在一组内，组内进行直接插入排序； 在一组内，组内进行直接插入排序；然后取 d2 & d1，重复上述分 组和排序操作； 组和排序操作；直至 di = 1，即所有记录放进一个组中排序为止。 ，即所有记录放进一个组中排序为止。 称为增量 增量。 其中 di 称为增量。 第一趟分组， 例：第一趟分组，设 d1 = 5 49 38 65 97 76 13 27 49 55 04 第二趟分组， 第一趟希尔排序 d2 = 3 13 27 49 55 04 49 38 65 97 76 第二趟分组，设 第三趟分组， 第二趟希尔排序 d3 = 1 13 04 49 38 27 49 55 65 97 76 第三趟分组，设 第三趟希尔排序 04 13 27 38 49 49 55 65 76 97数据结构 第十章 内部排序 希尔排序特点： 希尔排序特点： 分组不是简单的“逐段分割” 分组不是简单的“逐段分割”，而是将相隔某个增量的记录组成 一个子序列。 一个子序列。 增量序列取法 希尔最早提出的选法是 d1 = ?n/2?，di +1 = ? di /2?。 ? ? 克努特 (Knuth) 提出的选法是 di +1 =?(di-1) /3?。 ? ? 还有其他不同的取法。 还有其他不同的取法。 如何选择增量序列以产生最好的排序效果， 如何选择增量序列以产生最好的排序效果，至今仍没有从数学 上得到解决。 上得到解决。 1)、没有除 1 以外的公因子； 以外的公因子； 、 2)、最后一个增量值必须为 1。 、 。 希尔排序可提高排序速度 1)、记录跳跃式前移，在进行最后一趟排序时，已基本有序。 、记录跳跃式前移，在进行最后一趟排序时，已基本有序。 2)、分组后 n 值减小，n2 更小，而 T(n)=O(n2)，所以 T(n) 从 值减小， 更小， 、 ， 总体上看是减小了。 总体上看是减小了。 ▲数据结构 10.3 交换排序 49 97 1、冒泡排序 、 排序过程 49 一般情况下每经过 13 38 38 38 38 38 13 38 49 49 49 13 27 27 49 一趟“起泡” 一趟“起泡”，“ i 减 1”， ， 65 65 65 13 27 38 38 但并不是每趟都如此。 但并不是每趟都如此。 97 76 13 27 49 49 76 例： 13 27 49 49 76 13 97 5 13 2 349 165 9 7 8 27 97 27 27 3 176 5 7 8 9 49 2 97 49 97 49 i=6 97 初 1 3第 5第 7 第 8 第 9 第 2 第 始 i=2 二 三 四 五 六 一 趟 关 2 3趟 5趟 7 趟 8 趟 9 趟 1 键= 1 排 排 排 排 排 排 i 字 序 序 序 序 序 序第十章 内部排序 Void BubbleSort(SqList &L) { 1、比较第一个记录与第二个 、 i=n 记录， ; 关键字为逆序则交换； 为逆序则交换 记录，若关键字为逆序则交换；然 while ( i &1) { 后比较第二个记录与第三个记录； 后比较第二个记录与第三个记录； for k i = i & 1; i - - ) (=1; 依次类推， = 1; j n i-1 j + +) 依次类推( j 直至第&; 个记录和第 for ， n 个记录比较为止 & r[第一趟冒泡 个记录比较为止――第一趟冒泡 if ( r[ j +1] j ]) { 排序， 排序，结果关键字最大的记录被安 r[ j ] r[ j + 1 ] ; 置在最后一个记录上。 置在最后一个记录上。 k = //交换的位置 交换的位置 for2、= 1; j & n -1; j + +) (、对前 n-1 个记录进行第二 j} if ( r[ +1] 趟冒泡排序， & r[ j ]) 趟冒泡排序j，结果使关键字次大的 i =r[ j ] r[ 个记录位置。 个记录位置。 记录被安置在第 n-1 j + 1 ]; } // while 3、重复直到 “在一趟排序 、 } 冒泡排序算法 过程中没有进行过交换记录的操 仅第一二个交换过” 为止。 作” 或“仅第一二个交换过” 为止。数据结构 算法评价 时间复杂度： 时间复杂度： 最好情况（正序） 最好情况（正序） 比较次数： 比较次数：n -1 最坏情况（逆序） 最坏情况（逆序） 比较次数： 比较次数： 移动次数： 移动次数：0第十章 内部排序T(n) = O(n) 移动次数： 移动次数：3∑ ( i ? 1) =i=n 21 2 ∑ (i ? 1) = 2 (n ? n) i=nT(n) = O(n2) 空间复杂度： 空间复杂度：S(n) = O(1) 稳定性： 稳定性：稳定排序23 2 ( n ? n) 2数据结构2、一趟快速排序（一次划分） 、一趟快速排序（一次划分） 基本思想：任选一个记录 以它的关键字作为“枢轴” 一个记录， 基本思想：任选一个记录，以它的关键字作为“枢轴”，凡 关 键字小于枢轴的记录均移至枢轴之前， 键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录 均移至枢轴之后。 均移至枢轴之后。 low 和 high，从 high 所指位置起向前搜索找 附设两个指针 ， 到第一个关键字小于枢轴的关键字的记录与枢轴记录交换， 到第一个关键字小于枢轴的关键字的记录与枢轴记录交换，然后 从 low 所指位置起向后搜索找到第一个关键字大于枢轴的关键字 的记录与枢轴记录交换，重复这两步直至 low = high 为止。 的记录与枢轴记录交换， 为止。 例： s 23 49 14 52 80 52 36 52 14 58 61 97 t 80 23 75第十章 内部排序 一般取第一个记录low low low low high high high high high high low 为枢轴。 设 R[s]=52 为枢轴。数据结构第十章 内部排序int Partition (SqList &L, int low, int high) { L.r[0]=L.r[low]; L.r[0]=L.r[low]; pivotkey = L.r[low]. //用子表的第一个记录作枢轴记录 用子表的第一个记录作枢轴记录 L.r[low]=L.r[high]; while (low & high) L.r[high]=L.r[0]; L.r[high] { while (low & high && L.r[high].key &= pivotkey) - - L.r[low]←→L.r[high]; 将比枢轴小的记录移到低端 L.r[low] = L.r[high]; // // 将比枢轴小的记录交换到低端 while (low & high && L.r[low].key &= pivotkey) + + L.r[low]←→L.r[high]; 将比枢轴大的记录移到高端 L.r[high] = L.r[low]; // // 将比枢轴大的记录交换到高端 } //while L.r[0]=L.r[low]; L.r[low]=L.r[0]; L.r[low]=L.r[high]; L.r[low] // 返回枢轴所在位置 L.r[high]=L.r[0]; } // Partition数据结构 3、快速排序 、第十章 内部排序首先对无序的记录序列进行“一次划分” 首先对无序的记录序列进行“一次划分”，之后分别对分割 所得两个子序列“递归”进行一趟快速排序。 所得两个子序列“递归”进行一趟快速排序。 快速排序过程无序的记录序列 一次划分 无序记录子序列 (1)枢轴 无序子序列 (2)分别进行一趟快速排序 有序的记录序列…数据结构 第十章 内部排序 void QSort (SqList &L, int low, int high ) { // 对顺序表 L 中的子序列 L.r[low..high] 进行快速排序 if (low & high) { // 长度大于 长度大于1 pivotloc = Partition(L, low, high) ; // 对 L.r[low..high] 进行一次划分 QSort(L, low, pivotloc-1) ; // 对低子序列递归排序，pivotloc 是枢轴位置 对低子序列递归排序， QSort(L, pivotloc+1, high); // 对高子序列递归排序 } } // QSort 第一次调用函数 Qsort 待排序记录序列的上、 时，待排序记录序列的上、 下界分别为 1 和 L.length。 。 void QuickSort( SqList & L) { // 对顺序表进行快速排序 QSort(L, 1, L.length); } // QuickSort数据结构 4、快速排序的时间分析 、第十章 内部排序假设一次划分所得枢轴位置 i=k，则对 n 个记录进行快排所 ， 需时间： 需时间： T(n) = Tpass(n) + T(k-1) + T(n-k) 个记录进行一次划分所需时间。 其中 Tpass(n) 为对 n 个记录进行一次划分所需时间。 若待排序列中记录的关键字是随机分布的， 若待排序列中记录的关键字是随机分布的，则 k 取 1 至 n 中 任一值的可能性相同。 任一值的可能性相同。 一次划分所需时间和表长成正比 由此可得快速排序所需时间的平均值为： 由此可得快速排序所需时间的平均值为：设 Tavg(1)≤b，则可得结果： ≤ ，则可得结果： 结论：快速排序的时间复杂度为 O(n log n)。 结论： 。数据结构第十章 内部排序到目前为止快速排序是平均速度最大的一种排序方法。 平均速度最大的一种排序方法 到目前为止快速排序是平均速度最大的一种排序方法。 若待排记录的初始状态为按关键字有序时， 若待排记录的初始状态为按关键字有序时，快速排序将蜕 化为起泡排序， 化为起泡排序，其时间复杂度为 O(n2)。 所以快速排序适用于 。 原始记录排列杂乱无章的情况。 原始记录排列杂乱无章的情况。 为避免出现蜕化情况，需在进行一次划分之前，进行“予 为避免出现蜕化情况，需在进行一次划分之前，进行“ 处理” 处理”，即：先对 R(s).key, R(t).key 和 R[?(s+t)/2?].key，进行 ? ? ， 相互比较，然后取关键字的大小为中间的记录为枢轴记录。 相互比较，然后取关键字的大小为中间的记录为枢轴记录。 快速排序是一种不稳定的排序，在递归调用时需要占据 快速排序是一种不稳定的排序， 不稳定的排序 一定的存储空间用来保存每一层递归调用时的必要信息。 一定的存储空间用来保存每一层递归调用时的必要信息。 ▲数据结构 10.4 选择排序 10.4.1 简单选择排序 排序过程： 排序过程：第十章 内部排序次关键字比较， 个记录中找出关键字最小 首先通过 n C1 次关键字比较，从 n 个记录中找出关键字最小 的记录，将它与第一个记录交换。 的记录，将它与第一个记录交换。 次比较， 再通过 n C2 次比较，从剩余的 n C1 个记录中找出关键字次小 的记录，将它与第二个记录交换。 的记录，将它与第二个记录交换。 重复上述操作， 趟排序后，排序结束。 重复上述操作，共进行 n C1 趟排序后，排序结束。数据结构 假设排序过程中，待排记录序列的状态为： 假设排序过程中，待排记录序列的状态为：第十章 内部排序有序序列 R[1..i-1]无序序列 R[i..n] 从中选出 关键字最小的记录第i 趟 简单选择排序有序序列R[1..i] 有序序列无序序列 R[i+1..n]数据结构 例： k i =1 初始： [ 49 初始： 13 i =2 一趟： 一趟： i =3 二趟： 二趟： 三趟： i =4 三趟： 四趟： i =5 四趟： 五趟： i =6 五趟： 排序结束：六趟： 排序结束：六趟： 13 13 13 13 13 13 k 38 65 97 76第十章 内部排序 k 比较次数 49 13 27 ]n-1j j j j j j [38 65 97 76 49 27 ] n - 2 27 [65 97 76 49 38 ] 27 38 [97 76 49 65 ] 27 38 49 [76 97 65 ] 27 38 49 65 [97 76 ] n - 6 27 38 49 65 76 [97 ] 97void SelectSort (SqList &L) { // 对顺序表 L 作简单选择排序。 作简单选择排序。 时间复杂度： 时间复杂度：O(n2) 比较次数： 比较次数： i & L. ++ i) { for (i = 1; 空间复杂度： 空间复杂度：O(1) k = for ( j = i+1; j &= j++ if (L.r[j].key & L.r[k].key) k = j++) if (L.r[j].key & 移动次数： 正序： 移动次数： 正序：最小值为 0； 最大值为 3(n-1) 。 ； if (i != k) L.r[i]←→L.r[k]; // 与第 i 个记录交换 不稳定 } 个记录的关键字最小。 前 n C 1 个为正序， } // SelectSort 个为正序，第 n 个记录的关键字最小。数据结构 锦标赛排序Wang Yang Diao Cha Xue Bao Liu Zhao Cha Bao Liu Zhao Cha Zhao Bao Cha ? Cha Liu ? Diao Liu Bao ? Bao ? Liu Yang Diao Diao ? Wang Yang Xue第十章 内部排序 前提：若乙胜丙，甲胜乙，则认为甲必能胜丙。 前提：若乙胜丙，甲胜乙，则认为甲必能胜丙。Wang Yang Xue Diao Wang Xue ? Xue ? Yang Wang ? Zhao选出冠军的比较次数为 22+21+20 = 23 -1 = n-1。 。 选出亚军的比较次数为 3，即 log2n 次。 ， 其后的 n?2 个人的名次均如此产生，所以对于 n 个参赛选手 ? 个人的名次均如此产生， 来说， 个记录进行锦标赛排序， 来说，即对 n 个记录进行锦标赛排序，总的关键字比较次数至多 为 (n?1)log2n + n ?1，故时间复杂度为： O(nlog2n)。 ? ， 时间复杂度为： 个单元外， 个辅助单元。 此法除排序结果所需的 n 个单元外，尚需 n-1 个辅助单元。 ▲数据结构第十章 内部排序10.4.2 树形选择排序 思想： 个记录的关键字进行两两比较， 思想：首先对 n 个记录的关键字进行两两比较，然后在其 中 ?n/2? 个较小者之间再进行两两比较，直到选出最小关键字 ? 个较小者之间再进行两两比较， 的记录为止。 个叶子结点的完全二叉树表示。 的记录为止。可以用一棵有 n 个叶子结点的完全二叉树表示。13 97 76 65 49 38 27 38 97 49 65 ∞ 49 38 ∞ 49 ∞ 38 ∞ 65 97 65 97 ∞ 76 ∞ 76 13 ∞ 13 ∞ 27 49 27 ∞ 76 13 49 27 ∞ ∞ 49缺点： 缺点： 1、与“∞”的比较多余； 的比较多余； 、 2、辅助空间使用多。 、辅助空间使用多。13 27 38 49 49 65 76 97 49 38 65 97 76 13 27 49 时间复杂度： 时间复杂度：由于含有 n 个叶子结点的完全二叉树的深度 为?log2n?+1，则在树形选择排序中中，除了最小关键字外，每 ? ，则在树形选择排序中中，除了最小关键字外， 选择一个次小关键字仅需进行 ?log2n? 次比较，故时间复杂度 ? 次比较， 为 O(nlog2n)。 。数据结构 10.4.3 堆排序第十章 内部排序堆的定义： 堆的定义：n 个元素的序列 (k1, k2, …, kn)，当且仅当满足下 ， 列关系时，称之为堆 列关系时，称之为堆。 ki ≤ k2i ki ≤ k2i+1 小顶堆 小根堆 正 堆 或 ki ≥ k2i ki ≥ k2i+1 大顶堆 大根堆 逆 堆 (i = 1, 2, …, ?n/2?) ?数据结构 例1： (96, 83, 27, 38, 11, 09) ：9638 49 97 76 65第十章 内部排序 例2： (13, 38, 27, 49, 76, 65, 49, 97) ：13 27 4913 38 49 76 65 27 4983 38 11 092797可将堆序列看成完全二叉树， 可将堆序列看成完全二叉树，则： k2i 是 ki 的左孩子； k2i+1 是 ki 的右孩子。 的左孩子； 的右孩子。 所有非终端结点的值均不大（ 所有非终端结点的值均不大（小）于其左右孩子结点的值。 于其左右孩子结点的值。 个元素的最小值或最大值。 堆顶元素必为序列中 n 个元素的最小值或最大值。数据结构 堆排序： 堆排序：第十章 内部排序将无序序列建成一个堆，得到关键字最小（ 将无序序列建成一个堆，得到关键字最小（大）的 记录；输出堆顶的最小（ 记录；输出堆顶的最小（大）值后，将剩余的 n-1 个元 值后， 素重又建成一个堆， 个元素的次小值； 素重又建成一个堆，则可得到 n 个元素的次小值；如此 重复执行，直到堆中只有一个记录为止，每个记录出堆 重复执行，直到堆中只有一个记录为止， 的顺序就是一个有序序列，这个过程叫堆排序。 的顺序就是一个有序序列，这个过程叫堆排序。 堆排序堆排序需解决的两个问题： 堆排序需解决的两个问题： 1、如何由一个无序序列建成一个堆？ 、如何由一个无序序列建成一个堆？ 2、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？ 、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？数据结构 第二个问题解决方法――筛选： 筛选： 第二个问题解决方法 筛选第十章 内部排序所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉 所谓“筛选”指的是，对一棵左 右子树均为堆的完全二叉 树，“调整”根结点使整个二叉树也成为一个堆。 调整”根结点使整个二叉树也成为一个堆。筛 选 堆 堆数据结构第十章 内部排序输出堆顶元素之后，以堆中最后一个元素替代之； 输出堆顶元素之后，以堆中最后一个元素替代之；然后将 根结点值与左、右子树的根结点值进行比较， 根结点值与左、右子树的根结点值进行比较，并与其中小者进 行交换；重复上述操作，直至叶子结点，将得到新的堆， 行交换；重复上述操作，直至叶子结点，将得到新的堆，称这 个从堆顶至叶子的调整过程为“筛选” 个从堆顶至叶子的调整过程为“筛选”。65 38 27 49 97 76 13 38 76 65 49 97 97 49 97 13 76 49 65 38 76 97 65 49 27 49 27 97的堆， 筛选” 对深度为 k 的堆，“筛选” 所需进行的关键字比较的次数 至多为 2(k-1)。 。数据结构 第十章 内部排序 第一个问题解决方法： 第一个问题解决方法： 从无序序列的第 ?n/2? 个元素（即无序序列对应的完全二叉 ? 个元素（ 树的最后一个内部结点） 至第一个元素止，进行反复筛选。 树的最后一个内部结点）起，至第一个元素止，进行反复筛选。 排序之前的关键字序列为： 例: 排序之前的关键字序列为： 81 55 81 73 55 73 81 64 12 36 36 12 27 98 40 98 49 40 49 98现在， 右子树都已经调整为堆 最后只要调整根结点， 右子树都已经调整为堆， 现在，左/右子树都已经调整为堆，最后只要调整根结点，使 整个二叉树是个“ 整个二叉树是个“堆”即可。 即可。 建堆是一个从下往上进行“筛选”的过程。 建堆是一个从下往上进行“筛选”的过程。数据结构第十章 内部排序定义堆类型为： 定义堆类型为： typedef SqList HeapT // 堆用顺序表表示 void HeapSort ( HeapType &H ) { // 对顺序表 H 进行堆排序 for ( i = H.length/2; i & 0; - - i ) HeapAdjust (H.r, i, H.length); // 建大顶堆 for ( i = H. i & 1; - - i ) { H.r[1]←→H.r[i]; // 将堆顶记录和当前未经排序子序列 // H.r[1..i]中最后一个记录相互交换 中最后一个记录相互交换 HeapAdjust (H.r, 1, i -1); // 对 H.r[1] 进行筛选 } } // HeapSort数据结构第十章 内部排序void HeapAdjust (HeadType &H, int s, int m) { // 已知 H.r[s..m]中记录的关键字除 H.r[s] 之外均满足堆的特征，本函数自 之外均满足堆的特征， 中记录的关键字除 // 上而下调整 H.r[s] 的关键字，使 H.r[s..m] 成为一个大顶堆 的关键字， rc = H.r[s]; // 暂存 H.r[s] for ( j=2*s; j&=m; j*=2 ) { // j 初值指向左孩子自上而下的筛选过程 初值指向左孩子自上而下的筛选过程; if ( j & m && H.r[j].key & H.r[j+1].key ) ++j; // 左/右“子树根”之间先 右 子树根” // 进行相互比较，令 j 指示关键字较大记录的位置 进行相互比较， if ( rc.key &= R[j].key ) // 再作“根”和“子树根”之间的比较，若“&=”成立，则说明 再作“ 子树根”之间的比较， 成立， 成立 // 已找到 rc 的插入位置 s ，不需要继续往下调整 R[s] = R[j]; s = } R[s] = // 将调整前的堆顶记录插入到 s 位置 } // HeapAdjust // 否则记录上移，尚需继续往下调整 否则记录上移，数据结构 堆排序的时间复杂度和空间复杂度： 堆排序的时间复杂度和空间复杂度：第十章 内部排序1. 对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至 的堆， 筛选” 多 ； 2. 为 2(k-1)； ，建成深度为 h(=?log2n?+1) 的堆，所需进行的 对 n 个关键字 个关键字， 的堆， ? ? 关键字比较的次数至多 4n； ； 3. 调整“堆顶” n-1 次，总共进行的关键字比较的次数不超过 调整“堆顶” 2 (?log2(n-1)?+ ?log2(n-2)?+ …+log22) & 2n(?log2n?) ? ? ? ? ? 因此， 因此，堆排序的时间复杂度为 O(nlogn)，与简单选择排序 ， O(n2) 相比时间效率提高了很多。 相比时间效率提高了很多。 空间复杂度： 空间复杂度：S(n) = O(1) 堆排序是一种速度快 省空间的排序方法。 速度快且 堆排序是一种速度快且省空间的排序方法。 的排序方法 不稳定。 不稳定。 ▲数据结构 10.5 归并排序第十章 内部排序归并：将两个或两个以上的有序表组合成一个新的有序表。 归并：将两个或两个以上的有序表组合成一个新的有序表。 在内部排序中， 路归并排序。 在内部排序中，通常采用的是 2-路归并排序。即：将两个 位置相邻的记录有序子序列归并为一个记录有序的序列。 位置相邻的记录有序子序列归并为一个记录有序的序列。初始关键字： 初始关键字： [49] [38] [65] [97] [76] [13] [27] 看成是 n 个有序的子 序列（ 序列（长度为 1）， ）， 然后两两归并。 然后两两归并。 得到 ?n/2? 个长度为 ? 2 或 1 的有序子序列。 的有序子序列。 每趟归并的时间复 杂度为O(n)，共需进 杂度为 ， 行 ?log2n? 趟。 ?一趟归并后： 一趟归并后： [3849] [6597] [1376] [27]二趟归并后： [38 二趟归并后： 三趟归并后： 三趟归并后： [1349 6597] [132776]27 3849657697]空间复杂度为： 空间复杂度为：O(n)。 时间复杂度为：O(nlog2n)。 稳定。 。 时间复杂度为： 。 稳定。数据结构 10.6 基数排序第十章 内部排序第一关键字 K1 第二关键字 K2 基数排序是一种借助“多关键字排序”的思想来实现“ 基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。 字排序”的内部排序算法。 学号 101 105 特点： 特点：每个记录最终的 例：将右表所示的学生 102 102 位置由两个关键 成绩单按数学成绩 103 104 1 k2 决定。 决定。 字 k 的等级由高到低排 104 101 我们将它称之为复 我们将它称之为复 105 108 序，数学成绩相同 合关键字， 合关键字，即多关键字 106 103 的学生再按英语成 排序是按照复合关键字 107 106 绩的高低等级排序。 绩的高低等级排序。 108 107 的大小排序。 的大小排序。 10.6.1 多关键字的排序 数学 A B A A B C B B C A C D D E E C 英语 C A B B B D C B B A D B B A A B 其它 … … … … … … … …数据结构第十章 内部排序张牌，可按花色 面值分成两个 关键字” 花色和 分成两个“ 例：扑克牌中 52 张牌，可按花色和面值分成两个“关键字”，其 大小关系为：花色： 大小关系为：花色： ? & ?& ?& ? 面值： 面值： 2&3&4&5&6&7&8&9&10&J&Q&K&A 若对扑克牌按花色、面值进行升序排序，得到如下序列： 若对扑克牌按花色、面值进行升序排序，得到如下序列： ?2, ?3, ..., ?A, ?2, ?3, ..., ?A, ?2, ?3, ..., ?A, ?2, ?3, ..., ?A 即两张牌，若花色不同，不论面值怎样， 即两张牌，若花色不同，不论面值怎样，花色低的那张牌小 于花色高的，只有在同花色情况下， 于花色高的，只有在同花色情况下，大小关系才由面值的大小确 多关键字排序。 按照复合关键字的大小排序 定。这也是按照复合关键字的大小排序，即：多关键字排序。 这也是按照复合关键字的大小排序，数据结构 多关键字排序的方法： 多关键字排序的方法：第十章 内部排序n 个记录的序列 {R1, R2, …, Rn} 对关键字 (Ki0, Ki1, …, Kid-1) 有序是指： 有序是指：对于序列中任意两个记录 Ri 和 Rj (1≤i & j≤n) 都满 足下列（词典）有序关系：(Ki0, Ki1, …, Kid-1) & (Kj0, Kj1, …, Kjd-1) 足下列（词典）有序关系： 最主位关键字， 被称为最次位关键字 最次位关键字。 其中： 其中：K 0 被称为 最主位关键字， Kd-1 被称为最次位关键字。 多关键字排序按照从最主位关键字到最次位关键字或从最次 位关键字到最主位关键字的顺序逐次排序，分两种方法： 位关键字到最主位关键字的顺序逐次排序，分两种方法： 最高位优先法， 排序分组， 最高位优先法，简称 MSD 法：先按 k 0 排序分组，同一组中 记录， 相等， 排序分成子组，之后， 记录，关键字 k 0 相等，再对各组按 k 1 排序分成子组，之后，对 后面的关键字继续这样的排序分组， 后面的关键字继续这样的排序分组，直到按最次位关键字 k d 对 各子组排序后，再将各组连接起来，便得到一个有序序列。 各子组排序后，再将各组连接起来，便得到一个有序序列。数据结构第十章 内部排序最低位优先法， 开始排序， 最低位优先法，简称 LSD 法：先从 k d-1 开始排序，再对 k d-2 进行排序，依次重复， 排序后便得到一个有序序列。 进行排序，依次重复，直到对 k 0 排序后便得到一个有序序列。 例：学生记录含三个关键字： 学生记录含三个关键字： 系别、班号和班内的序列号， 系别、班号和班内的序列号， 其中以系别为最主位关键字。 其中以系别为最主位关键字。 LSD的排序过程如下： 的排序过程如下： 的排序过程如下 对 Ki (0≤i≤d -2) 进行排序时， 进行排序时，只能用 稳定的排序方法。 的排序方法 稳定的排序方法。无序序列 3,2,30 1,2,15 3,1,20 对K2排序 1,2,15 2,3,18 3,1,20 对K1排序 3,1,20 2,1,20 1,2,15 对K0排序 1,2,15 2,1,20 2,3,182,3,18 2,1,20 3,2,30 3,1,202,1,20 3,2,30 2,3,18 3,2,30数据结构第十章 内部排序法进行的排序，在一定的条件下（ 用 LSD 法进行的排序，在一定的条件下（即对 Ki 的不同值 Ki+1 均取相同值），可通过若干次“分配”和“收集”来实现。 均取相同值），可通过若干次“分配” ），可通过若干次 收集”来实现。 例：先将学生记录按英语等级由高到低分成 A、B、C、D、E 五 先将学生记录按英语等级由高到低分成 、 、 、 、 英语 个组： 个组：关键字类别 各组成员 A AA EA B AB BB DB CB C BC D CD E 学号 数学 英语 其它 … 101 B C 102 103 104 105 A C B A D E C B D B A B A B … … … … … … …然后按从左向右， 然后按从左向右，从上向下的顺序将 106 它们收集起来得到关键字序列： 它们收集起来得到关键字序列： 107 AA，EA，AB，BB，DB，CB，BC，CD ， ， ， ， ， ， ， 108数据结构关键字类别 各组成员 A AA EA B AB BB DB CB C BC D CD E第十章 内部排序 按从上向下， 按从上向下，从左向 右的顺序将其收集起 来得到关键字序列： 来得到关键字序列： AA，EA，AB，BB， ， ， ， ， DB，CB，BC，CD ， ， ， 按从上向下，从左向 按从上向下， 右的顺序将其收集起 来得到关键字序列： 来得到关键字序列：再按数学成绩由高到低分成 A、B、C、D、E 五个组： 、 、 、 、 五个组：关键字类别 各组成员 A AA AB B BB BC C CB CD D DB E EAAA，AB，BB，BC，CB，CD，DB， AA，AB，BB，BC，CB，CD，DB，EA 可以看出，这个关键字序列已经是有序的了。 可以看出，这个关键字序列已经是有序的了。 对每个关键字都是将整个序列按关键字分组， 对每个关键字都是将整个序列按关键字分组，然后按顺序收 显然LSD法，操作比较简单。 集，显然 法 操作比较简单。数据结构第十章 内部排序 必须将序列逐层分 割成若干子序列， 割成若干子序列， MSD 然后对各子序列分 别排序。 别排序。MSD 与 LSD 的不同特点不必分成子序列， 不必分成子序列， 对每个关键字都是 LSD 整个序列参加排序； 整个序列参加排序； 通过若干次分配与 收集实现排序。 收集实现排序。数据结构 基数排序： 基数排序：第十章 内部排序是借助于多关键字排序思想进行排序的一种排序方法。该 是借助于多关键字排序思想进行排序的一种排序方法。 方法将排序关键字K 看作是由多个关键字组成的组合关键字， 方法将排序关键字 看作是由多个关键字组成的组合关键字， 表示关键字的一位， 即：K=k0k1…kd-1。每个关键字 ki 表示关键字的一位，其中 k0 为最高位， 为最低位， 为关键字的位数。 为最高位，kd-1 为最低位，d 为关键字的位数。 例：对于关键字序列 (101, 203, 567, 231, 478, 352)，可以将每个 ， 看成由三个单关键字组成， 关键字 K 看成由三个单关键字组成，即 K= k1k2k3， 每个关键字 的取值范围为 0≤ki≤9，所以每个关键字可取值的数目为 10。 ， 。 通常将关键字取值的数目称为基数 基数， 表示， 通常将关键字取值的数目称为基数，用 r 表示，在本例中 r =10。 。 对于关键字序列（ 对于关键字序列（AB, BD, ED）可以将每个关键字看成是 ） 由二个单字母关键字组成的复合关键字， 由二个单字母关键字组成的复合关键字，并且每个关键字的取 值范围为 “A~Z”，所以关键字的基数 r = 26。 ， 。数据结构第十章 内部排序基数排序可用多关键字的LSD方法排序，即对待排序的记 方法排序， 基数排序可用多关键字的 方法排序 录序列按复合关键字从低位到高位的顺序交替地进行“分组”、 录序列按复合关键字从低位到高位的顺序交替地进行“分组” “收集”，最终得到有序的记录序列。在此我们将一次“分 收集” 最终得到有序的记录序列。在此我们将一次“ 组”、 位关键字组成的复合关键字， “收集”称为一趟。对于由 d 位关键字组成的复合关键字，需 收集”称为一趟。 要 经过d 趟的“分配” 收集” 因此， 值较大， 经过 趟的“分配”与“收集”。 因此，若 d 值较大，基数排▲数据结构 10.6.2 链式基数排序第十章 内部排序在计算机上实现基数排序时，为减少所需辅助存储空间， 在计算机上实现基数排序时，为减少所需辅助存储空间， 应采用链表作存储结构，即链式基数排序，具体作法为： 应采用链表作存储结构，即链式基数排序，具体作法为： 1、以静态链表存储待排记录，并令表头指针指向第一个记录； 、以静态链表存储待排记录，并令表头指针指向第一个记录； 2、“分配” 时，按当前“关键字位”所取值，将记录分配到不 、 分配” 按当前“关键字位”所取值， 同 链队列” 关键字位” 相同； “链队列 3、的收集”时，按当前关键字位取值从小到大将各队列首尾相 、“收集” ” 中，每个队列中记录的 “关键字位” 相同； 链成一个链表； 链成一个链表； 4、对每个关键字位均重复 2 和 3 两步。 、 两步。数据结构第十章 内部排序例： 以静态链表存储待排记录，并令表头指针指向第一个记录。 以静态链表存储待排记录，并令表头指针指向第一个记录。278 109 063 930 589 184 505 269 008 083“分配” 时，按当前“关键字位”所取值，将记录分配到不同的“链队 分配” 按当前“关键字位”所取值，将记录分配到不同的“ 分配 列” 中，e[0] 每个队列中记录的 “关键字位” 相同。 e[1] e[2] 关键字位” 相同。 e[3] e[4] e[5] e[6] e[7] e[8] e[9] 一 趟 269 分 配 083 008 589 930 f[0] f[1] f[2] 063 f[3] 184 f[4] 505 f[5] f[6] f[7] 278 f[8] 109 f[9]一趟收集：按当前关键字位取值从小到大将各队列首尾相链成一个链表； 一趟收集：按当前关键字位取值从小到大将各队列首尾相链成一个链表； 930 063 083 184 505 278 008 109 589 269数据结构一趟收集： 一趟收集： 930 063 083 184 505 278 008第十章 内部排序109589269e[0] 二 趟 分 配 505 f[0] 二趟收集： 二趟收集： 505 109 008e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8] 589e[9]269 930 f[1] f[2] f[3] f[4] f[5] 063 f[6] 278 f[7]184 083 f[8] f[9]008109930063269278083184589数据结构二趟收集： 二趟收集： 505 008 109 930 063 269 278第十章 内部排序083184589e[0] 三 趟 分 配 063 008 f[0] 三趟收集： 三趟收集： 008 083e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]184 109 f[1]278 269 f[2] f[3] f[4]589 505 f[5] f[6] f[7] f[8] 930 f[9]063083109184269278505589930数据结构 算法评价： 算法评价： 时间复杂度： 时间复杂度：第十章 内部排序假设：n ―― 记录数 假设： d ―― 关键字数 rd ―― 关键字取值范围 （如十进制为10） 如十进制为 ）分配（每趟）：T(n)=O(n) 分配（每趟）： ）： 收集（每趟）：T(n)=O(rd) 收集（每趟）： ）： T(n)=O(d(n+rd)) 空间复杂度： 空间复杂度：S(n)=2rd 个队列指针 + n 个指针域空间 ▲数据结构 10.7 各种排序方法的综合比较第十章 内部排序 一、时间性能1. 按平均时间性能来分，有三类排序方法： 按平均时间性能来分，有三类排序方法： 时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序，其中以 ：快速排序、堆排序和归并排序， 快速排序为最好。 快速排序为最好。 时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序， ：直接插入排序、起泡排序和简单选择排序， 其中以直接插入为最好， 其中以直接插入为最好，特别是对那些对关 键字基本有序的记录序列尤为如此。 键字基本有序的记录序列尤为如此。 时间复杂度为 O(n)：基数排序。 ：基数排序。 2. 当待排序列按关键字顺序有序时，直接插入排序和起泡排序能 当待排序列按关键字顺序有序时， 的时间复杂度， 达到 O(n) 的时间复杂度，快速排序的时间性能蜕化为 O(n2) 。 3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中 简单选择排序、 关键字的分布而改变。 关键字的分布而改变。数据结构 二、空间性能第十章 内部排序指的是排序过程中所需的辅助空间大小。 指的是排序过程中所需的辅助空间大小。 1. 所有的简单排序方法 包括：直接插入、冒泡和简单选择 和 所有的简单排序方法(包括 直接插入、冒泡和简单选择) 包括： 堆排序的空间复杂度为 O(1)； ； 2. 快速排序为 O(logn)，为递归程序执行过程中，栈所需的辅助 ，为递归程序执行过程中， 空间； 空间； 3. 归并排序所需辅助空间最多，其空间复杂度为 O(n)； 归并排序所需辅助空间最多， ； 4. 链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。 链式基数排序需附设队列首尾指针， 。 三、排序方法的稳定性能 1. 当对多关键字的记录序列进行 当对多关键字的记录序列进行LSD方法排序时，必须采用稳 方法排序时， 方法排序时 定的排序方法。 定的排序方法。 2. 对于不稳定的排序方法，只要能举出一个实例说明即可。 对于不稳定的排序方法，只要能举出一个实例说明即可。 3. 快速排序、堆排序和希尔排序是不稳定的排序方法。 快速排序、堆排序和希尔排序是不稳定的排序方法数据结构 四、关于“排序方法的时间复杂度的下限” 关于“排序方法的时间复杂度的下限”第十章 内部排序本章讨论的各种排序方法，除基数排序外， 本章讨论的各种排序方法，除基数排序外，其它方法都是 一般情况下， 个关键字进行排序，可能得到的结果有n! 一般情况下，对 n 个关键字进行排序，可能得到的结果有 基于“比较关键字”进行排序的排序方法。 基于“比较关键字”进行排序的排序方法。 种，由于含 n! 个叶子结点的二叉树的深度不小于 ?log2(n!)? +1， ? ， 可以证明， 可以证明，这类排序方法可能达到的最快的时间复杂度为 则对 n 个关键字进行排序的比较次数至少是 ?log2(n!)? ≈ nlog2n ? O(nlogn)。（基数排序不是基于“比较关键字”的排序方法， 。（基数排序不是基于 。（基数排序不是基于“比较关键字”的排序方法， (斯特林近似公式 。 斯特林近似公式)。 斯特林近似公式 所 所以，基于“比较关键字”进行排序的排序方法，可能达到 所以，基于“比较关键字”进行排序的排序方法， 以它不受这个限制。） 以它不受这个限制。） 的 对三个关键字进行排序的判定树如下： 例：对三个关键字进行排序的判定树如下： 最快的时间复杂度为 O(nlogn)。 。 1、树上的每一 、树上的每一 K1 & K2K1 & K3 K2 & K3 K3&K2&K1 K2&K1&K3 K2 & K3 K1 & K3次“比较”都 比较” 是必要的； 是必要的； 结点包含所 有可能情况。 有可能情况。、树上的叶子 K1&K2&K3 2、树上的叶子K2&K3&K1K3&K1&K2K1&K3&K2数据结构第十章 内部排序教学要求1、掌握排序的基本概念和各种排序方法的特点，并能加以 、掌握排序的基本概念和各种排序方法的特点， 灵活应用； 灵活应用； 2、掌握插入排序、交换排序、选择排序、归并排序的方法 、掌握插入排序、交换排序、选择排序、 及其性能分析方法； 及其性能分析方法； 3、了解基数排序方法及其性能分析方法。 、了解基数排序方法及其性能分析方法。数据结构第十章 内部排序作业： 作业： 10.1, 10.3, 10.12, 10.13（指出对这种序列采用哪种排序方 （ 法最快。） 法最快。）
第10章排序练习题答案_理学_高等教育_教育专区。数据结构各章练习题及答案 第10 章排序练习题答案一、填空题 1. 大多数排序算法都有两个基本的操作: 比较 和 ...数据结构第十章排序练习及答案 数据结构(C语言版)严蔚敏 吴伟民 编著 清华大学出版社数据结构(C语言版)严蔚敏 吴伟民 编著 清华大学出版社隐藏&& 一、选择题 1、...第10 章 内部排序一、单项选择题 1.若要尽可能地完成对实数数组得排序,且要求排序是稳定的,则应选___。 A.快速排序 C.归并排序 B.堆排序 D.基数排序 2....数据结构 第10章习题答案_IT认证_资格考试/认证_教育专区。数据结构 第10 章 《排序》习题参考答案 一、填空题(每空 1 分,共 24 分) 1. 大多数排序算法都...第10 章内部排序 习题练习答案 1.以关键字序列(265,301,751,129,937,863,742,694,076,438)为例,分别写出执行以下排序算法 的各趟排序结束时,关键字序列的...数据结构第10章作业_计算机软件及应用_IT/计算机_专业资料。第 10 章排序作业 作业一: 1) 对人意的 7 个关键字进行排序,至少要进行___次关键字 之间的两两...第十章排序答案_计算机软件及应用_IT/计算机_专业资料。第 10 章 排序 一、选择...【南京理工大学 1997 三、5 (2 分) 】 6.堆是一种有用的数据结构。试...堆排序 (1) 其比较次数与序列初态无关的算法是( )(2)不稳定的排序算法是(...第九章排序习题_数据结构... 9页 免费
数据结构答案 第10章 排... 12页...数据结构(c语言版)题集答案――第十章_内部排序_IT认证_资格考试/认证_教育专区。数据结构题集(c语言版)答案及部分代码第十章 内部排序 10.23 void Insert_So...《数据结构》第十章 排序 例题及答案《数据结构》第十章 排序 例题及答案隐藏&& 例题1:已知序列{17,18,60,40,7,32,73,65,85},请给出采用冒泡排序法对该...
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。}