前言
冒泡排序，是一个相对较为简单易于理解的排序算法。下面以升序为例。
正文
原理
- 比较相邻的两个元素a、b。若 a > b，则互换 a 与 b 的位置，否则不变。
- 按照上面的规则，第一轮循环次数为
array.length - 1，一轮循环结束，数组最后一项应该是最大数。 - 第二轮开始，循环次数为
array.length - 1 - 1，同样把本次循环的最大项互换到array[length - 1 - 1]的位置上。 - 以此类推...
图示
冒泡排序
实现
// 冒泡排序（升序） function bubbleSort(arr) { for (let i = 0; i < arr.length - 1; i++) { for (let j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } } return arr; } const array = [8, 12, 4, 0, 22, 8, 21, 3, 56]; console.log(bubbleSort(array)); // [0, 3, 4, 8, 8, 12, 21, 22, 56]
时间复杂度
可知冒泡排序执行次数是 (n-1) + (n-2) + ... + 2 + 1 = (n^2 - n)/2，根据时间复杂度推导方式，可得到 O(n^2)。
