ppt做长图网站,网站代码快捷键,摄影设计工作室,自己开发的软件如何赚钱一、排序的部分基本概念
1. 算法的稳定性
若待排序表中有两个元素 Ri 和 Rj #xff0c;其对应的关键字相同即 keyi keyj#xff0c;且在排序前 Ri 在 Rj 的前面#xff0c;若使用某一排序算法排序后#xff0c;Ri 仍然在 Rj 的前面#xff0c;则称这个排序算法是稳定的…一、排序的部分基本概念
1. 算法的稳定性
若待排序表中有两个元素 Ri 和 Rj 其对应的关键字相同即 keyi keyj且在排序前 Ri 在 Rj 的前面若使用某一排序算法排序后Ri 仍然在 Rj 的前面则称这个排序算法是稳定的否则称排序算法是不稳定的。
需要注意的是算法是否具有稳定性并不能衡量一个算法的优劣 它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复则排序结果是唯一的那么选择排序算法时的稳定与否就无关紧要。
2. 排序的分类
在排序过程中根据数据元素是否完全在内存中可将排序算法分为两类
1内部排序
是指在排序期间元素全部存放在内存中的排序。
2外部排序
是指在排序期间元素无法全部同时存放在内存中必须在排序的过程中根据要求不断地在内、外存之间移动的排序。
3. 一些结论
对于任意序列进行基于比较的排序求至少的比较次数应考虑最坏情况。对任意 n 个关键字排序的比较次数至少为 ⌈log2(n!)⌉ 。
上述公式证明如下在基于比较的排序方法中每次比较两个关键字后仅出现两种可能的转移。假设整个排序过程至少需要做 t 次比较则显然会有 2t 种情况。由于 n 个记录共有 n! 种不同的排列因而必须有 n! 种不同的比较路径于是有 2t n!即 t log2(n!) 。考虑到 t 为整数故为 ⌈log2(n!)⌉ 。
二、插入排序 插入排序是一种简单直观的排序方法其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法直接插入排序、折半插入排序和希尔排序。 【注】默认排序结果为非递减有序序列。 1. 直接插入排序
1算法思想与实现步骤
① 直接插入排序的基本思想是 将待排序的数组分为已排序和未排序两部分。每次从未排序部分中取出一个元素找到其在已排序部分中的合适位置并插入。
② 直接插入排序的实现步骤是 a从第二个元素开始依次取出待排序部分的第一个元素(当前元素)。 b与已排序部分的元素进行比较找到当前元素合适的插入位置。 即找到元素 L(i) 在有序序列 L[1…i - 1] 中的插入位置 k c将已排序部分中大于当前元素的元素向后移动一位为当前元素腾出位置。 即将 L[ k…i - 1] 中的所有元素依次后移一个位置 d将当前元素插入到找到的位置 即将 L(i) 复制到 L(k) e重复步骤 a-d 直到所有元素均被插入。 为了实现对 L[1…n] 的排序可以将 L(2) ~ L(n) 依次插入前面已排好序的子序列初始 L[1] 可以视为是一个已排好序的子序列。插入排序在实现上通常采用 就地排序空间复杂度为 O(1) 因而在从后向前的比较过程中需要反复把已排序元素逐步向后挪位为新元素提供插入空间。 2算法的C代码
void InsertSort(ElemType A[],int n) {int i, j;for(i2; in; i) { // 依次将A[2]~A[n]插入前面已排好序的序列中if(A[i]A[i-1]) { // 若A[i]关键字小于其前驱将A[i]插入有序表A[0] A[i]; // 复制为哨兵A[O]不存放元素for(ji-1; A[0]A[j]; --j){ // 从后往前查找待插入位置A[j1] A[j]; // 向后挪位} A[j1] A[O] ; // 复制到插入位置}}
}3示例
假定初始序列为 49, 38, 65, 97, 76, 13, 27, 49’初始时 49 可以视为一个已排好序的子序列按照上述算法进行直接插入排序的过程如下图所示括号内是已排好序的子序列。 4算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率仅使用了常数个辅助单元因而空间复杂度为 O(1) 。
II、时间效率在排序过程中向有序子表中逐个地插入元素的操作进行了 n - 1 趟每趟操作都分为比较关键字和移动元素而比较次数和移动次数取决于待排序表的初始状态。
在最好情况下表中元素已经有序此时每插入一个元素都只需比较一次而不用移动元素因而时间复杂度为 O(n) 。在最坏情况下表中元素顺序刚好与排序结果中的元素顺序相反逆序总的比较次数达到最大总的移动次数也达到最大总的时间复杂度为 O(n2) 。平均情况下考虑待排序表中元素是随机的此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度总的比较次数与总的移动次数均约为 n2 / 4 。
因此直接插入排序算法的时间复杂度为 O(n2) 。
② 稳定性
由于每次插入元素时总是从后向前先比较再移动所以不会出现相同元素相对位置发生变化的情况即直接插入排序是一个稳定的排序方法。
③ 适用性
直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时可以从前往后查找指定元素的位置。
2. 折半插入排序 从直接插入排序算法中不难看出每趟插入的过程中都进行了两项工作 ① 从前面的有序子表中查找出待插入元素应该被插入的位置② 给插入位置腾出空间将待插入元素复制到表中的插入位置。 当排序表为顺序表时可以对直接插入排序算法做如下改进 由于是顺序存储的线性表所以查找有序子表时可以用折半查找来实现。确定待插入位置后就可统一地向后移动元素。 1算法思想与实现步骤
① 折半插入排序的基本思想是 折半插入排序是对直接插入排序的优化通过折半查找的方法来提高插入的位置寻找效率。它减少了比较次数但在后面的插入步骤中仍需移动元素。
② 折半插入排序的实现步骤是 a从第二个元素开始依次取出待排序部分的第一个元素(当前元素)。 b在已排序部分使用折半查找找到当前元素的插入位置。 c移动已排序部分中大于当前元素的元素为当前元素腾出位置。 d将当前元素插入到找到的位置。 e重复步骤 a-e 直到所有元素均被插入。
2算法的C代码
void InsertSort(ElemType A[], int n) {int i, j, low, high, mid;for(i2; in; i) { // 依次将A[2]~A[n]插入前面的已排序序列A[O] A[i]; // 将A[i]暂存到A[O]low 1; high i-1; // 设置折半查找的范围while(low high) { // 折半查找默认递增有序mid (lowhigh)/2; // 取中间点if(A[mid]A[O]){high mid-1;} // 查找左半子表else{low mid1;} // 查找右半子表}for(ji-1; jhigh1; --j){ // 此时的high1lowA[j1] A[j]; // 统一后移元素空出插入位置}A[high1] A[O]; // 插入操作}
}3算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率仅使用了常数个辅助单元因而空间复杂度为 O(1) 。
II、从上述算法中不难看出折半插入排序仅减少了比较元素的次数约为 O(nlog2n)该比较次数与待排序表的初始状态无关仅取决于表中的元素个数 n 而元素的移动次数并未改变它依赖于待排序表的初始状态。 因此折半插入排序的时间复杂度仍为 O(n2) 但对于数据量不很大的排序表 折半插入排序往往能表现出很好的性能。
② 稳定性
折半插入排序是一种稳定的排序方法。
③ 适用性
折半插入排序算法仅适用于顺序存储的线性表。
3. 希尔排序 直接插入排序算法的时间复杂度为 O(n2)但若待排序列为“正序”时其时间效率可提高至 O(n)由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的又称缩小增量排序。 1算法思想与实现步骤
① 希尔排序的基本思想是 希尔排序是插入排序的一种改进版本通过选取增量序列来将数组分成多个子序列分别进行局部排序最后再进行整体插入排序。这种方法可以减少元素的移动次数提升排序效率。
② 希尔排序的实现步骤是 a选择一个增量序列。 例如初始增量为 d小于 n 通常 d n / 2随后不断缩小增量直到增量为 1 b对于每个增量按增量将整个数组分为若干个子序列。 即将待排序表分割成若干形如 L[ i, i d, i 2d, … , i kd ] 的“特殊子序列 c对每个子序列进行直接插入排序。 d重复步骤 b-c直到增量为 1 。 e最后对整个数组进行一次插入排序确保整体有序。
2算法的C代码
void ShellSort(ElemType A[] , int n) {
// A[O]只是暂存单元不是哨兵当jO时插入位置已到int d, i, j;for(dn/2; d1; dd/2){ // 增量变化无统一规定for(id1; in; i){if(A[i]A[i-d]){ // 需将A[i]插入有序增量子表A[O] A[i]; // 暂存在A[O]for(ji-d; jO A[0]A[j]; j-d){A[jd] A[j]; // 记录后移查找插入的位置}A[jd] A[0]; // 插入}}}
}3示例
先追求表中元素部分有序再逐渐逼近全局有序。 4算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率 仅使用了常数个辅助单元因而空间复杂度为 O(1) 。
II、时间效率 由于希尔排序的时间复杂度依赖于增量序列的函数这涉及数学上尚未解决的难题所以其时间复杂度分析比较困难。
当 n 在某个特定范围时希尔排序的时间复杂度约为 O(n1.3) 【优于直接插入排序】。在最坏情况下希尔排序的时间复杂度为 O(n2) 。
希尔排序最好的情况是序列原本就有序比较好的情况是序列基本有序。
② 稳定性
当相同关键字的记录被划分到不同的子表时可能会改变它们之间的相对次序因此希尔排序是一种不稳定的排序方法。
③ 适用性
希尔排序算法仅适用于线性表为顺序存储的情况。
4. 例题
① 折半插入排序算法的时间复杂度为 C 。 A. O(n) B. O(nlog2n) C. O(n2) D. O(n3)
② 【2012 统考真题】对同一待排序序列分别进行折半插入排序和直接插入排序两者之间可能的不同之处是 D 。 A. 排序的总趟数 B. 元素的移动次数 C. 使用辅助空间的数量 D. 元素之间的比较次数
③ 【2014 统考真题】用希尔排序方法对一个数据序列进行排序时若第一趟排序结果为 9, 1, 4, 13, 7, 8, 20, 23, 15 , 则该趟排序采用的增量间隔可能是 B 。 A. 2 B. 3 C. 4 D. 5
④ 【2015 统考真题】希尔排序的组内排序采用的是 A 。 A. 直接插入排序 B. 折半插入排序 C. 快速排序 D. 归并排序
⑤ 【2018 统考真题】对初始数据序列 (8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6) 进行希尔排序。若第一趟排序结果为 (1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8) 第二趟排序结果为 (1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9) 则两趟排序采用的增量间隔依次是 D 。 A. 3, 1 B. 3, 2 C. 5, 2 D. 5, 3
三、交换排序 所谓交换是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。基于交换的排序算法很多下面主要介绍冒泡排序和快速排序。 1. 冒泡排序
1算法思想与实现步骤
① 冒泡排序的基本思想是 冒泡排序通过从后往前或从前往后两两比较相邻元素的值若为逆序即 A[i - 1] A[ i ] 则交换它们将最小的元素逐步“冒泡”到序列的开头或将最大的元素逐步“冒泡”到序列的末尾。这个过程重复进行前一趟确定的最小或最大的元素不再参与比较每趟冒泡都会将未确定序列中下一个最小或最大的元素放到正确的位置。这样最多做 n - 1 趟冒泡就能把所有元素排好序。
② 冒泡排序的实现步骤是 a从尾到头或从头到尾遍历序列比较相邻的两个元素。 b如果前一个元素大于后一个元素则交换这两个元素。 c每遍历一轮最小的元素会传到序列的开头或最大的元素会传到序列的末尾。 d重复步骤 a-c直到没有交换发生为止。 注意冒泡排序中所产生的有序子序列一定是全局有序的不同于直接插入排序也就是说有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字这样每趟排序都会将一个元素放置到其最终的位置上。 2算法的C代码
void BubbleSort(ElemType A[],int n){for(int iO; in-1; i){bool flag false; // 表示本趟冒泡是否发生交换的标志for(int jn-1; ji; j--){ // 一趟冒泡过程if(A[j-1] A[j]){ // 若为逆序swap (A[j-1], A[j]); // 交换flag true;}}if(flagfalse){return;} // 本趟遍历后没有发生交换说明表已经有序}
}3示例 4算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率仅使用了常数个辅助单元因而空间复杂度为 O(1) 。
II、时间效率
当初始序列有序时显然第一趟冒泡后 flag 依然为 false本趟没有元素交换从而直接跳出循环比较次数为 n - 1移动次数为 0从而最好情况下的时间复杂度为 O(n)当初始序列为逆序时需要进行 n - 1 趟排序第 i 趟排序要进行 n - i 次关键字的比较而且每次比较后都必须移动元素 3 次来交换元素位置。 从而最坏情况下的时间复杂度为O(n2)平均时间复杂度为O(n2) 。
② 稳定性
由于 i j 且 A [i] A [j] 时不会发生交换因此冒泡排序是一种稳定的排序方法。
③ 适用性
冒泡排序算法适用于顺序存储和链式存储的线性表。
2. 快速排序
1算法思想与实现步骤
① 快速排序的基本思想是 快速排序采用分治法在待排序表 L[1…n] 中任取一个元素 pivot 作为枢轴或称基准通常取首元素通过一趟排序将待排序表划分为独立的两个子表 L[1…k - 1] 和 L[k 1…n]使得 L[1…k - 1] 中的所有元素小于 pivotL[k 1…n] 中的所有元素大于或等于 pivot则 pivot 放在了其最终位置 L(k) 上这个过程称为一次划分。然后分别递归地对左右两个子表重复上述过程直至每部分内只有一个元素或空为止即所有元素放在了其最终位置上。
② 快速排序的实现步骤是 a从待排序表中选择一个基准元素通常选第一个、最后一个或中间的元素。 b将待排序表重排使得基准的左侧是所有小于基准的元素右侧是所有大于基准的元素。 c递归地对基准左侧和右侧的子表进行快速排序。 d直到子表的规模为 1 或 0即已经是有序的。 注意在快速排序算法中并不产生有序子序列但每趟排序后会将上一趟划分的各个无序子表的枢轴基准元素放到其最终的位置上。 2算法的C代码
void QuickSort (ElemType A[],int low,int high){if(low high) { // 递归跳出的条件int pivotpos Partition(A, low, high); // 划分// Partition()就是划分操作将表A[low…high]划分为满足上述条件的两个子表QuickSort(A, low, pivotpos-1); // 依次对两个子表进行递归排序QuickSort(A, pivotposl, high);}
}
int Partition(ElemType A[], int low, int high) { // 一趟划分ElemType pivot A[low]; // 将当前表中第一个元素设为枢轴对表进行划分while(low high) { // 循环跳出条件while(low high A[high] pivot) {--high;}A[low] A[high]; // 将比枢轴小的元素移动到左端while(low high A[low] pivot) {low;}A[high] A[low]; // 将比枢轴大的元素移动到右端}A[low] pivot; // 枢轴元素存放到最终位置return low; // 返回存放枢轴的最终位置
}3示例 用二叉树的形式描述这个举例的递归调用过程如下图所示 4算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率由于快速排序是递归的需要借助一个递归工作栈来保存每层递归调用的必要信息其容量与递归调用的最大深度一致。
最好情况下为 O(log2n最坏情况下因为要进行 n - 1 次递归调用所以栈的深度为 O(n) 平均情况下栈的深度为 O(log2n) 。
II、时间效率快速排序的运行时间与划分是否对称有关。快速排序的最坏情况发生在两个区域分别包含 n - 1 个元素和 0 个元素时这种最大限度的不对称性若发生在每层递归上即对应于初始排序表基本有序或基本逆序时就得到最坏情况下的时间复杂度为 O(n2) 。 有很多方法可以提高算法的效率 一种方法是尽量选取一个可以将数据中分的枢轴元素如从序列的头尾及中间选取三个元素再取这三个元素的中间值作为最终的枢轴元素或者随机地从当前表中选取枢轴元素这样做可使得最坏情况在实际排序中几乎不会发生。 在最理想的状态下即 Partition() 可能做到最平衡的划分得到的两个子问题的大小都不可能大于n / 2在这种情况下快速排序的运行速度将大大提升此时时间复杂度为O(nlog2n) 。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。 ② 稳定性
在划分算法中若右端区间有两个关键字相同且均小于基准值的记录则在交换到左端区间后它们的相对位置会发生变化即快速排序是一种不稳定的排序方法。
③ 适用性
快速排序算法仅适用于顺序存储的线性表。
3. 例题
① 快速排序算法在 D 情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序
② 就平均性能而言目前最好的内部排序方法是 D 。 A. 冒泡排序 B. 直接插入排序 C . 希尔排序 D. 快速排序
③ 【2010 统考真题】采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中正确的是 D 。 A. 递归次数与初始数据的排列次序元关 B. 每次划分后先处理较长的分区可以减少递归次数 C. 每次划分后先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关
④ 【2011 统考真题】为实现快速排序算法待排序序列宜采用的存储方式是 A 。 A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储
⑤ 【2014 统考真题】下列选项中不可能是快速排序第 2 趟排序结果的是 C 。 A. 2, 3, 5, 4, 6, 7, 9 B. 2, 7, 5, 6, 4, 3, 9 C. 3, 2, 5, 4, 7, 6, 9 D. 4, 2, 3, 5, 7, 6, 9
⑥ 【2019 统考真题】排序过程中对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中不可能是快速排序第二趟结果的是 D 。 A. 5, 2, 16, 12, 28, 60, 32, 72 B. 2, 16, 5, 28, 12, 60, 32, 72 C. 2, 12, 16, 5, 28, 32, 72, 60 D. 5, 2, 12, 28, 16, 32, 72, 60
⑦ 【2023 统考真题】使用快速排序算法对数据进行升序排序若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88则该次划分的枢轴是 D 。 A. 11 B. 70 C. 80 D. 81
⑧ 对 8 个元素的序列进行快速排序在最好情况下的关键字比较次数是 D 。 A. 7 B. 8 C. 12 D. 13 【快速排序的最好情况是每次划分将待排序序列划分为等长的两部分。】
⑨ 双向冒泡排序是指对一个序列在正反两个方向交替进行扫描第一趟把最大值放在序列的最右端第二趟把最小值放在序列的最左端之后在缩小的范围内进行同样的扫描放在次右端、次左端直到序列有序。对数组 {4, 7, 8, 3, 5, 6, 10, 9, 1, 2} 进行双向冒泡排序则排序趟数是 B 。第一趟从左往右开始从左往右或从右往左都称为一趟。 A. 7 B. 6 C. 8 D. 9 【序列已有序后仍需再进行一趟无交换的排序才能确定序列已有序。】
四、选择排序 选择排序的基本思想是 每一趟如第 i 趟在后面 n - i 1 i 1, 2, … , n - 1 个待排序元素中选取关键字最小的元素作为有序子序列的第 i 个元素直到第 n - 1 趟做完待排序元素只剩下 1 个就不用再选了。 1. 简单选择排序
1算法思想与实现步骤
① 简单选择排序的基本思想是 简单选择排序通过不断选择未排序部分中的最小的元素将其放到已排序部分的末尾逐步构建出一个非递减有序的序列。
② 简单选择排序的实现步骤是 a从排序表的未排序部分 L[i…n] 找到最小元素。 b将找到的最小元素交换到已排序部分的末尾即 L( i ) 处每一趟排序可以确定一个元素的最终位置。 c标记已排序部分的边界继续对未排序部分重复步骤 a-b 。 d直到整个数组变为有序。
2算法的C代码
void SelectSort(ElemType A[], int n) {for(int iO; in-1; i){ // 一共进行n-1趟int min i; // 记录最小元素位置for(int ji1; jn; j){ // 在A[i…n-1]中选择最小的元素if(A[j] A[min]) {min j;} // 更新最小元素位置}if(min ! i) {swap(A[i], A[min]);} // 封装的swap()函数共移动元素 3 次}
}3示例 4算法的性能分析
① 时间复杂度与空间复杂度
I、空间效率仅使用常数个辅助单元故空间效率为 O(1) 。
II、时间效率在简单选择排序过程中元素移动的操作次数很少不会超过 3(n - 1) 次最好的情况是移动 0 次此时对应的表已经有序但元素间比较的次数与序列的初始状态无关始终是 n(n - 1) / 2 次因此时间复杂度始终是 O(n2) 。 【简单选择排序算法的比较次数为 O(n2)移动次数为 O(n) 。】
② 稳定性
在第 i 趟找到最小元素后和第 i 个元素交换可能会导致第 i 个元素与其含有相同关键字元素的相对位置发生改变。例如L {2, 2’, 1} 经过一趟排序后 L {1, 2’, 2}。因此简单选择排序是一种不稳定的排序方法。
③ 适用性
简单选择排序算法适用于顺序存储和链式存储的线性表以及关键字较少的情况。
2. 堆排序
1了解堆的定义
① 定义1一棵大根树小根树 是这样一棵树其中每个结点的值都大于小于或等于其子结点如果有子结点的话的值。在大根树或小根树中结点的子结点个数可以任意。
② 定义2一个大根堆小根堆既是大根树小根树也是完全二叉树。 因为堆是完全二叉树具有 n 个元素的堆的高度为 ⌈log2(n 1)⌉ 。因此如果能够在 O(height) 时间内完成插人和删除操作那么这些操作的复杂性为 O(log2n) 。
堆的定义如下n 个关键字序列 L [1…n] 称为堆当且仅当该序列满足 aL(i) L(2i) 且 L(i) L(2i 1) 或 bL(i) L(2i) 且 L(i) L(2i 1) 1 i ⌊n / 2⌋) 可以将堆视为一棵完全二叉树。
满足条件 a 的堆称为大根堆大顶堆大根堆的最大元素存放在根结点且其任意一个非根结点的值小于或等于其双亲结点值。满足条件 b 的堆称为小根堆小顶堆小根堆的定义刚好相反根结点是最小元素。
2大根堆的“上浮”和“下沉”
在大根堆中上浮操作Upward Sift 或 Bubble Up和下沉操作Downward Sift 或 Bubble Down是确保堆性质每个父结点的值大于或等于子结点的值得以维持的重要操作。
① “上浮”操作上浮操作用于在插入新元素后调整堆的结构确保大根堆的性质得以满足。 步骤自下而上 a将新插入的元素放在数组的末尾即堆的最后一个位置。 b从该新元素的位置开始检查其值是否大于其父结点的值。 c如果大于则与父结点交换位置。 d重复以上步骤直到达到根结点或堆的性质得以满足。
② “下沉”操作下沉操作用于在删除堆顶元素或在将堆的最后一个元素移到根结点后调整堆的结构确保大根堆的性质得以满足。 步骤自上而下 a将堆顶元素通常是最大值与最后一个元素交换位置。 b移除最后一个元素即原堆顶元素。 c从新根结点开始检查其值与左右子结点的值。 d若根结点小于任一子结点则与较大的子结点交换位置。 e重复以上步骤直到达到叶结点或堆的性质得以满足。
3大根堆的插入、初始化和删除操作
① 大根堆的插入 a添加元素将新元素添加到数组末尾堆的最后一个位置。 b上浮操作自下而上检查新插入元素是否满足大根堆的性质。 从新元素的位置开始若其值大于其父结点的值则交换两者继续向上比较直到满足大根堆的性质或到达根结点。 示例如下图所示在已经建好的大根堆中加入新元素 63 。 实现这种插入策略的时间复杂性为 O(height) O(log2n) 。
② 大根堆的删除通常删除堆顶元素 a替换根节点将堆顶最大值与最后一个元素交换。 b移除最后元素从堆中移除最后一个元素原堆顶。 c下沉操作自上而下从新根结点开始进行下沉调整。 比较新根结点与其子结点若其值小于任一子结点的值则与较大的子结点交换直到满足大根堆的性质。 示例如下图所示在已经建好的大根堆中删除堆顶元素 87 。 实现这种删除策略的时间复杂性为 O(height) O(log2n) 。
③ 大根堆的初始化 a创建数组使用数组来存储堆中的元素。 b构建堆将无序数组转换成大根堆通常采用“自下而上”的方法遍历所有的非叶结点从最后一个非叶结点开始索引为 ⌊(n / 2)⌋ n 为结点总数索引从 1 开始依次向上调整每个结点使其满足大根堆的性质。 c调整结点对每个结点调用“下沉”操作确保其大于或等于其子结点。 数组构建堆的过程可以分为两种 I、把数组元素逐个插入到一个空堆中这时需要用“上浮”操作来维护大根堆的性质【为了构建这个初始的非空堆我们需要在空堆中执行 n 次插入操作插入操作所需的总时间为 O(nlog2n) 】 II、更高效的做法是直接将一个无序数组转化为大根堆再依次调整结点这种方法称为“堆化”Heapify这时只需通过“下沉”操作便可完成初始化【用这种方法初始化堆的时间复杂度为 O(n) 】。 目前我们讨论的就是“堆化”的过程。 示例如下图所示初始数组序列为 {49, 38, 65, 97, 76, 13, 27, 49’} 在大根堆的初始化过程和删除操作中主要依赖“下沉”操作而大根堆的插入操作中可能会使用到“上浮”操作。 4算法思想与实现步骤
① 堆排序的基本思想是 堆排序利用堆这种数据结构的性质首先构建一个最大堆或最小堆然后反复将堆顶元素最大或最小取出并放入有序部分。
② 堆排序的实现步骤是 a将待排序数组 L[1…n] 中的 n 个元素构建成一个最大堆(或最小堆)。 b将堆顶元素与最后一个元素交换并从堆中移除堆顶元素。 c对剩余的元素调整为堆结构。 d重复步骤 b 和 c直到所有元素都有序直到堆中仅剩一个元素为止。
5算法的C代码
void BuildMaxHeap(ElemType A[],int len){for(int ilen/2; iO; i--){ // 从i[n/2]~1反复调整堆HeadAdjust(A, i, len);}
}
void HeadAdjust(ElemType A [], int k, int len) {
// 函数HeadAdjust将元素k为根的子树进行调整A[O] A[k]; // A[O]暂存子树的根结点for(int i2*k; ilen; i*2){ // 沿key较大的子结点向下筛选if(ilen A[i]A[il]) {i;} // 取key较大的子结点的下标if (A[0]A[i]) {break;} // 筛选结束else{A[k] A[i]; // 将A[i]调整到双亲结点上k i; // 修改k值以便继续向下筛选}}A[k] A[O]; // 被筛选结点的值放入最终位置
}
void HeapSort(ElemType A[], int len) {BuildMaxHeap(A, len); // 初始建堆for(int ilen; il; i--) { // n-1趟的交换和建堆过程Swap(A[i], A[1]); // 输出堆顶元素和堆底元素交换HeadAdjust(A, 1, i-1); // 调整把剩余的i-1个元素整理成堆}
}调整的时间与树高有关为 O(h) 。在建含 n 个元素的堆时关键字的比较总次数不超过 4n时间复杂度为 O(n) 这说明可以在线性时间内将一个无序数组建成一个堆。 6算法的性能分析 堆排序适合关键字较多的情况。例如在 1 亿个数中选出前 100 个最大值。首先使用一个大小为 100 的数组读入前 100 个数建立小顶堆而后依次读入余下的数若小于堆顶则舍弃否则用该数取代堆顶并重新调整堆待数据读取完毕堆中 100 个数即为所求。 ① 时间复杂度与空间复杂度
I、空间效率仅使用了常数个辅助单元所以空间复杂度为 O(1) 。
II、时间效率建堆时间为 O(n) 之后有 n - 1 次向下调整操作 每次调整的时间复杂度为 O(h)故在最好、最坏和平均情况下堆排序的时间复杂度为 O(nlog2n) 。
② 稳定性
进行筛选时有可能把后面相同关键字的元素调整到前面所以堆排序算法是一种不稳定的排序方法。
③ 适用性
堆排序仅适用于顺序存储的线性表。
3. 例题
① 【2009 统考真题】已知关键字序列 5, 8, 12, 19, 28, 20, 15, 22 是小根堆插入关键字 3调整好后得到的小根堆是 A 。 A. 3, 5, 12, 8, 28, 20, 15, 22, 19 B. 3, 5, 12, 19, 20, 15, 22, 8, 28 C. 3, 8, 12, 5, 20, 15, 22, 28, 19 D. 3, 12, 5, 8, 28, 20, 15, 22, 19
② 【2011 统考真题】已知序列 25, 13, 10, 12, 9 是大根堆在序列尾部插入新元素 18将其再调整为大根堆调整过程中元素之间进行的比较次数是 B 。 A. 1 B. 2 C. 4 D. 5
③ 【2015 统考真题】已知小根堆为 8, 15, 10, 21, 34, 16, 12删除关键字 8 之后需重建堆在此过程中关键字之间的比较次数是 C 。 A. 1 B. 2 C. 3 D. 4
④【2018 统考真题】在将序列 (6, 1, 5, 9, 8, 4, 7) 建成大根堆时正确的序列变化过程是 A 。 A. 6, 1, 7, 9, 8, 4, 5 -- 6, 9, 7, 1, 8, 4, 5 -- 9, 6, 7, 1, 8, 4, 5 -- 9, 8, 7, 1, 6, 4, 5 B. 6, 9, 5, 1, 8, 4, 7 -- 6, 9, 7, 1, 8, 4, 5 -- 9, 6, 7, 1, 8, 4, 5 -- 9, 8, 7, 1, 6, 4, 5 C. 6, 9, 5, 1, 8, 4, 7 -- 9, 6, 5, 1, 8, 4, 7 -- 9, 6 , 7, 1, 8, 4, 5 -- 9, 8, 7, 1, 6, 4, 5 D. 6, 1, 7, 9, 8, 4, 5 -- 7, 1, 6, 9, 8, 4, 5 -- 7, 9, 6, 1, 8, 4, 5 -- 9, 7, 6, 1, 8, 4, 5 -- 9, 8, 6, 1, 7, 4, 5
⑤ 【2020 统考真题】下列关于大根堆至少含 2 个元素的叙述中正确的是 C 。 I. 可以将堆视为一棵完全二叉树 II. 可以采用顺序存储方式保存堆 III. 可以将堆视为一棵二叉排序树 IV. 堆中的次大值一定在根的下一层 A. 仅 I 、II B. 仅 II 、III C. 仅 I 、II 和 IV D. I 、III 和 IV
⑥ 【2021 统考真题】将关键字 6, 9, 1, 5, 8, 4, 7 依次插入到初始为空的大根堆 H 中得到的 H 是 B 。 A. 9, 8, 7, 6, 5, 4, 1 B. 9, 8, 7, 5, 6, 1, 4 C. 9, 8, 7, 5, 6, 4, 1 D. 9, 6, 7, 5, 8, 4, 1 文章转载自： http://www.morning.spghj.cn.gov.cn.spghj.cn http://www.morning.btgxf.cn.gov.cn.btgxf.cn http://www.morning.hcxhz.cn.gov.cn.hcxhz.cn http://www.morning.ysbrz.cn.gov.cn.ysbrz.cn http://www.morning.fldk.cn.gov.cn.fldk.cn http://www.morning.ghkgl.cn.gov.cn.ghkgl.cn http://www.morning.lhsdf.cn.gov.cn.lhsdf.cn http://www.morning.hdrsr.cn.gov.cn.hdrsr.cn http://www.morning.qgjxy.cn.gov.cn.qgjxy.cn http://www.morning.nlgmr.cn.gov.cn.nlgmr.cn http://www.morning.xpzgg.cn.gov.cn.xpzgg.cn http://www.morning.hgsylxs.com.gov.cn.hgsylxs.com http://www.morning.plcyq.cn.gov.cn.plcyq.cn http://www.morning.hclqy.cn.gov.cn.hclqy.cn http://www.morning.jlthz.cn.gov.cn.jlthz.cn http://www.morning.trffl.cn.gov.cn.trffl.cn http://www.morning.jppb.cn.gov.cn.jppb.cn http://www.morning.djpps.cn.gov.cn.djpps.cn http://www.morning.cqyhdy.cn.gov.cn.cqyhdy.cn http://www.morning.yqqxj1.cn.gov.cn.yqqxj1.cn http://www.morning.tzjqm.cn.gov.cn.tzjqm.cn http://www.morning.ltrms.cn.gov.cn.ltrms.cn http://www.morning.ymwcs.cn.gov.cn.ymwcs.cn http://www.morning.mbhdl.cn.gov.cn.mbhdl.cn http://www.morning.rkkh.cn.gov.cn.rkkh.cn http://www.morning.yqkxr.cn.gov.cn.yqkxr.cn http://www.morning.fgwzl.cn.gov.cn.fgwzl.cn http://www.morning.qkqpy.cn.gov.cn.qkqpy.cn http://www.morning.qytyt.cn.gov.cn.qytyt.cn http://www.morning.tqjwx.cn.gov.cn.tqjwx.cn http://www.morning.cbchz.cn.gov.cn.cbchz.cn http://www.morning.yysqz.cn.gov.cn.yysqz.cn http://www.morning.hmmnb.cn.gov.cn.hmmnb.cn http://www.morning.lhrwy.cn.gov.cn.lhrwy.cn http://www.morning.nfyc.cn.gov.cn.nfyc.cn http://www.morning.pynzj.cn.gov.cn.pynzj.cn http://www.morning.pkpqh.cn.gov.cn.pkpqh.cn http://www.morning.qmncj.cn.gov.cn.qmncj.cn http://www.morning.qyxwy.cn.gov.cn.qyxwy.cn http://www.morning.hnhgb.cn.gov.cn.hnhgb.cn http://www.morning.lfqnk.cn.gov.cn.lfqnk.cn http://www.morning.lfdrq.cn.gov.cn.lfdrq.cn http://www.morning.gfkb.cn.gov.cn.gfkb.cn http://www.morning.mpngp.cn.gov.cn.mpngp.cn http://www.morning.ymrq.cn.gov.cn.ymrq.cn http://www.morning.stflb.cn.gov.cn.stflb.cn http://www.morning.xbdrc.cn.gov.cn.xbdrc.cn http://www.morning.fcwb.cn.gov.cn.fcwb.cn http://www.morning.bcjbm.cn.gov.cn.bcjbm.cn http://www.morning.nrbqf.cn.gov.cn.nrbqf.cn http://www.morning.hgsmz.cn.gov.cn.hgsmz.cn http://www.morning.knqck.cn.gov.cn.knqck.cn http://www.morning.npqps.cn.gov.cn.npqps.cn http://www.morning.rtlth.cn.gov.cn.rtlth.cn http://www.morning.rhmt.cn.gov.cn.rhmt.cn http://www.morning.hdzty.cn.gov.cn.hdzty.cn http://www.morning.tgxrm.cn.gov.cn.tgxrm.cn http://www.morning.qnklx.cn.gov.cn.qnklx.cn http://www.morning.qmfhh.cn.gov.cn.qmfhh.cn http://www.morning.hhqtq.cn.gov.cn.hhqtq.cn http://www.morning.rqbkc.cn.gov.cn.rqbkc.cn http://www.morning.xkzr.cn.gov.cn.xkzr.cn http://www.morning.rfbt.cn.gov.cn.rfbt.cn http://www.morning.hpdpp.cn.gov.cn.hpdpp.cn http://www.morning.bnylg.cn.gov.cn.bnylg.cn http://www.morning.kfyqd.cn.gov.cn.kfyqd.cn http://www.morning.kpqjr.cn.gov.cn.kpqjr.cn http://www.morning.ypktc.cn.gov.cn.ypktc.cn http://www.morning.fnrkh.cn.gov.cn.fnrkh.cn http://www.morning.yymlk.cn.gov.cn.yymlk.cn http://www.morning.khtyz.cn.gov.cn.khtyz.cn http://www.morning.jrplk.cn.gov.cn.jrplk.cn http://www.morning.rpfpx.cn.gov.cn.rpfpx.cn http://www.morning.trkhx.cn.gov.cn.trkhx.cn http://www.morning.yfstt.cn.gov.cn.yfstt.cn http://www.morning.kydrb.cn.gov.cn.kydrb.cn http://www.morning.kqpq.cn.gov.cn.kqpq.cn http://www.morning.glxmf.cn.gov.cn.glxmf.cn http://www.morning.rlqml.cn.gov.cn.rlqml.cn http://www.morning.gcbhh.cn.gov.cn.gcbhh.cn
