JavaScript实现选择排序部分测试用例运行失败排查

问题复现 #

现有如下选择排序实现代码，在短测试用例（如[1,3,2]）下可正常运行，但传入用例[8, 5, 2, 9, 5, 6, 3]时无法得到正确排序结果：

function selectionSort(array) {
    for(let j = 0; j < array.length; j++) {
        let smallest = array[j];
            for(let i = j; i >= 0; i--) {
                if(array[i] > smallest) {
                    let temp1 = array[i];
                    let temp2 = array[j];
    
                    array[i] = temp2;
                    array[j] = temp1;
                }
            }
    }
    return array;
}

selectionSort([8, 5, 2, 9, 5, 6, 3]).forEach(element => {
    console.log(element);
});

原实现思路为：将j作为元素选择指针，内层循环反向遍历j位置之前的元素，交换得到当前范围内的最小元素。

核心逻辑错误点 #

• 违背选择排序核心设计：标准选择排序每一轮仅需要在未排序区间找到最小值的索引，最后执行1次交换将最小值放到未排序区间头部即可。当前代码在内层循环中只要遇到比smallest大的元素就交换，频繁交换会直接打乱数组元素的相对位置。
• 比较基准值未更新：代码中smallest存储的是轮次初始时array[j]的数值，一旦内层循环发生交换，array[j]的值已经改变，但smallest仍然是旧值，后续比较的基准完全失效。
• 内层循环遍历范围错误：选择排序中j位置之前的[0, j-1]属于已经完成排序的区间，未排序区间范围是[j, array.length-1]。当前内层循环从j反向遍历到0，相当于反复在已排序区间做无效且错误的交换，会破坏之前已经排好的顺序。

修正后可运行代码 #

function selectionSort(array) {
    for(let j = 0; j < array.length; j++) {
        // 记录未排序区间最小值的索引，初始为当前未排序区间起点j
        let minIndex = j;
        // 遍历整个未排序区间，找到最小值对应的索引
        for(let i = j + 1; i < array.length; i++) {
            if(array[i] < array[minIndex]) {
                minIndex = i;
            }
        }
        // 找到最小值后，仅交换一次，将最小值放到未排序区间的起点
        if(minIndex !== j) {
            [array[j], array[minIndex]] = [array[minIndex], array[j]];
        }
    }
    return array;
}

// 测试用例运行
selectionSort([8, 5, 2, 9, 5, 6, 3]).forEach(element => {
    console.log(element);
});

运行上述代码，对测试用例[8, 5, 2, 9, 5, 6, 3]的排序输出为2,3,5,5,6,8,9，符合升序排序预期。

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