YCBlogs算法笔记：选择排序深度解析——直接选择排序与树形锦标赛排序原理及Java实现

教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载选择排序是一类以每轮从未排序区间选出极值并归位为核心的排序方法YCBlogs 仓库的 选择排序笔记 系统地梳理了它的三种形态直接选择排序、树形选择排序锦标赛排序与堆排序。本文以该笔记为骨架完整保留其中两段可运行的 Java 实现并补充逐行代码解析、复杂度推导、稳定性辨析与优化思路帮助读者彻底理解选择排序家族为后续阅读堆排序等进阶笔记打好基础。1. 选择排序的种类划分根据 选择排序笔记 的总结选择排序并不是单一算法而是一族算法的统称共分三种种类别称核心手段稳定性直接选择排序简单选择排序线性扫描找极值逐个交换归位不稳定树形选择排序锦标赛排序借助满二叉树两两比较选出极值稳定堆排序大根堆 / 小根堆排序借助堆结构在 O(logn) 内取极值不稳定这一划分也印证在仓库 排序算法总览 中选择排序 — O(n²)被明确归入不稳定排序一组。三者的演进关系可以概括为一条优化主线直接选择排序每轮要用 O(n) 的时间线性扫描找最小值树形选择排序用一棵满二叉树把找最小值的代价分摊到建树与比较上堆排序进一步复用树形结构把比较信息压缩进一个数组省去了 O(n) 的辅助空间。以下分别深入直接选择排序与树形选择排序堆排序的完整代码与思想可移步 堆排序笔记 查阅。2. 直接选择排序2.1 基本思想在长度为 N 的无序数组中第一次遍历 n-1 个数找到最小的数值与第一个元素交换第二次遍历 n-2 个数找到最小的数值与第二个元素交换依此类推……第 n-1 次遍历找到最小的数值与第 n-1 个元素交换排序完成。核心要点在于每一轮扫描只做查找不立刻交换只有找到本轮区间内的最小值后才把它与区间起点做一次交换。这与冒泡排序相邻两两比较、随时交换的行为有本质区别也是选择排序交换次数远少于冒泡的原因。2.2 排序过程哨位机制笔记中用哨位哨兵来描述扫描游标通过设置哨位将哨位位置的数与哨位之后包括哨位的序列中最小的数进行交换然后哨位递增直到哨位到达数组中最后一个数为止。以数组[5, 3, 8, 6, 4]升序排序为例逐步走一遍第 1 轮哨位指向下标 0值 5扫描下标 14 找出最小值 3下标 1交换5与3→[3, 5, 8, 6, 4]下标 0 归位第 2 轮哨位指向下标 1值 5扫描下标 24 找出最小值 4下标 4交换 →[3, 4, 8, 6, 5]下标 1 归位第 3 轮哨位指向下标 2值 8扫描下标 34 找出最小值 5下标 4交换 →[3, 4, 5, 6, 8]下标 2 归位第 4 轮哨位指向下标 3值 6扫描下标 4 仅剩8最小值即自身无需交换第 5 轮哨位指向下标 4区间仅剩一个元素自动就位排序结束。可见每轮哨位左侧是已就位的有序区右侧是待排序区当哨位走到数组末尾时全部元素归位。2.3 代码实现笔记给出的完整实现如下selectSort1我补充了逐行注释/* * 直接选择排序 */ public static void selectSort1(int[] data) { int pos; // 外层循环控制哨位i 即当前待归位的位置 for (int i 0; i data.length; i) { pos i; // 哨位假设当前区间最小元素就在 i 处 // 内层循环找出从 i 开始到数组末尾这段区间中最小的数 // pos 记录这个最小数在数组中的位置 for (int j i 1; j data.length; j) { if (data[j] data[pos]) { pos j; } } // 交换两个数的位置只有当最小值不在 i 处时才需要交换 if (pos ! i) { int temp data[i]; data[i] data[pos]; data[pos] temp; } } for (int i 0; i data.length; i) { System.out.println(yc1----- data[i]); } }几个值得注意的实现细节pos变量是哨位机制在代码层面的化身内层循环结束时pos指向区间最小值的下标交换后data[i]即为第 i 小的元素if (pos ! i)的交换前置判断当最小值本来就在哨位位置时跳过交换避免无意义的写操作也使得已经有序的数组全程零交换外层循环上限代码写成i data.length实际只需i data.length - 1即可——最后一个元素在倒数第二轮结束后必然就位这里多出一轮自查并不影响正确性属于可接受的写法。2.4 复杂度分析直接选择排序的时间复杂度与输入数据的初始顺序完全无关最好 / 最坏 / 平均时间复杂度均为 O(n²)因为无论数组是否已经有序内层循环都必须完整扫描剩余区间去确认最小值。总比较次数为固定的(n-1) (n-2) … 1 n(n-1)/2即笔记中所说即使数组一开始就是正序的也需要将两重循环进行完交换次数最多n-1次每轮至多一次交换是选择排序相比冒泡在写操作上的显著优势空间复杂度 O(1)仅使用pos、temp两个临时变量属于原地排序In-place sort不占用多余空间。2.5 稳定性辨析重要这里需要特别指出 选择排序笔记 中一处前后不一致的表述笔记第 0 节明确写道直接选择排序和堆排序是不稳定排序而笔记 1.4 节又写到直接选择排序是一种原地排序并且稳定stable sort的排序算法。两者矛盾。结合 排序算法总览 将选择排序 — O(n²)列入不稳定排序的分类可以确认第 0 节的结论是正确的1.4 节中的稳定应视为笔误。直接选择排序不稳定的原因可以用一个经典反例说明数组[3a, 3b, 1]3a、3b为两个相等的 3用于区分相对次序第一轮找到最小值1与下标 0 的3a交换得到[1, 3b, 3a]——原本在前面的3a被交换到了3b之后两个相等元素的相对顺序被破坏因此算法不稳定。2.6 如何优化笔记原文档在如何优化一节只给出了复杂度说明这里基于算法原理补充三类常见优化双向选择二元选择排序每一轮同时扫描找出区间内的最小值和最大值分别放到区间的首尾这样每轮可以让两个元素归位外层循环次数减半总比较次数约降低 50%但时间复杂度量级仍为 O(n²)保持先找后换策略像selectSort1那样先记录pos再一次性交换避免像某些实现那样边扫描边交换造成无谓的写操作注意与冒泡的区别冒泡排序可以通过本轮无交换即提前终止的标志位见 冒泡排序笔记 中的flag优化处理近似有序数组但选择排序的内层扫描是强制的不存在这种提前退出机制——这也是选择排序在近乎有序数据上表现不如插入、冒泡的原因。2.7 使用场景小规模数据排序当数据量很小如几十到几百个元素时O(n²) 的代价可接受且实现简单、不易出错对写操作敏感的场景选择排序最多 n-1 次交换在交换代价远高于比较代价如交换的是大对象引用之外的重量级数据的环境下有相对优势教学与面试基础选择排序是理解有序区 / 无序区划分、稳定性概念与复杂度分析的入门算法也是面试中手写排序的基础题。3. 树形选择排序锦标赛排序3.1 基本思想树形选择排序利用满二叉树的性质将待排序的数放入叶子节点中同属于一个根节点的两个叶子节点相互比较较小的叶子节点复制到其根节点根节点之间再相互比较直到整棵树的根节点。此时整棵树的根节点就是待排序数组中最小的一个数。下一次循环中要将这个数置为最大值然后再开始循环直到全部的数都被取出排序完成。因为这种两两比较、胜者晋级的过程与体育比赛中的淘汰赛完全一致所以又称锦标赛排序。它相对直接选择排序的进步在于比较结果被树结构保存下来每轮选出最小值后只需沿冠军所在的路径向上重新比较就能复用其他节点的既有比较结果而不是像直接选择排序那样每轮把整个区间重新扫一遍。3.2 排序过程笔记总结为三步构造满二叉树要求可以将待排序数组全部放入叶子节点中若元素个数不是 2 的幂补充∞哨兵节点使树成为满二叉树自底向上比较将两个叶子节点中较小的数挪入其根节点全部挪完后再将两个根节点中较小的数挪入它们的根节点……直到整棵树的根节点。此时树根保存的是全局最小值取出并重赛取出根节点中的数即当前最小值将其对应叶子节点中的数置为最大值表示已出局然后重复第 2 步的比较过程直到每个数都被取出过一次。以n个元素为例叶子节点数为n加上逐层合并的内部节点完全二叉树的节点总数为2n - 1——这也是下文代码中treeSize 2 * len - 1的由来。3.3 代码实现笔记给出的完整实现如下treeSelectSort并补充了关键注释public static void treeSelectSort(int[] a) { int len a.length; int treeSize 2 * len - 1; // 完全二叉树的节点数 int low 0; int[] tree new int[treeSize]; // 临时的树存储空间 // 由后向前填充此树索引从 0 开始 for (int i len - 1, j 0; i 0; --i, j) { // 填充叶子节点 tree[treeSize - 1 - j] a[i]; } for (int i treeSize - 1; i 0; i - 2) { // 填充非终端节点 // 两个子节点中较小的复制到父节点 tree[(i - 1) / 2] ((Comparable) tree[i - 1]).compareTo(tree[i]) 0 ? tree[i - 1] : tree[i]; } // 不断移走最小节点 int minIndex; while (low len) { int min tree[0]; // 树根即当前最小值 a[low] min; minIndex treeSize - 1; // 找到最小值的索引从最后一个叶子向前扫描定位值等于 min 的叶子 while (((Comparable) tree[minIndex]).compareTo(min) ! 0) { minIndex--; } tree[minIndex] Integer.MAX_VALUE; // 设置一个最大值标志表示该元素已出局 // 找到其兄弟节点并沿路径向上重新比较、更新父节点 while (minIndex 0) { // 如果其还有父节点 if (minIndex % 2 0) { // 如果是右节点 tree[(minIndex - 1) / 2] ((Comparable) tree[minIndex - 1]).compareTo(tree[minIndex]) 0 ? tree[minIndex - 1] : tree[minIndex]; minIndex (minIndex - 1) / 2; } else { // 如果是左节点 tree[minIndex / 2] ((Comparable) tree[minIndex]).compareTo(tree[minIndex 1]) 0 ? tree[minIndex] : tree[minIndex 1]; minIndex minIndex / 2; } } } for (int i 0; i a.length; i) { System.out.println(yc1----- a[i]); } }这段代码的四个阶段分别对应排序过程的每一步填充叶子tree[treeSize - 1 - j] a[i]把原数组a逆序填入树的末段即全部叶子节点建树for (int i treeSize - 1; i 0; i - 2)从最后一对叶子开始每次比较兄弟节点tree[i-1]与tree[i]把较小者写入父节点tree[(i-1)/2]自底向上完成全部内部节点的填充取出最小值min tree[0]直接读取树根写入结果数组a[low]随后从最后一个叶子向前扫描找到等于min的叶子下标minIndex将其置为Integer.MAX_VALUE出局标志沿路径重赛从minIndex出发根据左右子节点判定父节点下标右节点(minIndex-1)/2左节点minIndex/2比较兄弟节点后把较小者写回父节点并沿树向上迭代直到更新完树根得到下一轮的最小值。需要注意tree数组在构造时是int[]而比较通过((Comparable) ...)强制转换完成因此该方法要求待排序数组的元素类型实现了Comparable接口如包装类型Integer排序结果按自然顺序升序输出Integer.MAX_VALUE作为已出局标志也意味着该实现不适用于包含Integer.MAX_VALUE的原始数据。3.4 复杂度与空间代价从算法设计原理看树形选择排序建树阶段比较次数为n-1时间复杂度 O(n)每轮取最小值树根即最小值读取为 O(1)由于只有出局叶子所在的一条路径需要重新比较沿路径向上更新至多 O(logn) 层。因此理论时间复杂度为O(nlogn)相比直接选择排序的 O(n²) 是质的提升空间复杂度 O(n)需要额外的2n-1大小的树数组这是它相对堆排序空间 O(1)的主要劣势。这里需要指出仓库中该实现的一个可改进点while (((Comparable) tree[minIndex]).compareTo(min) ! 0) { minIndex--; }采用从最后一个叶子向前线性扫描的方式定位出局元素的叶子下标当数组存在大量重复的最小值时最坏情况下每次都要扫描 O(n) 个叶子整体复杂度会退化为 O(n²)。从代码结构可以推断更优的做法是在建树与向上更新时同步记录最小值对应的叶子索引把定位操作从 O(n) 降到 O(logn)从而使实现稳定保持在理论复杂度 O(nlogn)。3.5 从锦标赛排序到堆排序树形选择排序虽然把时间复杂度降到了 O(nlogn)却付出了 O(n) 辅助空间的代价且需要出局标志参与比较工程实现繁琐。堆排序正是对它的进一步改良将完整二叉树压缩为隐式二叉堆用数组下标关系parent (i-1)/2、left 2i1表达父子关系无需额外树空间每次从堆顶取出极值后用一次自顶向下的下沉调整O(logn)恢复堆性质最终实现O(nlogn) 时间、O(1) 空间的原地排序。大根堆 / 小根堆的完整实现与max_heap调整代码可查阅 堆排序笔记。4. 三种选择排序综合对比对比维度直接选择排序树形选择排序锦标赛堆排序最好时间复杂度O(n²)O(nlogn)O(nlogn)最坏时间复杂度O(n²)O(nlogn)O(nlogn)平均时间复杂度O(n²)O(nlogn)O(nlogn)空间复杂度O(1)O(n)额外树数组O(1)是否原地排序是否是稳定性不稳定稳定不稳定交换次数最多 n-1 次—写树数组—堆顶交换实现复杂度简单较复杂中等适用场景小规模数据、面试手写教学理解比较信息复用大数据量、top-k、优先队列其中稳定性的依据分别来自 选择排序笔记 第 0 节与 排序算法总览 的分类选择排序、堆排序为不稳定排序树形选择排序为稳定排序复杂度数据基于上述算法原理推导可直接与 冒泡排序笔记O(n²)、快速排序笔记平均 O(nlogn)等 O(n²)/O(nlogn) 家族成员横向对比。5. 延伸阅读围绕排序算法YCBlogs 仓库还提供了同一系列的对比笔记与实现建议按以下顺序串联阅读排序算法总览稳定 / 不稳定排序的整体分类与复杂度速查冒泡排序笔记同属 O(n²) 的相邻交换排序含flag提前终止优化插入排序笔记对近似有序数据表现更好的 O(n²) 排序常作为快排小区间优化的搭档选择排序笔记本文主体直接选择排序 锦标赛排序希尔排序笔记插入排序的增量分组改进不稳定但可逼近 O(nlogn)归并排序笔记稳定的 O(nlogn) 分治排序需 O(n) 额外空间堆排序笔记选择排序家族的终极形态大根堆 / 小根堆实现快速排序笔记工程中最常用的分治排序含三数取中、尾递归等优化策略。本文涉及的代码均出自上述笔记原文可直接复制运行selectSort1与treeSelectSort均可用于整型数组升序排序若要验证输出结果只需将方法末尾的System.out.println打印循环替换为Arrays.toString(data)即可。赞分享教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载相关推荐OI-wiki 锦标赛排序Tournament Sort详解树形选择排序的原理、复杂度与双语言实现OI wiki 锦标赛排序Tournament Sort详解树形选择排序的原理、复杂度与双语言实现 锦标赛排序Tournament sort又称树形选文档知识库教育教程Indoor3D5分钟打造沉浸式室内3D地图的完整指南Indoor3D5分钟打造沉浸式室内3D地图的完整指南 在大型购物中心迷失方向、在办公楼找不到会议室、在医院焦急寻找诊室——这些困扰现代都市人的痛点现在有了教程codeforces-go中的排序选择排序实现codeforces go中的排序选择排序实现 在算法竞赛中排序算法是处理数据的基础工具。本文将聚焦于 codeforces go 项目中的选择排序实现帮科学计算创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考