企业官网建设流程全解析

圈排序 (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 次写入，n=100 完全逆序需 14850 次写入
• 选择排序：每轮最多交换 1 次（3 次写入），n=100 需约 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_start=0, item=3 --- 找 3 的正确位置：统计比 3 小的元素 1 < 3 → pos=1 2 < 3 → pos=2 pos=2（3 应在索引 2） 跳过重复：arr[2]=4 ≠ 3，无需跳过 写入: arr[2] ← 3, 被挤出 item=4 数组: [3, 1, 3, 2, 5] ← 注意位置 0 暂时还是 3（旧值） --- 旋转：item=4 找位置 --- 找 4 的正确位置：统计比 4 小的元素（从 cycle_start+1 开始） 1 < 4 → pos=1 3(位置0的旧值不算) → 跳过 2 < 4 → pos=2... 实际：从 cycle_start+1=1 开始扫描 arr[1]=1 < 4 → pos=1 arr[2]=3 < 4 → pos=2 arr[3]=2 < 4 → pos=3 arr[4]=5 > 4 → 不变 pos=3（4 应在索引 3） 跳过重复：arr[3]=2 ≠ 4，无需跳过 写入: arr[3] ← 4, 被挤出 item=2 数组: [3, 1, 3, 4, 5] --- 旋转：item=2 找位置 --- 找 2 的正确位置：统计比 2 小的元素 arr[1]=1 < 2 → pos=1 pos=1（2 应在索引 1） 写入: arr[1] ← 2, 被挤出 item=1 数组: [3, 2, 3, 4, 5] --- 旋转：item=1 找位置 --- 找 1 的正确位置：统计比 1 小的元素 无 → pos=0（1 应在索引 0） 写入: arr[0] ← 1, 回到 cycle_start=0，循环结束 数组: [1, 2, 3, 4, 5] --- cycle_start=1~4: 都已在正确位置，跳过 --- 最终结果: [1, 2, 3, 4, 5] 总写入次数: 4（恰好等于不在正确位置的元素数）

关键观察

1. 每个元素最多写入一次：元素被直接放到最终位置，不会再次被移动
2. 写入次数 = 不在正确位置的元素数：这是理论下界，不可能更少
3. 循环检测：通过pos == cycle_start判断是否回到起点，结束当前循环
4. 重复元素处理：while item == arr[pos]: pos += 1跳过相等元素，避免覆盖

与选择排序的本质区别

核心差异：选择排序用"交换"归位极值（3 次写入），圈排序用"旋转"归位元素（1 次写入）。代价是圈排序的比较次数更多——每个元素都要完整扫描未排序部分来计算正确位置。

三、代码实现

完整代码

通过网盘分享的文件：算法
链接: https://pan.baidu.com/s/1DTJt1X2Is_IQeH5fAXvtZg?pwd=yyqf 提取码: yyqf
–来自百度网盘超级会员v4的分享

完整实现

defcycle_sort(arr,ascending=True):""" 圈排序：通过循环旋转将每个元素直接放到最终位置，最小化写入次数。 核心特点：每个元素最多被写入一次（最少写入排序），适合写代价高的场景 （如 EEPROM/Flash 存储器，写入次数有物理损耗）。 时间复杂度：O(n²) | 空间复杂度：O(1) | 不稳定排序 参数: arr: 待排序列表 ascending: 排序方向，True=升序（默认），False=降序 返回: 排序后的列表（原地排序） """n=len(arr)ifn<=1:returnarr# 遍历每个位置，将对应元素旋转到正确位置forcycle_startinrange(n-1):item=arr[cycle_start]# 找到 item 的正确位置：统计未排序部分中比它小（升序）/大（降序）的元素个数pos=cycle_startforiinrange(cycle_start+1,n):ifascending:ifarr[i]<item:pos+=1else:ifarr[i]>item:pos+=1# 如果已在正确位置，跳过此轮ifpos==cycle_start:continue# 跳过与 item 相等的重复元素，避免覆盖whileitem==arr[pos]:pos+=1# 将 item 放到正确位置，取出被替换的元素arr[pos],item=item,arr[pos]# 旋转循环：继续为被替换的元素找正确位置，直到回到起点whilepos!=cycle_start:pos=cycle_startforiinrange(cycle_start+1,n):ifascending:ifarr[i]<item:pos+=1else:ifarr[i]>item:pos+=1whileitem==arr[pos]:pos+=1arr[pos],item=item,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,ascending=True):"""圈排序（记录写入次数），用于对比测试。"""n=len(arr)ifn<=1:returnarr,0writes=0forcycle_startinrange(n-1):item=arr[cycle_start]pos=cycle_startforiinrange(cycle_start+1,n):ifascending:ifarr[i]<item:pos+=1else:ifarr[i]>item:pos+=1ifpos==cycle_start:continuewhileitem==arr[pos]:pos+=1arr[pos],item=item,arr[pos]writes+=1whilepos!=cycle_start:pos=cycle_startforiinrange(cycle_start+1,n):ifascending:ifarr[i]<item:pos+=1else:ifarr[i]>item:pos+=1whileitem==arr[pos]:pos+=1arr[pos],item=item,arr[pos]writes+=1returnarr,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[:],ascending=False)}")# 边界测试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]

四、复杂度分析

时间复杂度

推导过程：

cycle_start=0: 扫描 n-1 个元素计算 pos → n-1 次比较 cycle_start=1: 扫描 n-2 个元素计算 pos → n-2 次比较 ... cycle_start=n-2: 扫描 1 个元素 → 1 次比较 每个循环内部的旋转还要额外扫描： 循环长度为 k 的环 → k 次扫描，每次 O(n) 总比较次数 ≈ n²（比选择排序更多，因为旋转时要重新计数）

关键结论：圈排序的比较次数比选择排序更多——选择排序每轮只找极值（一次扫描），圈排序每个元素都要重新计数（多次扫描）。这是"用更多比较换更少写入"的代价。

写入次数（核心指标）

理论下界：任何排序算法的写入次数至少等于"不在正确位置的元素数量"（因为这些元素必须被写入至少一次）。圈排序恰好达到这个下界——没有任何排序算法能比圈排序写入更少。

空间复杂度

O(1)——仅使用item、pos、cycle_start、i等常数个辅助变量，原地排序。

稳定性

不稳定排序。循环旋转时元素跨越距离写入，可能改变相等元素的相对顺序。

五、横向对比

圈排序与同系列算法的对比：

写入次数实测对比

importrandomprint("--- 写入次数对比 (n=100) ---")test_data=random.sample(range(1000),100)_,cycle_writes=_cycle_sort_with_writes(test_data[:])_,sel_writes=selection_sort_writes(test_data[:])_,bub_writes=bubble_sort_writes(test_data[:])print(f"圈排序写入次数:{cycle_writes}")print(f"选择排序写入次数:{sel_writes}（每次交换=3次写入）")print(f"冒泡排序写入次数:{bub_writes}（每次交换=3次写入）")print("\n--- 完全逆序写入对比 (n=100) ---")reverse_data=list(range(100,0,-1))_,cycle_w=_cycle_sort_with_writes(reverse_data[:])_,sel_w=selection_sort_writes(reverse_data[:])_,bub_w=bubble_sort_writes(reverse_data[:])print(f"圈排序写入次数:{cycle_w}")print(f"选择排序写入次数:{sel_w}")print(f"冒泡排序写入次数:{bub_w}")

典型输出：

--- 写入次数对比 (n=100) --- 圈排序写入次数: 98 选择排序写入次数: 270（每次交换=3次写入） 冒泡排序写入次数: 7812（每次交换=3次写入） 圈排序比选择排序少写: 172 次 圈排序比冒泡排序少写: 7714 次 --- 完全逆序写入对比 (n=100) --- 圈排序写入次数: 100 选择排序写入次数: 150 冒泡排序写入次数: 14850

写入次数汇总

选型建议：

• 写代价极高（Flash/EEPROM）：圈排序（写入达到理论下界）
• 写代价中等：选择排序（交换次数少，比较次数比圈排序少）
• 通用场景：快速排序或 TimSort（综合性能最优）
• 需要稳定性：归并排序或 TimSort

六、工程实战

Flash 存储器排序场景

圈排序最经典的应用场景是EEPROM/Flash 存储器中的数据排序：

# 模拟 Flash 存储器排序：写入次数 = 存储块损耗classFlashStorage:def__init__(self,data):self.data=data self.write_count=0# 记录写入次数（物理损耗指标）self.max_writes=100000# 存储块最大擦写次数defwrite(self,index,value):self.data[index]=value self.write_count+=1defremaining_life(self):returnself.max_writes-self.write_count# 排序 500 个元素的 Flash 数据flash=FlashStorage([64,34,25,12,22,11,90,...])# 圈排序：写入次数 ≈ 500（不正确位置的元素数）# 冒泡排序：写入次数 ≈ 75000（3 × 逆序对数）# 圈排序让 Flash 寿命延长 150 倍

写一次存储介质

某些存储介质（如 WORM 光盘、一次性写入 Flash）只允许每个位置写入一次。圈排序在这种极端场景下有独特价值——虽然不是严格的"每位置写一次"，但写入次数极少，可以通过预留冗余位置来适配。

数据库记录排序

数据库中排序大记录时，交换两条记录可能涉及磁盘 I/O：

# 数据库场景：交换两条记录 = 2 次磁盘写入# 圈排序：每条记录最多写入 1 次磁盘# 选择排序：每轮最多 2 次磁盘写入（交换两条记录）# 冒泡排序：每个逆序对 2 次磁盘写入

性能对比

importrandomimporttime random_data=random.sample(range(10000),5000)start=time.time()cycle_sort(random_data[:])print(f"圈排序:{time.time()-start:.4f}s")start=time.time()sorted(random_data[:])print(f"TimSort:{time.time()-start:.4f}s")

典型输出：

圈排序: 1.5626s TimSort: 0.0006s

圈排序比 TimSort 慢 2600 倍——这是"用更多比较换更少写入"的代价。只有在写代价远高于读代价的场景下，这个交换才划算。

为什么标准库不用圈排序？

七、常见误区与面试题

高频面试题

Q1：圈排序的核心优势是什么？

圈排序的核心优势是写入次数最少——总写入次数恰好等于"不在正确位置的元素数量"，达到理论下界。任何比较排序都不可能比它写入更少。这是因为圈排序通过循环旋转，让每个元素直接写入到最终位置，不会再次被移动。适用于 Flash/EEPROM 等写代价远高于读代价的场景。

Q2：圈排序的写入次数为什么是理论下界？

一个不在正确位置的元素，必须被写入至少一次才能归位。圈排序中每个元素恰好被写入一次（在循环旋转中），不多不少。而已在正确位置的元素通过pos == cycle_start跳过，零写入。因此总写入次数 = 不在正确位置的元素数，这是任何排序算法都不可能超越的下界。

Q3：圈排序和选择排序有什么区别？

选择排序用"交换"归位（3 次写入），圈排序用"旋转"归位（1 次写入）。圈排序写入更少但比较更多——用更多比较换更少写入。

Q4：圈排序是稳定的吗？

不稳定。循环旋转时元素跨越距离写入到正确位置，可能跳过相等元素，改变其相对顺序。例如[3a, 1, 3b, 2]，旋转时 3a 可能先于 3b 被写入，导致 3b 在 3a 之前。

常见实现错误

八、总结

圈排序的核心要点：

1. 最少写入排序——总写入次数 = 不在正确位置的元素数，达到理论下界
2. 循环旋转归位——计算最终位置 → 直接写入 → 被挤出元素继续找位置 → 回到起点
3. 用比较换写入——比较次数比选择排序更多（旋转时重新计数），但写入次数最少
4. 原地 + 不稳定——O(1) 空间，但跨距离写入破坏稳定性
5. 特殊场景不可替代——Flash/EEPROM 等写代价高的场景，圈排序是唯一合理选择

圈排序在排序算法家族中是一个"极端特化"的算法——它牺牲了时间复杂度（O(n²) 的比较）和通用性，换取了写入次数的理论最优。它不适合通用排序，但在写代价远高于读代价的硬件场景中不可替代。理解了"循环分解 + 旋转归位"的思想，就理解了如何从数学结构上最小化写入操作。

📌专栏导航：算法

⬅️上一篇：梳排序 (Comb Sort) ➡️下一篇：1-11-奇偶排序-OddEvenSort

如果这篇文章对你有帮助，欢迎点赞、收藏、关注，支持专栏持续更新！