如何用参考索引数组与swap函数在JS中原地排序数组（AI脚本场景）

最优实现 #

核心思路 #

问题本质是循环置换分组处理：每个元素的目标位置可通过referenceArray确定，我们可以找出数组中的所有置换循环（比如元素A需到位置B，元素B需到位置C，元素C需到位置A，形成一个循环）。对于长度为k的循环，仅需k-1次交换即可完成所有元素归位，这是交换次数最少的最优方案。

为了高效跟踪元素位置变化，我们维护两个映射数组：

• origToPos：记录原数组索引对应的元素当前所在的位置
• origAtPos：记录当前位置对应的元素来自原数组的哪个索引

代码实现 #

function algorithmToSortArray(arrayToBeSorted, referenceArray) {
    var n = arrayToBeSorted.length;
    if (n !== referenceArray.length) return arrayToBeSorted;

    // 初始化映射数组
    var origToPos = [];
    var origAtPos = [];
    for (var i = 0; i < n; i++) {
        origToPos[i] = i;
        origAtPos[i] = i;
    }

    // 标记已处理的位置，避免重复操作
    var visited = [];
    for (var i = 0; i < n; i++) {
        visited[i] = false;
    }

    // 遍历每个位置处理循环置换
    for (var i = 0; i < n; i++) {
        if (visited[i]) continue;

        var currentPos = i;
        while (!visited[currentPos]) {
            visited[currentPos] = true;
            // 当前位置需要的原数组索引
            var neededOrigIndex = referenceArray[currentPos];
            
            // 元素已在正确位置，跳过交换
            if (origAtPos[currentPos] === neededOrigIndex) {
                continue;
            }

            // 获取目标元素当前所在的位置
            var neededPos = origToPos[neededOrigIndex];
            // 交换两个位置的元素
            swapItems(currentPos, neededPos);

            // 更新映射数组，同步元素位置变化
            var currOrig = origAtPos[currentPos];
            origToPos[currOrig] = neededPos;
            origToPos[neededOrigIndex] = currentPos;

            origAtPos[currentPos] = neededOrigIndex;
            origAtPos[neededPos] = currOrig;

            // 移动到循环中的下一个位置继续处理
            currentPos = neededPos;
        }
    }

    return arrayToBeSorted;
}

代码说明 #

1. 映射初始化：origToPos和origAtPos初始时直接对应原数组的索引与位置关系。
2. 循环处理：遍历每个位置，若未处理则进入循环置换逻辑：
   • 找到当前位置需要的元素的当前位置
   • 交换元素并更新映射数组，确保后续操作能准确跟踪元素位置
   • 沿着循环依次处理，直到所有元素归位
3. 最优性：每个循环仅需k-1次交换（k为循环长度），整体交换次数达到理论最小值，时间复杂度为O(n)，适合处理任意规模的数组。

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