基于随机值的数组洗牌算法：Java实现O(nlogn)版本遇阻

你现在的核心问题是错误地排序了随机值数组，而没有按随机值对索引数组排序，同时直接修改原数组会导致元素覆盖丢失。以下是修正后的完整实现：

核心思路回顾 #

和Python逻辑完全一致：

• 给每个元素生成随机权重
• 对索引数组按对应权重排序
• 用排序后的索引重新排列原数组

修正后的代码 #

import java.util.Random;

public class ShuffleHelper {
    public void shuffle(Object[] a) {
        if (a.length < 2) {
            return;
        }

        int size = a.length;
        Random rand = new Random();
        Integer[] randWeights = new Integer[size];
        // 生成每个索引对应的随机权重
        for (int i = 0; i < size; i++) {
            randWeights[i] = rand.nextInt(Integer.MAX_VALUE);
        }
        
        // 初始化索引数组
        int[] indexArr = new int[size];
        for (int i = 0; i < size; i++) {
            indexArr[i] = i;
        }
        
        // 按权重对索引数组排序（自定义归并排序）
        mergeSort(indexArr, randWeights);
        
        // 用临时数组存储结果，避免原数组元素被覆盖
        Object[] temp = new Object[size];
        for (int i = 0; i < size; i++) {
            temp[i] = a[indexArr[i]];
        }
        // 把结果复制回原数组
        System.arraycopy(temp, 0, a, 0, size);
    }

    // 针对索引数组的归并排序，排序依据是对应的权重值
    private void mergeSort(int[] indexes, Integer[] weights) {
        if (indexes.length <= 1) {
            return;
        }
        int mid = indexes.length / 2;
        int[] left = new int[mid];
        int[] right = new int[indexes.length - mid];
        
        System.arraycopy(indexes, 0, left, 0, mid);
        System.arraycopy(indexes, mid, right, 0, indexes.length - mid);
        
        mergeSort(left, weights);
        mergeSort(right, weights);
        
        merge(indexes, left, right, weights);
    }

    private void merge(int[] result, int[] left, int[] right, Integer[] weights) {
        int i = 0, j = 0, k = 0;
        // 比较左右索引对应的权重，决定排序顺序
        while (i < left.length && j < right.length) {
            if (weights[left[i]].compareTo(weights[right[j]]) <= 0) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        // 处理剩余元素
        while (i < left.length) {
            result[k++] = left[i++];
        }
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
}

关键修正点 #

• 索引数组排序逻辑：修改了归并排序方法，不再直接比较索引值，而是比较每个索引对应的随机权重，这才是和Python代码rand_indexes.sort(key=lambda i: rand_values[i])等价的逻辑。
• 避免元素覆盖：原代码直接修改a[i] = a[index]会导致前面的元素被覆盖后，后续索引引用到的是修改后的值，必须用临时数组先存好所有洗牌结果，再复制回原数组。
• 类型优化：用Integer[]存储随机权重（替代泛型Comparable[]）更清晰；用int[]存储索引避免装箱拆箱的性能开销。

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