如何修复我的Java Cyclic Sort算法使其正常运行？

你的代码核心问题是交换逻辑错误，没有遵循循环排序的核心思想——将元素放到对应的正确位置，而是错误地进行相邻元素交换，导致无法完成排序甚至陷入死循环。

错误分析 #

循环排序适用于元素为1到n连续整数的场景，每个元素arr[i]的正确位置是索引arr[i]-1（因为元素值从1开始）。但你的代码中，当元素不在正确位置时，只是将arr[i]与arr[i+1]交换，这本质是冒泡排序的片段逻辑，无法将元素直接归位到目标位置，比如测试数组中的5永远无法被放到索引4的位置，最终导致排序失败。

修正后的代码 #

package bdsa;

import java.util.Arrays;

public class cyclicSort {
    public static void main(String[] args) {
        int[] arr = {5,3,4,1,2};
        cyclic(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void cyclic(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            // 计算当前元素应该在的正确索引
            int correctIndex = arr[i] - 1;
            // 若当前元素不在正确位置，交换到正确位置
            if (arr[i] != arr[correctIndex]) {
                int temp = arr[i];
                arr[i] = arr[correctIndex];
                arr[correctIndex] = temp;
            } else {
                // 元素已在正确位置，移动到下一个索引
                i++;
            }
        }
    }
}

关键修正点 #

• 交换目标修正：不再交换相邻元素，而是将当前元素与它正确位置上的元素交换，确保每次交换都能让至少一个元素归位
• 循环条件优化：只有当当前元素处于正确位置时，才移动索引i；否则继续处理当前索引的新元素，直到它归位

运行修正后的代码，测试数组会被正确排序为[1, 2, 3, 4, 5]。

内容的提问来源于stack exchange，提问作者Karthikeyan Sekar