时间戳

首页 > 解决方案 > 一个简单的 selectionSort 但无休止地运行

javascript - 一个简单的 selectionSort 但无休止地运行

问题描述

我写了一个简单的seletionSort：

function selectionSort(arr) {
    let copyArr = [...arr];
    let newArr = [];
    while (copyArr) {
        minimum = Math.min(...copyArr);
        newArr.push(minimum);
        console.log("newArr", newArr);
        copyArr.splice(arr.indexOf(minimum), 1);
        console.log("copyArr", copyArr);
    }
    return newArr;
}

不幸的是，当应用到时arr = [-7, 34, 27, 87, 21, 0, -11]，它会无休止地运行并输出：

newArr [ -11 ]
copyArr [ -7, 34, 27, 87, 21, 0 ]
newArr [ -11, -7 ]
copyArr [ 34, 27, 87, 21, 0 ]
newArr [ -11, -7, 0 ]
copyArr [ 34, 27, 87, 21, 0 ]
...
newArr [
-11, -7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0,  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0,  0, 0, 0,
... 752 more items
]

有什么问题？

标签： javascript

解决方案

你有两个主要问题：

  1. 数组总是真实的，即使它们是空的[]。这意味着您的 while 循环将继续执行，因为在您的条件下[]使用时将被评估为 true 。while您可以将条件更改为在长度为 0 时停止，这可以通过检查是否.length为真/假来完成。

  2. 您正在从数组中拼接错误的索引。目前，您正在使用数组，但这会在删除arr.indexOf(minimum)任何元素之前为您提供元素的索引。copyArray这意味着元素arr的索引 from 与索引 from 不匹配copyArray。您可以更改它以查找copyArray.indexOf()索引，以在 copyArray 中找到最小值的正确索引

function selectionSort(arr) {
  let copyArr = [...arr];
  let newArr = [];
  while (copyArr.length) {
    minimum = Math.min(...copyArr);
    newArr.push(minimum);
    console.log("newArr", newArr);
    copyArr.splice(copyArr.indexOf(minimum), 1);
    console.log("copyArr", copyArr);
  }
  return newArr;
}

console.log(selectionSort([4, 2, 10, 1]));

对于稍微优化的解决方案，请考虑创建一个函数来查找最小数字的索引，然后执行交换。这样你就不需要迭代数组两次来找到最小数字然后找到那个数字的位置

function findMinIndex(arr, start) {
  let minIdx = start;
  for(let i = start+1; i < arr.length; i++) {
    if(arr[i] < arr[minIdx]) {
      minIdx = i;
    }
  }
  return minIdx;
}

function selectionSort([...arr]) {
  for(let i = 0; i < arr.length-1; i++) {
    const minIdx = findMinIndex(arr, i); // get pos of min
    // Swap the two elements around
    const tmp = arr[i]; 
    arr[i] = arr[minIdx];
    arr[minIdx] = tmp;
  }
  return arr;
}

console.log(selectionSort([4, 2, 10, 1]));

推荐阅读