冒泡排序
原文链接：https://note.noxussj.top/?source=sifo
什么是冒泡排序（bubbleSort）？
冒泡排序是所有排序算法中最简略的一种，当然也是性能最差的一种。冒泡排序的思维其实很简略，就如它的名字一样在水中 "冒泡"。水中有很多散乱的小气泡，而后一个个气泡往水面上冒出。
例如一组无序的数组，最右边就是水底，最左边就是水面，最右边的元素一直的跟左边的元素比拟，最初替换地位到最左边。
算法步骤
- 冒泡排序会比拟所有相邻的元素
- 从第一个数开始，每两个相邻的数进行比拟
- 这两个相邻的数比拟完后，依照小的放在右边，大的放在左边的想法，替换它们的地位
- 执行完一轮后，大的数就会被排到最左边
- 反反复复反复 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