javascript - 具有意外堆栈的递归插入排序

Question

我正在尝试以递归方式编写插入排序，并想出了以下代码。

function recursiveInsertionSort(array) {
    sort(array, array.length - 1);
}

function sort(array, index) {
    if (index > 0) {
        sort(array, index - 1);
        let j = index - 1;
        let key = array[index];
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

这段代码运行完美。

例如，如果输入为 [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]，则返回 [1, 2, 3, 4、7、8、9、10、14、16]。

在 let key = array[index]; 行，我只是尝试将当前索引处的值存储在临时变量中并在循环内使用它。

如果我不将其存储在变量中而是直接使用它，如以下代码所示，我会得到错误的输出，即数组未排序。我不明白为什么它会这样。甚至递归堆栈对我来说似乎也是完美的。但我得到了一个奇怪的输出。

function sort(array, index) {
    if (index > 0) {
        sort(array, index - 1);
        let j = index - 1;
        while (j >= 0 && array[j] > array[index]) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = array[index];
    }
}

例如，如果输入为 [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]，则返回 [ 4, 4, 4, 4, 16, 16, 16, 16, 16, 16]。

有人可以帮我解决这个问题吗？这实际上打破了我对递归的理解。

Answer 1

array[index] 在第一步更改。(当 j 为 index - 1 时)

j = index -1
array[j+1] = array[j] => array[index]= array[index-1]

所以如果不将array[index]保存到key，排序时就会丢失数据。