对数组进行排序的最小交换次数

Question

我需要做这样的事情：假设我有一个数组：

 [3, 4, 1, 2]

我需要交换 3 和 4，以及 1 和 2，所以我的数组看起来像[4, 3, 2, 1]. 现在，我可以只做sort(). 在这里我需要计算我需要多少次迭代，将初始数组更改为最终输出。例子：

// I can sort one pair per iteration
let array = [3, 4, 1, 2, 5]
let counter = 0;

//swap 3 and 4
counter++;
// swap 1 and 2
counter++;
// 5 goes to first place
counter++

// now counter = 3 <-- what I need

编辑：这是我尝试过的。并不总是有效...它来自这个问题：Bubble sort algorithm JavaScript

let counter = 0;
    let swapped;
    do {
        swapped = false;
        for (var i = 0; i < array.length - 1; i++) {
            if (array[i] < array[i + 1]) {
                const temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = true;
                counter++;
            }
        }
    } while (swapped);

编辑：这并不总是正确的，因为我可以从最后到第一个交换位置，例如。看上面的示例代码，现在已经编辑好了。

Answer 1

这是迄今为止我尝试过的最佳代码，该代码也被hackerrank接受为最佳答案：

function minimumSwaps(arr) {
    var arrLength = arr.length;

    // create two new Arrays 
    // one record value and key separately
    // second to keep visited node count (default set false to all)

    var newArr = [];
    var newArrVisited = [];
    for (let i = 0; i < arrLength; i++) {
        newArr[i]= [];
        newArr[i].value = arr[i];
        newArr[i].key = i;
        newArrVisited[i] = false;
    }

    // sort new array by value

    newArr.sort(function (a, b) {
        return a.value - b.value;
    })

    var swp = 0;
    for (let i = 0; i < arrLength; i++) {

        // check if already visited or swapped
        if (newArr[i].key == i || newArrVisited[i]) {
            continue;
        }

        var cycle = 0;
        var j = i;
        while (!newArrVisited[j]) {

            // mark as visited
            newArrVisited[j] = true;
            j = newArr[j].key; //assign next key
            cycle++;
        }
        if (cycle > 0) {
            swp += (cycle > 1) ? cycle - 1 : cycle;
        } 

    }
    return swp;
}

参考