关于前端:冒泡排序

20次阅读

共计 711 个字符,预计需要花费 2 分钟才能阅读完成。

冒泡排序

原文链接:https://note.noxussj.top/?source=sifo

什么是冒泡排序(bubbleSort)?

冒泡排序是所有排序算法中最简略的一种,当然也是性能最差的一种。冒泡排序的思维其实很简略,就如它的名字一样在水中 “ 冒泡 ”。水中有很多散乱的小气泡,而后一个个气泡往水面上冒出。

例如一组无序的数组,最右边就是水底,最左边就是水面,最右边的元素一直的跟左边的元素比拟,最初替换地位到最左边。


算法步骤

  1. 冒泡排序会比拟所有相邻的元素
  2. 从第一个数开始,每两个相邻的数进行比拟
  3. 这两个相邻的数比拟完后,依照小的放在右边,大的放在左边的想法,替换它们的地位
  4. 执行完一轮后,大的数就会被排到最左边
  5. 反反复复反复 n – 1 遍后,整个排序就实现了

动画演示链接

https://visualgo.net/zh/sorting


根底案例

  • 工夫复杂度:O (n ^ 2)
  • 空间复杂度:O (1)
    Array.prototype.bubbleSort = function () {for (let i = 0; i < this.length - 1; i++) {for (let j = 0; j < this.length - 1 - i; j++) {if (this[j] > this[j + 1]) {const temp = this[j]
                    this[j] = this[j + 1]
                    this[j + 1] = temp
                }
            }
        }
    }
    
    const arr = [5, 4, 3, 2, 1]
    
    arr.bubbleSort() // [1, 2, 3, 4, 5]

代码中存在两个嵌套循环,所以工夫复杂度是 O (n ^ 2),而空间复杂度是 O (1),因为没有应用会随着数据增大而增大的变量。


原文链接:https://note.noxussj.top/?source=sifo

正文完
 0