JavaScript — 数组被一堆 "undefined"填满

Question

我是 JavaScript 新手，正在尝试实现选择排序来亲自接触数组(注意:我知道有一个内置的排序函数)。不过，我遇到了一些奇怪的行为。

这是我的代码:

function selectionSort(array)
{
    let currentMin = 0;
    var minIndex = 0;

    function swap(array, i, j)
    {
        let temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    for(var i = 0; i < array.length - 1; i++)
    {
        console.log(array);
        currentMin = array[i];
        minIndex = i;

        for(var j = i + 1; j < array.length; j++)
        {
            if(array[j] < currentMin)
            {
                currentMin = array[j];
                minIndex = j;
            }
        }

        if(minIndex != i)
        {
            swap(array, i, j);
        }
    }

    console.log(array);

    return array;
}

var myArray = [2, 50, 8, 4, 3, -400, 12, 120];
var sorted = selectionSort(myArray);
document.write('<p>Unsorted: ' + String(myArray) + '</p>');
document.write('<p>Sorted: ' + String(sorted) + '</p>');

结果:

这是一些日志的屏幕截图:

我做错了什么导致出现所有这些未定义？

Answer 1

问题出在这里:

swap(array, i, j);

当你调用它时，j是array.length，因此array[j]是undefined，因为你已经超出了数组的末尾。

我想你的意思是:

swap(array, i, minIndex);
// ------------^^^^^^^^

进行此更改后，在对“未排序”行进行排序之前而不是之后输出数组:

function selectionSort(array)
{
    let currentMin = 0;
    var minIndex = 0;

    function swap(array, i, j)
    {
        let temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    for(var i = 0; i < array.length - 1; i++)
    {
        console.log(array);
        currentMin = array[i];
        minIndex = i;

        for(var j = i + 1; j < array.length; j++)
        {
            if(array[j] < currentMin)
            {
                currentMin = array[j];
                minIndex = j;
            }
        }

        if(minIndex != i)
        {
            swap(array, i, minIndex);
        }
    }

    console.log(array);

    return array;
}

var myArray = [2, 50, 8, 4, 3, -400, 12, 120];
document.write('<p>Unsorted: ' + String(myArray) + '</p>');
selectionSort(myArray);
document.write('<p>Sorted: ' + String(myArray) + '</p>');

<小时/>

重要的是要了解 selectionSort 对数组进行就地操作，它不会创建新数组。从你的原始代码来看，你似乎认为它是这样的:

var myArray = [2, 50, 8, 4, 3, -400, 12, 120];
var sorted = selectionSort(myArray);
document.write('<p>Unsorted: ' + String(myArray) + '</p>');
document.write('<p>Sorted: ' + String(sorted) + '</p>');

sorted 和 myArray 都指向同一个数组(sorted === myArray 为 true)，这就是为什么两行都显示数组的内容在上使用selectionSort，甚至是“未排序”行。

如果您想返回一个新数组，您可以首先在selectionSort中复制该数组，如下所示:

array = array.slice();

或者在现代环境中，array = Array.from(array);。

但是如果您要创建一个新数组，插入排序可能比这种排序算法更有效。 (还有其他用于就地排序的算法，其中大多数对于大多数输入数据都比此算法更有效。)