cosmos 项目中的选择排序（Selection Sort）：原理、复杂度分析与 9 种语言实现详解

教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载选择排序Selection Sort是 cosmos 项目中收录的最基础排序算法之一它是一种原地in-place、基于比较的简单排序算法。本指南以 关联文档 为核心骨架结合仓库内 9 种语言的真实实现源码完整讲解选择排序的分区思想、工作过程、伪代码、复杂度边界以及如何在 C、C、Python、Java、Go、Rust、JavaScript、Swift、Shell 中编写、运行和验证它帮助你建立起算法原理 — 复杂度分析 — 多语言落地的完整闭环。算法原理已排序区与未排序区的两分法选择排序的核心思想非常直观把列表在逻辑上划分为两个部分——左端的已排序区sorted part和右端的未排序区unsorted part。初始时已排序区为空整个列表都属于未排序区。算法的每一步执行如下操作在未排序区中扫描并选出最小元素将它与未排序区的最左端元素交换交换完成后该元素即并入已排序区未排序区的边界随之向右移动一个位置。重复上述过程直到未排序区只剩一个元素为止。整个过程像一条边界线从左向右推进左边永远是已就位的元素右边永远是待处理的元素。由于所有操作都在原数组上通过交换完成因此它是一个原地排序算法不需要额外的大块存储空间。原文档明确指出了该算法的适用边界选择排序不适合处理大型数据集因为它的平均和最坏情况复杂度均为Ο(n·n) O(n²)其中 n 为元素个数。工作过程演示从 [7 5 4 2] 到 [2 4 5 7]原文档给出的输入输出示例为输入[7 5 4 2]输出[2 4 5 7]下面按轮次拆解其完整执行过程每轮交换后边界左侧即已排序区轮次未排序区找到的最小值交换操作数组状态初始[7 5 4 2]——[7 5 4 2]第 1 轮[7 5 4 2]2末位交换 7 与 2[2 5 4 7]第 2 轮[5 4 7]4交换 5 与 4[2 4 5 7]第 3 轮[5 7]5已就位无需交换[2 4 5 7]完成———[2 4 5 7]可以看到每轮结束后至少有一个元素落到最终位置n 个元素最多需要 n−1 轮即可完全有序。算法伪代码原文档给出的伪代码如下它是后续所有语言实现的母本SelectionSort(A): for j ← 1 to n-1 smallest ← j for i ← j 1 to n if A[i] A[smallest] smallest ← i Swap A[j] ↔ A[smallest]外层循环j负责推进已排序区边界内层循环i在未排序区[j1, n]中寻找最小值下标最后将最小值交换到位置j。注意伪代码中的下标从 1 开始而实际编程语言除个别外通常从 0 开始因此真实实现中外层循环一般是for i in 0..n-2。复杂度分析选择排序是少数输入无关的排序算法之一——无论数据初始是否有序它都必须完整扫描未排序区来确认最小值因此其复杂度不随输入分布改变。时间复杂度情形复杂度说明最坏情况O(n²)比较次数恒为 n(n−1)/2平均情况Θ(n²)与最坏情况相同的比较次数最好情况Ω(n²)即使数组已有序仍需扫描全部未排序区空间复杂度O(1)辅助空间。除少数临时变量记录最小值下标、交换用的临时量外不需要额外数组属于典型的原地排序。交换次数是选择排序的一大优点每轮最多一次交换总计最多n−1次交换。这一点在写操作代价高昂的场景例如交换大对象或写入慢速存储中选择排序比冒泡排序O(n²) 次交换有明显优势。从稳定性角度看标准选择排序不稳定当存在重复元素时把远端的较小元素直接交换到已排序区末尾可能越过与其相等的元素从而改变相等元素的相对次序仓库中各语言实现均未做稳定性处理可从 selection_sort.py 等源码中的直接交换逻辑推断。仓库源码级实现纵览cosmos 仓库在 code/sorting/src/selection_sort 目录下提供了多达 9 种语言的实现覆盖了从脚本语言到系统级语言的完整谱系。逐一分析如下。Python最贴近伪代码的教科书实现selection_sort.py 用 10 行代码完整复现了伪代码逻辑def selection_sort(array): for i in range(len(array) - 1): minimumValue i for j in range(i 1, len(array)): if array[j] array[minimumValue]: minimumValue j temp array[minimumValue] array[minimumValue] array[i] array[i] temp return array实现要点外层循环到len(array) - 1即可最后一个元素无需再比较内层循环从i 1开始只记录最小值的下标而非值本身最后通过三行临时变量完成原地交换。函数原地修改并返回原列表。C支持升序与降序双模式selection_sort.c 是仓库中功能最完整的实现之一它通过order参数同时支持两种排序方向order 1升序每轮在未排序区寻找最小元素第 22-37 行order 0降序每轮在未排序区寻找最大元素第 38-54 行其他取值输出Undefined sorting order并拒绝执行第 55-58 行。程序在main()中通过scanf依次读取元素个数、数组元素与排序方向并额外做了一次输入合法性校验第 93-97 行。编译运行方式gcc selection_sort.c -o selection_sort ./selection_sort # 依次输入元素个数、数组元素、排序方向1 升序 / 0 降序C模板 迭代器 自定义比较器selection_sort.cpp 用现代 C 泛型编程重写了该算法支持任意迭代器区间与自定义比较函数templatetypename _Input_Iter, typename _Compare void selectionSort(_Input_Iter begin, _Input_Iter end, _Compare compare) { if (begin ! end) for (auto curr begin; curr ! end; curr) { auto minimum curr; auto forward curr; while (forward ! end) if (compare(*forward, *minimum)) minimum forward; std::iter_swap(minimum, curr); } }同时提供了一个便捷重载第 34-41 行默认使用std::less按升序排序使用者无需关心迭代器与比较器的细节。这套接口设计与 C 标准库算法风格一致可直接作用于std::vector、std::list等容器的迭代器区间。编译方式g -stdc11 selection_sort.cpp -o selection_sort_cppJava类封装 main 示例selection_sort.java 将算法封装为SelectionSort类的静态方法sort(int[] arr)并在main中给出了可直接运行的示例int[] arr { 1, 5, 2, 5, 2, 9, 7 }; SelectionSort.sort(arr); System.out.print(java.util.Arrays.toString(arr));sort方法同样采用记录最小值下标 交换的模式私有静态方法swap负责元素交换。运行方式javac selection_sort.java java SelectionSortGo 与 Rust语言惯用法示例selection_sort.go 展示了 Go 的多重赋值交换语法array[i], array[min] array[min], array[i]第 15 行该实现针对固定长度数组[8]int编写示例数据为{5, 6, 1, 2, 7, 9, 8, 4}go run selection_sort.goselection_sort.rs 使用Veci32与内置的arr.swap(i, min)方法并额外加了if min ! i守卫避免同位置自我交换的无谓开销第 12-14 行rustc selection_sort.rs ./selection_sortJavaScript 与 Swift前端与 iOS 场景selection_sort.js 是纯函数式实现selectionSort(inputArray)原地排序并返回数组同样包含minAt ! i的交换守卫node selection_sort.jsSwift 仓库中提供了两个文件selection_sort.swift 是基于inout参数的函数版本selection_sort_extension.swift 则更进一步通过extension Array把选择排序挂载为数组的成员方法并支持泛型比较器闭包extension Array { mutating func selectionSort(compareWith less: (Element, Element) - Bool) { for i in 0..self.count { var min i for j in i 1..self.count { if less(self[j], self[min]) { min j } } swap(self, at: min, and: i) } } }这使得任意Element类型数组都能通过传入比较闭包来决定排序方向与 C 版的自定义比较器设计思路异曲同工。Shell带自校验的 Bash 实现selection_sort.sh 是一份完整的 Bash 脚本值得关注的是它不仅实现了算法还包含了完整的测试与验证闭环create_array()用$RANDOM生成 10 个随机数填充数组print_array()打印数组内容verify_sort()逐对检查相邻元素是否满足升序不满足则报错退出第 22-32 行selection_sort()标准的选择排序实现交换前同样有minIdx -ne $i守卫。运行方式bash selection_sort.sh # 输出排序前数组 → 排序后数组 → Array sorted correctly.verify_sort提供的思路可以推广到任意语言排序后增加一遍线性校验是单元测试之外最简单有效的正确性保障。与仓库其他排序算法的横向定位cosmos 的 code/sorting/src 目录收录了 300 个排序相关源文件含多种语言的各类排序算法实现与文档。在 O(n²) 级别的简单排序家族中选择排序的定位非常清晰相比冒泡排序交换次数从 O(n²) 降为O(n)但比较次数相同相比插入排序插入排序对近似有序数据有天然的适应性最好 O(n)而选择排序不具备这种适应性无论输入如何都要完整扫描选择排序的价值在于实现极简、交换开销可控、原地完成适合教学演示、元素交换代价高昂、或数据量较小如 n 数百的场景。小结本文完整继承并深化了 选择排序文档 的全部核心内容两分区思想、[7 5 4 2] → [2 4 5 7] 的分步演示、标准伪代码、O(n²)/O(1) 的时空复杂度边界并进一步结合仓库内 9 种语言的真实实现Python、C、C、Java、Go、Rust、JavaScript、Swift 与 Shell剖析了升序/降序双模式、自定义比较器、泛型扩展、自我校验等进阶用法。对于数据量小、追求实现简洁与交换次数可控的场景选择排序依然是值得熟练掌握的入门级排序利器。赞分享教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载相关推荐Hello 算法选择排序Selection Sort原理图解、多语言实现与复杂度剖析Hello 算法选择排序Selection Sort原理图解、多语言实现与复杂度剖析 选择排序是最直观的一类排序算法每一轮从未排序区间中挑出最小元素放教程文档示例工程教育OI-wiki 选择排序Selection Sort详解原理、稳定性分析与多种语言实现OI wiki 选择排序Selection Sort详解原理、稳定性分析与多种语言实现 选择排序是一种简单直观的基于比较的排序算法也是 OI / ICP文档知识库教育教程Cosmos 项目中的 Pigeonhole Sort鸽巢排序原理、复杂度与多语言实现详解Cosmos 项目中的 Pigeonhole Sort鸽巢排序原理、复杂度与多语言实现详解 导读 本文以 OpenGenus Cosmos 仓库中 pig教程示例工程上一篇kfyty725/loveqq-framework的属性源CompositePropertySource配置下一篇深入解析 sqlc 的 AST 工具包Walk、Apply、Search 与 Join 的遍历与重写机制创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考