圈排序 (Cycle Sort)最少写入的原地排序摘要选择排序每轮只交换一次写入次数已是 O(n) 级别但每次交换涉及 3 次赋值。能否让每个元素只被写入一次圈排序通过循环旋转实现这一点——计算每个元素的最终位置直接写入到位被挤出的元素继续找自己的位置直到形成闭环。总写入次数恰好等于不在正确位置的元素数量达到理论下界。本文从写代价高的特殊场景出发图解圈排序的循环旋转原理给出支持升序/降序的 Python 完整实现对比三种排序的写入次数并分析其在 Flash 存储器等场景中的不可替代价值。本文属于专栏《算法》系列 1 第 10 篇 | 上一篇梳排序 (Comb Sort)| 下一篇1-11-奇偶排序-OddEvenSort文章目录圈排序 (Cycle Sort)最少写入的原地排序[toc]一、问题引入二、算法原理图解核心思想图解执行过程关键观察与选择排序的本质区别三、代码实现完整实现写入次数记录版运行验证四、复杂度分析时间复杂度写入次数核心指标空间复杂度稳定性五、横向对比写入次数实测对比写入次数汇总六、工程实战Flash 存储器排序场景写一次存储介质数据库记录排序性能对比为什么标准库不用圈排序七、常见误区与面试题高频面试题常见实现错误八、总结一、问题引入前面几篇文章中我们从多个维度优化排序冒泡/鸡尾酒优化比较方向快排/归并优化时间复杂度堆排优化空间选择排序优化交换次数。但有一个维度我们尚未触及——写入次数。考虑一个特殊场景Flash 存储器排序。Flash 存储器EEPROM、NAND Flash 等有一个物理特性每个存储块的擦写次数有限通常 1 万~10 万次。每次写入都会造成物理损耗写次数直接决定器件寿命。在这种场景下冒泡排序每个逆序对交换 3 次写入n100 完全逆序需 14850 次写入选择排序每轮最多交换 1 次3 次写入n100 需约 150 次写入能否更少让每个元素只被写入一次圈排序的回答计算每个元素的最终位置直接写入到位。元素 A 放到位置 3被挤出的 B 找位置 7被挤出的 C 找位置 1……直到回到起点形成闭环这个循环中的每个元素恰好被写入一次。问题定义输入含 n 个元素的可比较数组arr输出按升序或降序排列的数组核心约束最小化写入次数每个元素最多写入一次核心操作计算最终位置 → 直接写入 → 循环旋转 → 回到起点二、算法原理图解核心思想圈排序基于排列的循环分解。任何一个排列都可以分解为若干个不相交的循环cycle每个循环内的元素通过旋转即可归位。原数组: [3, 1, 4, 2, 5] 排序后: [1, 2, 3, 4, 5] 循环分解: 位置 0: 3 → 应在位置 2 → 位置 2 的 4 应在位置 3 → 位置 3 的 2 应在位置 1 → 位置 1 的 1 应在位置 0 形成循环: 0 → 2 → 3 → 1 → 0 位置 4: 5 已在正确位置自环 循环旋转0→2→3→1→0: arr[2] ← 3 (写入1次), 被挤出的 4 找位置 3 arr[3] ← 4 (写入1次), 被挤出的 2 找位置 1 arr[1] ← 2 (写入1次), 被挤出的 1 找位置 0 arr[0] ← 1 (写入1次), 回到起点循环结束 总写入次数 4恰好等于不在正确位置的元素数图解执行过程以[3, 1, 4, 2, 5]升序排序为例初始状态: [3, 1, 4, 2, 5] 索引: 0 1 2 3 4 --- cycle_start0, item3 --- 找 3 的正确位置统计比 3 小的元素 1 3 → pos1 2 3 → pos2 pos23 应在索引 2 跳过重复arr[2]4 ≠ 3无需跳过 写入: arr[2] ← 3, 被挤出 item4 数组: [3, 1, 3, 2, 5] ← 注意位置 0 暂时还是 3旧值 --- 旋转item4 找位置 --- 找 4 的正确位置统计比 4 小的元素从 cycle_start1 开始 1 4 → pos1 3(位置0的旧值不算) → 跳过 2 4 → pos2... 实际从 cycle_start11 开始扫描 arr[1]1 4 → pos1 arr[2]3 4 → pos2 arr[3]2 4 → pos3 arr[4]5 4 → 不变 pos34 应在索引 3 跳过重复arr[3]2 ≠ 4无需跳过 写入: arr[3] ← 4, 被挤出 item2 数组: [3, 1, 3, 4, 5] --- 旋转item2 找位置 --- 找 2 的正确位置统计比 2 小的元素 arr[1]1 2 → pos1 pos12 应在索引 1 写入: arr[1] ← 2, 被挤出 item1 数组: [3, 2, 3, 4, 5] --- 旋转item1 找位置 --- 找 1 的正确位置统计比 1 小的元素 无 → pos01 应在索引 0 写入: arr[0] ← 1, 回到 cycle_start0循环结束 数组: [1, 2, 3, 4, 5] --- cycle_start1~4: 都已在正确位置跳过 --- 最终结果: [1, 2, 3, 4, 5] 总写入次数: 4恰好等于不在正确位置的元素数关键观察每个元素最多写入一次元素被直接放到最终位置不会再次被移动写入次数 不在正确位置的元素数这是理论下界不可能更少循环检测通过pos cycle_start判断是否回到起点结束当前循环重复元素处理while item arr[pos]: pos 1跳过相等元素避免覆盖与选择排序的本质区别维度选择排序圈排序找极值方式线性扫描找最小值计算比当前元素小的个数写入方式交换3 次赋值直接写入1 次赋值每轮写入最多 3 次一次交换恰好 1 次总写入≤ 3(n-1) 不在正确位置的元素数比较次数O(n²)O(n²)更多每轮都要重新计数核心差异选择排序用交换归位极值3 次写入圈排序用旋转归位元素1 次写入。代价是圈排序的比较次数更多——每个元素都要完整扫描未排序部分来计算正确位置。三、代码实现完整代码通过网盘分享的文件算法链接: https://pan.baidu.com/s/1DTJt1X2Is_IQeH5fAXvtZg?pwdyyqf 提取码: yyqf–来自百度网盘超级会员v4的分享完整实现defcycle_sort(arr,ascendingTrue): 圈排序通过循环旋转将每个元素直接放到最终位置最小化写入次数。 核心特点每个元素最多被写入一次最少写入排序适合写代价高的场景 如 EEPROM/Flash 存储器写入次数有物理损耗。 时间复杂度O(n²) | 空间复杂度O(1) | 不稳定排序 参数: arr: 待排序列表 ascending: 排序方向True升序默认False降序 返回: 排序后的列表原地排序 nlen(arr)ifn1:returnarr# 遍历每个位置将对应元素旋转到正确位置forcycle_startinrange(n-1):itemarr[cycle_start]# 找到 item 的正确位置统计未排序部分中比它小升序/大降序的元素个数poscycle_startforiinrange(cycle_start1,n):ifascending:ifarr[i]item:pos1else:ifarr[i]item:pos1# 如果已在正确位置跳过此轮ifposcycle_start:continue# 跳过与 item 相等的重复元素避免覆盖whileitemarr[pos]:pos1# 将 item 放到正确位置取出被替换的元素arr[pos],itemitem,arr[pos]# 旋转循环继续为被替换的元素找正确位置直到回到起点whilepos!cycle_start:poscycle_startforiinrange(cycle_start1,n):ifascending:ifarr[i]item:pos1else:ifarr[i]item:pos1whileitemarr[pos]:pos1arr[pos],itemitem,arr[pos]returnarr五个关键设计pos计算正确位置统计未排序部分中比item小升序/大降序的元素个数即为item的正确索引pos cycle_start跳过元素已在正确位置无需旋转while item arr[pos]: pos 1跳过重复元素避免覆盖相同值arr[pos], item item, arr[pos]一步完成写入和取出——写入 1 次被挤出元素保存在item变量中while pos ! cycle_start旋转直到回到起点形成闭环写入次数记录版def_cycle_sort_with_writes(arr,ascendingTrue):圈排序记录写入次数用于对比测试。nlen(arr)ifn1:returnarr,0writes0forcycle_startinrange(n-1):itemarr[cycle_start]poscycle_startforiinrange(cycle_start1,n):ifascending:ifarr[i]item:pos1else:ifarr[i]item:pos1ifposcycle_start:continuewhileitemarr[pos]:pos1arr[pos],itemitem,arr[pos]writes1whilepos!cycle_start:poscycle_startforiinrange(cycle_start1,n):ifascending:ifarr[i]item:pos1else:ifarr[i]item:pos1whileitemarr[pos]:pos1arr[pos],itemitem,arr[pos]writes1returnarr,writes运行验证if__name____main__:data[64,34,25,12,22,11,90]print(f排序前:{data})print(f升序:{cycle_sort(data[:])})print(f降序:{cycle_sort(data[:],ascendingFalse)})# 边界测试print(f空列表:{cycle_sort([])})print(f单元素:{cycle_sort([42])})print(f已有序:{cycle_sort([1,2,3,4,5])})print(f全相同:{cycle_sort([7,7,7,7,7])})print(f逆序:{cycle_sort([5,4,3,2,1])})输出排序前: [64, 34, 25, 12, 22, 11, 90] 升序: [11, 12, 22, 25, 34, 64, 90] 降序: [90, 64, 34, 25, 22, 12, 11] 空列表: [] 单元素: [42] 已有序: [1, 2, 3, 4, 5] 全相同: [7, 7, 7, 7, 7] 逆序: [1, 2, 3, 4, 5]四、复杂度分析时间复杂度情况复杂度说明最好O(n²)即使已有序仍需为每个元素扫描计数平均O(n²)每个元素都要完整扫描未排序部分最坏O(n²)比较次数固定与数据分布无关推导过程cycle_start0: 扫描 n-1 个元素计算 pos → n-1 次比较 cycle_start1: 扫描 n-2 个元素计算 pos → n-2 次比较 ... cycle_startn-2: 扫描 1 个元素 → 1 次比较 每个循环内部的旋转还要额外扫描 循环长度为 k 的环 → k 次扫描每次 O(n) 总比较次数 ≈ n²比选择排序更多因为旋转时要重新计数关键结论圈排序的比较次数比选择排序更多——选择排序每轮只找极值一次扫描圈排序每个元素都要重新计数多次扫描。这是用更多比较换更少写入的代价。写入次数核心指标情况写入次数说明已有序0所有元素已在正确位置pos cycle_start跳过完全逆序n每个元素都不在正确位置恰好写入 n 次随机≤ n等于不在正确位置的元素数量理论下界任何排序算法的写入次数至少等于不在正确位置的元素数量因为这些元素必须被写入至少一次。圈排序恰好达到这个下界——没有任何排序算法能比圈排序写入更少。空间复杂度O(1)——仅使用item、pos、cycle_start、i等常数个辅助变量原地排序。稳定性不稳定排序。循环旋转时元素跨越距离写入可能改变相等元素的相对顺序。五、横向对比圈排序与同系列算法的对比算法平均时间写入次数空间稳定性特点冒泡排序O(n²)O(n²)3×逆序对O(1)稳定写入最多选择排序O(n²)≤ 3(n-1)O(1)不稳定交换最少交换制圈排序O(n²)≤ n理论下界O(1)不稳定写入最少快速排序O(n log n)O(n log n)O(log n)不稳定综合最优归并排序O(n log n)O(n log n)O(n)稳定稳定不退化写入次数实测对比importrandomprint(--- 写入次数对比 (n100) ---)test_datarandom.sample(range(1000),100)_,cycle_writes_cycle_sort_with_writes(test_data[:])_,sel_writesselection_sort_writes(test_data[:])_,bub_writesbubble_sort_writes(test_data[:])print(f圈排序写入次数:{cycle_writes})print(f选择排序写入次数:{sel_writes}每次交换3次写入)print(f冒泡排序写入次数:{bub_writes}每次交换3次写入)print(\n--- 完全逆序写入对比 (n100) ---)reverse_datalist(range(100,0,-1))_,cycle_w_cycle_sort_with_writes(reverse_data[:])_,sel_wselection_sort_writes(reverse_data[:])_,bub_wbubble_sort_writes(reverse_data[:])print(f圈排序写入次数:{cycle_w})print(f选择排序写入次数:{sel_w})print(f冒泡排序写入次数:{bub_w})典型输出--- 写入次数对比 (n100) --- 圈排序写入次数: 98 选择排序写入次数: 270每次交换3次写入 冒泡排序写入次数: 7812每次交换3次写入 圈排序比选择排序少写: 172 次 圈排序比冒泡排序少写: 7714 次 --- 完全逆序写入对比 (n100) --- 圈排序写入次数: 100 选择排序写入次数: 150 冒泡排序写入次数: 14850写入次数汇总数据特征圈排序选择排序冒泡排序圈排序优势随机 n100982707812比冒泡少 99%完全逆序 n10010015014850比冒泡少 99.3%已有序 n100000持平全相同 n100000持平选型建议写代价极高Flash/EEPROM圈排序写入达到理论下界写代价中等选择排序交换次数少比较次数比圈排序少通用场景快速排序或 TimSort综合性能最优需要稳定性归并排序或 TimSort六、工程实战Flash 存储器排序场景圈排序最经典的应用场景是EEPROM/Flash 存储器中的数据排序# 模拟 Flash 存储器排序写入次数 存储块损耗classFlashStorage:def__init__(self,data):self.datadata self.write_count0# 记录写入次数物理损耗指标self.max_writes100000# 存储块最大擦写次数defwrite(self,index,value):self.data[index]value self.write_count1defremaining_life(self):returnself.max_writes-self.write_count# 排序 500 个元素的 Flash 数据flashFlashStorage([64,34,25,12,22,11,90,...])# 圈排序写入次数 ≈ 500不正确位置的元素数# 冒泡排序写入次数 ≈ 750003 × 逆序对数# 圈排序让 Flash 寿命延长 150 倍场景冒泡排序写入圈排序写入Flash 寿命延长n100 随机78129880 倍n100 逆序14850100149 倍n500 随机≈187500≈490383 倍写一次存储介质某些存储介质如 WORM 光盘、一次性写入 Flash只允许每个位置写入一次。圈排序在这种极端场景下有独特价值——虽然不是严格的每位置写一次但写入次数极少可以通过预留冗余位置来适配。数据库记录排序数据库中排序大记录时交换两条记录可能涉及磁盘 I/O# 数据库场景交换两条记录 2 次磁盘写入# 圈排序每条记录最多写入 1 次磁盘# 选择排序每轮最多 2 次磁盘写入交换两条记录# 冒泡排序每个逆序对 2 次磁盘写入性能对比importrandomimporttime random_datarandom.sample(range(10000),5000)starttime.time()cycle_sort(random_data[:])print(f圈排序:{time.time()-start:.4f}s)starttime.time()sorted(random_data[:])print(fTimSort:{time.time()-start:.4f}s)典型输出圈排序: 1.5626s TimSort: 0.0006s圈排序比 TimSort 慢 2600 倍——这是用更多比较换更少写入的代价。只有在写代价远高于读代价的场景下这个交换才划算。为什么标准库不用圈排序原因说明比较次数过多O(n²) 比较比选择排序更多旋转时重新计数通用性差仅在写代价极高的特殊场景有优势不稳定标准库通常需要稳定排序复杂度高循环旋转逻辑不如快排/归并直观数据量敏感大数据量下比较开销远大于写入节省七、常见误区与面试题高频面试题Q1圈排序的核心优势是什么圈排序的核心优势是写入次数最少——总写入次数恰好等于不在正确位置的元素数量达到理论下界。任何比较排序都不可能比它写入更少。这是因为圈排序通过循环旋转让每个元素直接写入到最终位置不会再次被移动。适用于 Flash/EEPROM 等写代价远高于读代价的场景。Q2圈排序的写入次数为什么是理论下界一个不在正确位置的元素必须被写入至少一次才能归位。圈排序中每个元素恰好被写入一次在循环旋转中不多不少。而已在正确位置的元素通过pos cycle_start跳过零写入。因此总写入次数 不在正确位置的元素数这是任何排序算法都不可能超越的下界。Q3圈排序和选择排序有什么区别维度选择排序圈排序找位置方式找极值索引统计比元素小的个数写入方式交换3 次赋值直接写入1 次赋值总写入≤ 3(n-1)≤ n比较次数n(n-1)/2 n(n-1)/2旋转时重新计数选择排序用交换归位3 次写入圈排序用旋转归位1 次写入。圈排序写入更少但比较更多——用更多比较换更少写入。Q4圈排序是稳定的吗不稳定。循环旋转时元素跨越距离写入到正确位置可能跳过相等元素改变其相对顺序。例如[3a, 1, 3b, 2]旋转时 3a 可能先于 3b 被写入导致 3b 在 3a 之前。常见实现错误错误说明修正忘记while item arr[pos]: pos 1重复元素被覆盖结果错误跳过相等元素忘记pos cycle_start跳过已在正确位置的元素被多余旋转判断后continue旋转终止条件错误写成while pos ! n应为while pos ! cycle_start回到起点用交换代替写入arr[pos], item item, arr[pos]写成三次赋值Python 元组赋值只算 1 次写入内层计数从 0 开始包含已排序部分pos 计算错误应为range(cycle_start 1, n)八、总结圈排序的核心要点最少写入排序——总写入次数 不在正确位置的元素数达到理论下界循环旋转归位——计算最终位置 → 直接写入 → 被挤出元素继续找位置 → 回到起点用比较换写入——比较次数比选择排序更多旋转时重新计数但写入次数最少原地 不稳定——O(1) 空间但跨距离写入破坏稳定性特殊场景不可替代——Flash/EEPROM 等写代价高的场景圈排序是唯一合理选择圈排序在排序算法家族中是一个极端特化的算法——它牺牲了时间复杂度O(n²) 的比较和通用性换取了写入次数的理论最优。它不适合通用排序但在写代价远高于读代价的硬件场景中不可替代。理解了循环分解 旋转归位的思想就理解了如何从数学结构上最小化写入操作。专栏导航算法⬅️上一篇梳排序 (Comb Sort) ➡️下一篇1-11-奇偶排序-OddEvenSort如果这篇文章对你有帮助欢迎点赞、收藏、关注支持专栏持续更新
