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

鹰码

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方法上,因为它每次都减少了循环的长度,但是我认为索引在这里并不重要,因此可能不是问题!

kaya3

您的代码正在从原始数组中删除元素,因此,在每次迭代中,都会i++增加i,也会splice减少array.length这意味着iarray.length每一次的,而不是由1获得靠得更近2,这样你想让它循环迭代仅一半多的时间。这意味着您只将一半的元素归类为sortedArray

通过const length = array.length;首先复制,变量length不会在循环内更改,因此每次迭代都i++使变量i更接近length1,因此迭代次数是原始数组长度,并且每个元素都进行了排序。

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

本文收集自互联网,转载请注明来源。

如有侵权,请联系[email protected] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

为什么排序数组中需要临时存储?

来自分类Dev

为什么我的自适应选择排序算法在C ++中不起作用

来自分类Dev

为什么在这种排序算法实现中向量比数组显着慢?

来自分类Dev

为什么在Merge-Sort算法中有必要在对数组进行排序之前将其分为两部分?

来自分类Dev

为什么我的选择排序不显示正确排序的数组?

来自分类Dev

为什么排序算法失败?

来自分类Dev

在选择排序中,降序数组的性能比升序数组更快。为什么?

来自分类Dev

在Dymola解决DAE中,为什么要在执行Patelides算法之后使用DASSL算法?

来自分类Dev

为什么要在变量中存储Promise对象?

来自分类Dev

Java中的选择排序算法

来自分类Dev

为什么要在数组O(1)中查找?

来自分类Dev

为什么要在JS中推送数组引用而不是PHP

来自分类Dev

为什么我的选择对数组进行无序排序?

来自分类Dev

我们为什么要在某些递归算法中复制ArrayList?

来自分类Dev

为什么此算法中的数组索引超出范围?

来自分类Dev

为什么我的指针算法在此数组中失败

来自分类Dev

为什么我的选择排序算法不做它应该做的事情(java)?

来自分类Dev

C#中的IndexOutOfRangeException –为什么数组的长度变为0?

来自分类Dev

为什么要在JavaScript中的JSON对象数组中创建额外的数组数组

来自分类Java

为什么要使用两种不同的算法对数组进行排序?

来自分类Dev

当数组具有重复值时,为什么快速排序算法的持续时间会增加?

来自分类Dev

为什么Fedora的dnf按长度排序?

来自分类Dev

为什么要在jwt标头中发送算法

来自分类Dev

为什么选择排序比气泡排序快?

来自分类Dev

我应该选择哪种算法,为什么?

来自分类Dev

为什么要在MySQL中为UTF8文本数据设置排序规则?

来自分类Dev

为什么要在Forge laravel中重新安装存储库以更改环境中的数据?

来自分类Java

排序小整数数组的最佳排序算法是什么?

来自分类Dev

为什么列表中的元素数称为“大小”,而数组的长度称为“长度”?

Related 相关文章

  1. 1

    为什么排序数组中需要临时存储?

  2. 2

    为什么我的自适应选择排序算法在C ++中不起作用

  3. 3

    为什么在这种排序算法实现中向量比数组显着慢?

  4. 4

    为什么在Merge-Sort算法中有必要在对数组进行排序之前将其分为两部分?

  5. 5

    为什么我的选择排序不显示正确排序的数组?

  6. 6

    为什么排序算法失败?

  7. 7

    在选择排序中,降序数组的性能比升序数组更快。为什么?

  8. 8

    在Dymola解决DAE中,为什么要在执行Patelides算法之后使用DASSL算法?

  9. 9

    为什么要在变量中存储Promise对象?

  10. 10

    Java中的选择排序算法

  11. 11

    为什么要在数组O(1)中查找?

  12. 12

    为什么要在JS中推送数组引用而不是PHP

  13. 13

    为什么我的选择对数组进行无序排序?

  14. 14

    我们为什么要在某些递归算法中复制ArrayList?

  15. 15

    为什么此算法中的数组索引超出范围?

  16. 16

    为什么我的指针算法在此数组中失败

  17. 17

    为什么我的选择排序算法不做它应该做的事情(java)?

  18. 18

    C#中的IndexOutOfRangeException –为什么数组的长度变为0?

  19. 19

    为什么要在JavaScript中的JSON对象数组中创建额外的数组数组

  20. 20

    为什么要使用两种不同的算法对数组进行排序?

  21. 21

    当数组具有重复值时,为什么快速排序算法的持续时间会增加?

  22. 22

    为什么Fedora的dnf按长度排序?

  23. 23

    为什么要在jwt标头中发送算法

  24. 24

    为什么选择排序比气泡排序快?

  25. 25

    我应该选择哪种算法,为什么?

  26. 26

    为什么要在MySQL中为UTF8文本数据设置排序规则?

  27. 27

    为什么要在Forge laravel中重新安装存储库以更改环境中的数据?

  28. 28

    排序小整数数组的最佳排序算法是什么?

  29. 29

    为什么列表中的元素数称为“大小”,而数组的长度称为“长度”?

热门标签

归档