排序算法之：圈排序（Cycle Sort）的最小写操作优化与原地排序特性 题目描述 给定一个包含 n 个元素的整数数组 arr ，要求使用 圈排序（Cycle Sort） 对其进行升序排序。圈排序的核心特点是 最小化写操作次数 （每个元素最多被写入一次），并实现 原地排序 （仅需 O(1) 额外空间）。请解释其工作原理、步骤，并分析如何保证最小写操作。 解题过程 1. 算法背景与核心思想 圈排序是一种基于 元素最终位置 的非比较类排序算法。其核心思想是： 将数组视为一组 圈（Cycle） ，每个圈独立排序。 通过将元素直接交换到其 最终正确位置 ，减少不必要的中间交换。 理想情况下，每个元素只需一次写操作（即直接放置到最终位置）。 2. 关键概念：元素的目标位置 对于数组 arr 中的某个元素 x ，其 目标位置 （即排序后应处的位置）由数组中比 x 小的元素数量决定。 例如： arr = [4, 3, 2, 1] ，元素 4 比 3 个元素大，故目标位置为索引 3 （0-based）。 3. 算法步骤详解 步骤 1：遍历数组，处理每个圈 从索引 i = 0 开始，依次处理每个元素： 若当前元素已在正确位置（即其目标位置等于当前索引），则跳过。 否则，以当前元素为起点，开始一个圈的排序。 步骤 2：构建一个圈 计算当前元素 x = arr[i] 的目标位置 pos ： 注意：若存在重复元素，需确保相同元素按原顺序排列（稳定排序需额外处理）。 若 pos 等于当前索引 i ，说明 x 已在正确位置，结束当前圈。 否则，将 x 与 arr[pos] 交换（或直接写入目标位置），并更新 x 为被替换的元素。 重复步骤 2，直到回到圈的起点（即当前圈闭合）。 步骤 3：继续处理下一个圈 移动索引 i 到下一个未处理元素，重复步骤 2，直到整个数组有序。 4. 示例演示 以 arr = [3, 1, 4, 2] 为例： 圈 1 （起点 i=0 , x=3 ）： 比 3 小的元素有 1, 2 ，故 pos = 2 。 交换 arr[0] 与 arr[2] → [4, 1, 3, 2] 。 新 x=4 ，目标位置 pos=3 （比 4 小的有 3 个元素）。 交换 arr[2] 与 arr[3] → [4, 1, 2, 3] 。 新 x=2 ，目标位置 pos=1 ，交换 arr[3] 与 arr[1] → [4, 3, 2, 1] 。 新 x=1 ，目标位置 pos=0 ，交换 arr[1] 与 arr[0] → [1, 3, 2, 4] 。 回到起点 i=0 ，圈结束。 圈 2 （起点 i=1 , x=3 ）： 目标位置 pos=2 ，交换 arr[1] 与 arr[2] → [1, 2, 3, 4] 。 最终结果： [1, 2, 3, 4] 。 5. 最小写操作的实现 每次交换时，元素被直接移动到其目标位置，避免多次临时移动。 若使用 直接赋值 而非交换（如先将 x 保存，再逐个覆盖目标位置），可进一步减少写操作（但需注意循环终止条件）。 最坏情况下写操作次数为 n （每个元素一次写操作），优于许多排序算法（如选择排序需 O(n²) 次写操作）。 6. 复杂度分析 时间复杂度 ：O(n²)（需为每个元素计算目标位置，最坏需遍历整个数组）。 空间复杂度 ：O(1)（原地排序，仅需常数额外空间）。 适用场景 ：对写操作敏感的场景（如闪存存储），且元素可被直接覆盖。 7. 边界条件与重复元素处理 若存在重复元素，需在计算 pos 时统计 已处理过的相同元素 ，避免目标位置冲突。 可通过记录相同元素的起始索引或使用辅助计数器实现稳定排序。 通过以上步骤，圈排序在保证原地排序的同时，显著优化了写操作次数，适用于特定约束场景。