排序算法之：圈排序（Cycle Sort）的最小写操作优化与原地排序特性

题目描述
圈排序（Cycle Sort）是一种基于循环分解的原地排序算法，其核心目标是通过最少的写操作次数对数组进行排序。该算法特别适用于需要最小化写操作成本的场景（例如，闪存存储设备中写操作会损耗寿命）。给定一个长度为 n 的数组，圈排序的时间复杂度为 O(n²)，但写操作次数可优化至理论最小值（即每个元素最多被移动一次到其正确位置）。

解题过程

1. 算法核心思想

   • 将数组分解为多个循环（Cycle），每个循环中的元素通过环形替换移动到正确位置。
   • 例如，若元素 x 应排在位置 i，而当前位置 j 的元素 y 应排在位置 k，则通过连续交换将 x 移动到 i，同时 y 移动到 k，直到循环闭合。

2. 步骤详解
   步骤 1：遍历数组，选择循环起点

   • 从索引 0 开始，依次检查每个元素是否已在正确位置（即元素值等于排序后应处的索引位置）。若不在，则以其为起点启动一个循环。

   步骤 2：构建循环并移动元素

   • 以当前元素 arr[i] 为例，计算其正确位置 pos：

     pos = 数组中比 arr[i] 小的元素个数 + 数组中与 arr[i] 相等且索引小于 i 的元素个数  
     

   • 若 pos 与 i 相同，说明元素已在正确位置，跳过。
   • 否则，将 arr[i] 与 arr[pos] 交换，并重复计算新移动到 arr[i] 的元素的正确位置，直到循环闭合（即回到起点）。

   步骤 3：处理重复元素

   • 若存在重复元素，需确保相同元素的相对顺序不变（稳定排序）。在计算 pos 时，需统计比当前元素小的元素数量，以及相同元素中索引更小的数量，以避免破坏稳定性。

   步骤 4：优化写操作次数

   • 每次循环中，仅在所有元素确定正确位置后执行一次写操作，而不是每次交换都写。例如，先将循环中的元素暂存，再一次性按顺序写入正确位置。

3. 示例演示
   数组：[4, 3, 2, 1]

   • 循环 1：元素 4 的正确位置是索引 3（因为比 4 小的元素有 3 个）。交换 4 和 1，数组变为 [1, 3, 2, 4]。
   • 循环 2：元素 1 的正确位置是索引 0（已正确）。
   • 循环 3：元素 3 的正确位置是索引 2。交换 3 和 2，数组变为 [1, 2, 3, 4]。
   • 最终数组有序，写操作次数为 3（每个元素移动一次）。

4. 复杂度分析

   • 时间复杂度：O(n²)（每个元素需遍历后续元素计算正确位置）。
   • 空间复杂度：O(1)（原地排序）。
   • 写操作次数：最优情况下为 n（每个元素移动一次），优于多数排序算法。

关键点总结

• 圈排序通过循环分解最小化写操作，适用于写操作成本高的场景。
• 需注意重复元素的稳定性处理，确保相同元素的原始相对顺序不变。
• 尽管时间复杂度较高，但其原地特性和最小写操作次数使其在特定场景下具有优势。