圈排序（Cycle Sort）的最小写操作优化与原地排序特性 题目描述 圈排序（Cycle Sort）是一种专注于最小化写操作次数的原地排序算法。它通过将每个元素直接放置到其最终应在的位置，从而在整个排序过程中实现最少的元素交换次数。该算法特别适用于那些写操作代价高昂的场景（如闪存存储）。给定一个包含 n 个元素的数组，圈排序确保每个元素最多被移动一次到其正确位置，总写操作次数为 O(n)。题目要求理解圈排序的工作原理，并分析其原地排序特性及最小写操作的优势。 解题过程 算法核心思想 圈排序基于一个关键观察：如果数组中的每个元素都直接移动到其最终排序位置，那么总交换次数等于数组中“圈”的数量。每个圈代表一组元素，它们通过交换操作循环移动到各自正确的位置。 算法过程： 遍历数组，对于每个位置 i ，计算当前元素 arr[i] 在排序后应处于的位置 pos 。 如果 pos 不等于 i ，则将 arr[i] 与 arr[pos] 交换。 重复此过程，直到当前圈中的所有元素都归位，然后移动到下一个未处理的元素继续构建新圈。 详细步骤 步骤 1 ：初始化一个变量 writes （可选，用于统计写操作次数）。 步骤 2 ：从数组的第一个元素开始遍历（索引 i = 0 到 n-1 ）。 步骤 3 ：对于当前元素 item = arr[i] ，计算其正确位置 pos 。方法为统计数组中比 item 小的元素个数（例如，若数组元素唯一，则 pos 等于比 item 小的元素数量）。 步骤 4 ：如果 pos 等于 i ，说明 item 已在正确位置，跳过后续操作，继续处理下一个元素。 步骤 5 ：如果 pos 不等于 i ，但 arr[pos] 等于 item （表示有重复元素），则将 pos 向后移动一位（避免重复元素覆盖），直到找到空位或不同元素。 步骤 6 ：将 item 与 arr[pos] 交换，并增加 writes 计数。 步骤 7 ：重复步骤 3-6，直到当前圈闭合（即回到起始位置 i ），然后继续处理下一个未归位的元素。 示例演示 假设数组 [4, 3, 2, 1] ： 处理 i=0 （元素 4）：正确位置 pos=3 （因为 1,2,3 均小于 4）。交换后数组为 [1, 3, 2, 4] ，写操作次数+1。 当前元素变为 1（原在 pos=3 ），其正确位置 pos=0 ，交换后数组为 [1, 3, 2, 4] （实际未变），圈闭合。 继续处理 i=1 （元素 3）：正确位置 pos=2 ，交换后数组为 [1, 2, 3, 4] 。 最终数组有序，总写操作次数为 2（每个圈最多 n 次交换，但本例仅需两次）。 算法特性分析 时间复杂度 ：O(n²)，因为每个元素可能需要遍历整个数组以计算 pos 。 空间复杂度 ：O(1)，除了输入数组外仅使用常数级额外空间（原地排序）。 最小写操作 ：每个元素最多被移动一次，写操作次数等于圈的数量（理想情况下为 n，最坏为 n-1）。 稳定性 ：非稳定排序，因交换操作可能改变相同元素的相对顺序。 适用场景 写操作代价高的场景（如闪存、EEPROM）。 数据量较小且注重减少写次数的场景。不适用于大规模数据或读操作优先的场景。