Cosmos 仓库中的 Circle Sort 环形排序算法：原理、伪代码与八种语言实现解析

教程示例工程【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址https://gitcode.com/gh_mirrors/co/cosmos点击查看免费下载Circle Sort环形排序是一种基于环形两两比较思想的原址in-place排序算法它把数组想象成一系列同心圆先比较位于同一圆上、呈中心对称的两个元素首尾配对、次首尾配对……再递归地对左右两半重复同样的过程直到某轮遍历不再发生任何交换为止。本文以 code/sorting/src/circle_sort/README.md 为骨架结合 Cosmos 仓库中 C、C、Java、C#、Python、JavaScript、Swift、Objective-C 八种语言的真实实现完整讲解该算法的核心思想、伪代码、边界处理与时间复杂度读完即可看懂并复现任意语言的 Circle Sort。算法核心思想把数组画成同心圆Circle Sort 最直观的解释方式是在整数数组上画同心圆把待排序数组的首尾元素看成最外层圆上直径相对的两个点依次把第 2 个元素与倒数第 2 个元素、第 3 个元素与倒数第 3 个元素……看成同一圆上相对的点对每一对位于同一圆上的元素进行比较若顺序错误则交换左大右小就交换一趟完整比较结束后把数组从中间一分为二对左右两个子数组分别递归执行同样的过程递归到无法再拆分为止再从最内层回退外层循环反复执行上述过程直到一整趟比较中没有任何交换发生数组即已有序。原始 README 中配有一张示意同心圆配对的示意图图片引自 geeksforgeeks不属于本仓库内容此处不再引用。核心要点在于每趟扫描本质上是同时做多组对称配对的比较-交换一轮下来较大的元素向右侧末尾移动、较小的元素向左侧开头移动从而把一趟冒泡的收敛速度放大为多组配对同时收敛。算法伪代码继承自 README原文档给出了两层伪代码内层inner_circle负责一趟同心圆比较-交换 递归分裂外层circle_sort负责循环驱动直到不再有交换function inner_circle (index a, index b) { start : a end : b swap : 0 if (start end) return (swap) while (start end) if (value at start value at end) swap.values(start , end) swap (end if) start end-- (end while) swap inner_circle (a, end) swap inner_circle (start, b) return(swap) } function circle_sort (index a, n) { while inner_circle (a, a n - 1) }对伪代码的逐行解读如下while (start end)首尾指针相向而行每次比较a[start]与a[end]这对对称点左大右小则交换并计数swap inner_circle (a, end)一趟扫描结束后左半部分递归此时右边界为上一趟的end两指针相遇位置或偏左一格swap inner_circle (start, b)右半部分递归左边界为上一趟的startwhile inner_circle (...)驱动循环只要某趟递归返回的交换次数不为 0就说明数组仍未完全有序需要再跑一整轮。这正是 Circle Sort多趟收敛特征的来源。从伪代码到真实实现仓库源码级剖析Cosmos 仓库在 code/sorting/src/circle_sort/ 目录下提供了 8 种语言的实现文件所有实现都严格遵循同一套逻辑可作为对照阅读的范本语言文件备注Ccircle_sort.c带mainscanf交互输入Ccircle_sort.cpp带mainscanf交互输入Pythoncircle_sort.py硬编码测试数组[6, 5, 3, 1, 8, 7, 2, 4]打印每步交换Javacircle_sort.java双重载Sort含含负数测试用例C#circle_sort.cs与 Java 版结构完全对应JavaScriptcircle_sort.js参考 Rosetta Code 改写循环打印中间结果Swiftcircle_sort.swift递归返回Bool是否发生交换Objective-Ccircle_sort.m基于NSMutableArray随机数据驱动递归函数签名与三要素以 circle_sort.c 为例递归函数的签名是int circle_sort(int *a, int n, int lower, int upper, int swaps)它包含三个关键要素终止条件base caseif (lower upper) return swaps;—— 当区间收缩为单元素时直接返回不再比较一趟对称比较while (lower upper)内完成首尾配对比较与交换奇偶长度边界if (lower upper) if (a[lower] a[upper 1]) ...—— 当区间长度为奇数时两指针会同时停在正中间的元素上lower upper此时需要把中间元素与它右侧相邻元素即右半区的第一个元素再比较一次。这是 Circle Sort 最容易被忽略的细节少了这一步奇数长度数组无法完全有序左右递归circle_sort(a, n, low, low mid, swaps)与circle_sort(a, n, low mid 1, high, swaps)其中mid (upper - lower) / 2。外层驱动循环的两种写法不同语言的实现对外层反复扫描直到无交换采用了两种等价写法计数法C/C/Java/C#外层循环判断inner返回的交换次数是否为 0。例如 Java 版的入口while (Sort(array, 0, array.length - 1, 0) ! 0);布尔法Swift/Objective-C递归函数直接返回本趟是否发生过交换外层while判断布尔值。例如 circle_sort.swiftfunc circleSort(_ array: inout [Int]) { while circleSort(array, low: 0, high: array.count - 1) {} }布尔法在递归返回时用swapped || left || right汇总左半、右半、本层三处是否发生交换语义更清晰也避免了交换计数在多语言int传值语义下需要逐层回传的问题。一处值得注意的差异C/C/Java/C#/JavaScript 的偶数长度实现直接复用while退出后的指针状态判断lo hi而 Swift/Objective-C 额外加了l 1 array.count的越界保护。从源码结构看前者隐含假设调用时hi n - 1最大合法下标后者则更谨慎地防御了边界访问移植到其他语言时可作为参考。复杂度分析README 给出的时间复杂度结论为最好情况O(n log n)—— 若数组接近有序外层while只需很少几趟每趟的递归深度为 log n最坏情况O(n log n log n)—— 每趟扫描本身是 O(n)递归分裂的深度为 log n而外层可能需要的完整趟数在最坏情况下也达到 log n 量级因此相乘得到 O(n log² n)。空间复杂度为 O(log n)来自递归调用的栈深度属于原址排序不依赖额外数组。需要说明的是README 中的复杂度结论是算法层面的经验性表述Circle Sort 在实践中主要作为教学型排序算法出现工程上通常优先选择复杂度更稳定的归并排序或快速排序本仓库 sorting 目录下收录了 300 个排序实现文件可供横向对比。运行与验证交互式运行C/Ccircle_sort.c 与 circle_sort.cpp 均以交互方式运行先输入数组长度n再逐个输入元素# C 版 gcc circle_sort.c -o circle_sort ./circle_sort # C 版 g circle_sort.cpp -o circle_sort_cpp ./circle_sort_cpp程序会依次打印Unsorted List:与Sorted List:两行结果。脚本语言直接运行Pythoncircle_sort.py 内置测试数组[6, 5, 3, 1, 8, 7, 2, 4]且每次发生交换都会打印数组当前状态与累计交换次数非常适合观察同心圆配对的收敛过程python3 circle_sort.pyJavaScriptcircle_sort.js 使用while (circlesort(...))驱动并打印每一趟的中间结果node circle_sort.jsSwift / Objective-C 版本分别需要swift circle_sort.swift与 Xcode/Clang 的 Foundation 环境Objective-C 版使用arc4random() % 100 - 50生成 30 个 [-50, 49] 的随机整数作为输入。Java / C#Java 与 C# 版直接内置了含负数的测试用例{2, 14, 4, 6, 8, 1, 5, 3, 7, 11, 0, 13, 20, -1}编译运行后即可在控制台看到排序结果无需手动输入。手工推演示例以 Python 版测试数组[6, 5, 3, 1, 8, 7, 2, 4]n 8为例推演第一趟外层圆index 0 vs 76 4交换 →[4, 5, 3, 1, 8, 7, 2, 6]内层圆index 1 vs 65 2交换 →[4, 2, 3, 1, 8, 7, 5, 6]index 2 vs 53 7不交换index 3 vs 41 8不交换两指针相遇后不再满足lower upper本趟配对结束随后对左右各 4 个元素递归执行同样的对称比较。可以看到一趟扫描就把最大值 8 推到了右半区、把最小值 1 推到了左半区边缘——这就是一圈扫描 多组冒泡同时进行的效果。适用场景与局限从实现特征可以总结出 Circle Sort 的适用边界适合教学演示对称比较 分治递归的排序思想数据规模较小、对空间敏感要求原址的场景作为理解反复扫描直到无交换这类循环不变式的好例子不适合大数据量工程排序最坏 O(n log² n) 劣于归并/堆排序、需要稳定排序比较交换不保证相等元素相对顺序、以及对最坏复杂度有硬性要求的系统。若想对比同目录下的其他排序算法可继续阅读 code/sorting/src/ 下的 README 与各类实现仓库根目录的 README.md 也给出了整个 Cosmos 算法代码库的组织结构便于按分类检索更多算法。赞分享教程示例工程【免费下载链接】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原理图解、多语言实现与复杂度剖析 选择排序是最直观的一类排序算法每一轮从未排序区间中挑出最小元素放教程文档示例工程教育Hello 算法中冒泡排序的实现原理、效率优化与多语言代码解析Hello 算法中冒泡排序的实现原理、效率优化与多语言代码解析 冒泡排序bubble sort通过连续地比较与交换相邻元素实现排序这个过程就像气泡从底部升教程文档示例工程教育Hello 算法桶排序Bucket Sort原理、代码实现与均匀分桶策略详解Hello 算法桶排序Bucket Sort原理、代码实现与均匀分桶策略详解 桶排序Bucket Sort是《Hello 算法》hello algo教程文档示例工程教育上一篇如何快速安装和配置Ka-Block!5分钟搞定Safari广告拦截下一篇【亲测免费】 常见问题解答关于AnimateDiff模型创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考