如何对多个数组进行原地（in place）同步排序？

当然可以实现原地（in-place）排序，不需要额外创建自定义类或者占用大量内存空间！核心思路是利用**循环置换（Cycle Sort）**的思想，通过追踪每个元素在排序后的目标位置，同步调整三个数组的元素，全程只用到几个临时变量，空间复杂度为O(1)（除了输入数组本身）。

核心逻辑说明 #

你的三个数组是强关联的：indexes[i]对应sources[i]和targets[i]。我们需要根据indexes的排序结果，把每组关联元素移动到正确的位置。具体步骤如下：

1. 首先，确定每个原始索引i对应的目标位置：也就是排序后indexes[i]应该处于的索引位置（比如原indexes是[0,2,8,5]，排序后是[0,2,5,8]，那么原索引3的5应该移动到索引2的位置，原索引2的8应该移动到索引3的位置）。
2. 遍历每个索引位置，如果当前元素已经在正确位置，直接跳过；否则进入循环，把当前循环链上的所有元素依次交换到目标位置，同时同步操作三个数组的对应元素。

Java 代码实现 #

public class InPlaceSort {
    public static void main(String[] args) {
        int[] indexes = new int[]{0, 2, 8, 5};
        String[] sources = new String[]{"how", "are", "today", "you"};
        String[] targets = new String[]{"I", "am", "thanks", "fine"};

        inPlaceSort(indexes, sources, targets);

        // 打印结果
        System.out.print("indexes -> {");
        for (int i = 0; i < indexes.length; i++) {
            System.out.print(indexes[i] + (i == indexes.length - 1 ? "" : ","));
        }
        System.out.println("}");

        System.out.print("sources -> {");
        for (int i = 0; i < sources.length; i++) {
            System.out.print("\"" + sources[i] + "\"" + (i == sources.length - 1 ? "" : ","));
        }
        System.out.println("}");

        System.out.print("targets -> {");
        for (int i = 0; i < targets.length; i++) {
            System.out.print("\"" + targets[i] + "\"" + (i == targets.length - 1 ? "" : ","));
        }
        System.out.println("}");
    }

    private static void inPlaceSort(int[] indexes, String[] sources, String[] targets) {
        int n = indexes.length;
        // 遍历每个位置，处理循环置换
        for (int i = 0; i < n; i++) {
            // 如果当前元素已经在正确位置，跳过
            if (indexes[i] == getSortedIndex(indexes, indexes[i], i)) {
                continue;
            }

            // 保存当前位置的元素，准备交换
            int currentIndex = indexes[i];
            String currentSource = sources[i];
            String currentTarget = targets[i];

            int j = i;
            // 循环处理当前置换链，直到回到起始位置
            while (indexes[j] != currentIndex || j != i) {
                // 找到当前元素应该去的目标位置
                int targetPos = getSortedIndex(indexes, indexes[j], j);

                // 把目标位置的元素移动到当前位置
                indexes[j] = indexes[targetPos];
                sources[j] = sources[targetPos];
                targets[j] = targets[targetPos];

                // 移动到目标位置，继续处理
                j = targetPos;
            }

            // 把最初保存的元素放到最终的目标位置
            indexes[j] = currentIndex;
            sources[j] = currentSource;
            targets[j] = currentTarget;
        }
    }

    // 辅助方法：找到某个值在排序后的indexes数组中的位置（支持稳定排序，处理重复值）
    private static int getSortedIndex(int[] arr, int value, int originalIdx) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < value || (arr[i] == value && i < originalIdx)) {
                count++;
            }
        }
        return count;
    }
}

关键细节说明 #

• 重复索引处理：上面的代码支持indexes存在重复值的场景，通过在getSortedIndex中对比原始索引，保证了排序的稳定性（相同索引值的元素保持原始顺序）。
• 空间复杂度：整个过程只用到了几个临时变量，没有创建额外的数组或对象，完全符合原地排序的要求。
• 时间复杂度：时间复杂度为O(n²)，对于小规模数组（比如你的示例）非常高效；如果数组规模较大，可以先创建一个排序后的索引映射表（O(n)空间）来优化时间到O(n log n)，但这就不属于严格意义的原地排序了。

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