为什么要在选择排序算法中存储数组的长度？

Question

Grokking算法书的算法代码：

const findSmallestIndex = (array) => {
  let smallestElement = array[0]; // Stores the smallest value
  let smallestIndex = 0; // Stores the index of the smallest value

  for (let i = 1; i < array.length; i++) {
    if (array[i] < smallestElement) {
      smallestElement = array[i];
      smallestIndex = i;
    }
  }

  return smallestIndex;
};

// 2. Sorts the array
const selectionSort = (array) => {
  const sortedArray = [];
  const length = array.length;

  for (let i = 0; i < length; i++) {
    // Finds the smallest element in the given array 
    const smallestIndex = findSmallestIndex(array);
    // Adds the smallest element to new array
    sortedArray.push(array.splice(smallestIndex, 1)[0]);
  }

  return sortedArray;
};

console.log(selectionSort([5, 3, 6, 2, 10])); // [2, 3, 5, 6, 10]

问题出在函数 selectionSort 中，将数组长度存储在变量中是使其正常工作所必需的，而这个我无法理解，我试图不将长度存储在变量中:

const selectionSort = (array) => {
  const sortedArray = [];


  for (let i = 0; i < array.length; i++) {
    // Finds the smallest element in the given array 
    const smallestIndex = findSmallestIndex(array);
    // Adds the smallest element to new array
    sortedArray.push(array.splice(smallestIndex, 1)[0]);
  }

  return sortedArray;
};

console.log(selectionSort([5, 3, 6, 2, 10])); // [2, 3, 5]

我猜想可能是splice方法的问题，因为它在循环中每次都减少了长度，但我认为索引在这里并不重要，所以它可能不是问题所在！

Answer 1

您的代码正在从原始数组中删除元素，因此在每次迭代中，i++ 增加 i 并且 splice 减少 array.length。这意味着 i 和 array.length 每次靠得更近 2 倍而不是 1 倍，所以循环只迭代你想要的次数的一半。这意味着您只将一半的元素排序为 sortedArray.

通过先复制const length = array.length;，变量length在循环内没有改变，所以i++使得i更接近length迭代1次，所以迭代次数是原始数组长度，每个元素都被排序。

附带说明一下，您的算法排序到一个新数组中，但将原始数组留空。那可能永远不是您想要的；排序算法应该就地对数组进行排序（按排序顺序保留原始数组），或者 return 一个新的排序数组（保留原始数组不变）。您可以通过在函数开始时制作 array 的副本来解决此问题，因此算法会破坏副本而不是原始副本。

Answer 2

我把它放在这里的唯一原因是发布的实现显然来自算法文本，不必要地过于复杂且效率低下。

function selectionSort(array) {
  function smallestIndex(start) {
    let si = start;
    for (let i = start + 1; i < array.length; ++i) {
      if (array[i] < array[si])
        si = i;
    }
    return si;
  }

  for (let i = 0; i < array.length; i++) {
    let index = smallestIndex(i), t;
    // swap value into current slot
    t = array[index];
    array[index] = array[i];
    array[i] = t;
  }
  return array;
}

这里对smallestIndex()函数进行了增强，将起始位置作为参数。因此它在数组的 remainder 中找到最小值的索引。在第一次迭代中，这将是整个数组中的最小值。该值与当前起点处的任何值交换，因此在第一次通过主循环后，数组中的位置 0 是整个数组中的最小值。

在下一次迭代中，索引的搜索从 1 开始，因此该过程将从原始数组中找到 第二小的 值，并将其交换到位置 1。

该过程继续遍历数组。请注意，没有构造新数组，也没有调用线性时间数组方法。

为什么要在选择排序算法中存储数组的长度？

Why should length of the array be stored in selection sort algorithm?

javascript

arrays

algorithm

selection-sort