冒泡排序
原理解析
选择第1个和第2个数字,如果第1个>第2个二者交换位置(假设是升序排列)。之后选择第2个和第3个数字,类似交换处理。一轮下来后,最大的数字会“冒泡”到最后一位。
接下来,忽略已经拍好的数字,对于剩下的数字再来一轮
...
直到所有的数字都排列完成。
范例演示
以下表格里,红色表示选中的待排序的数字,粗体表示本轮刚刚排列过的数字,蓝色表示最终排好的数字。
第一轮:
- 选择 10 和 34, 进行比较, 其中 10 < 34, 二者不需要交换
- 选择 34 和 21, 进行比较, 其中 34 > 21, 二者需要交换
- 选择 34 和 47, 进行比较, 其中 34 < 47, 二者需不要交换
- 选择 47 和 3, 进行比较, 其中 47 > 3, 二者需要交换
- ...
- 最后 47 交换到末尾
第二轮:
忽略已经排列好的47, 按照刚刚的逻辑再次排序
...
第一轮 | 10 | 34 | 21 | 47 | 3 | 28 |
10 | 34 | 21 | 47 | 3 | 28 | |
10 | 21 | 34 | 47 | 3 | 28 | |
10 | 21 | 34 | 47 | 3 | 28 | |
10 | 21 | 34 | 3 | 47 | 28 | |
10 | 21 | 34 | 3 | 28 | 47 | |
第二轮 | 10 | 34 | 21 | 3 | 28 | 47 |
10 | 34 | 21 | 3 | 28 | 47 | |
10 | 21 | 34 | 3 | 28 | 47 | |
10 | 21 | 3 | 34 | 28 | 47 | |
10 | 21 | 3 | 28 | 34 | 47 | |
第三轮 | 10 | 21 | 3 | 28 | 34 | 47 |
10 | 21 | 3 | 28 | 34 | 47 | |
10 | 3 | 21 | 28 | 34 | 47 | |
10 | 3 | 21 | 28 | 34 | 47 | |
第四轮 | 10 | 3 | 21 | 28 | 34 | 47 |
3 | 10 | 21 | 28 | 34 | 47 | |
3 | 10 | 21 | 28 | 34 | 47 | |
第五轮 | 3 | 10 | 21 | 28 | 34 | 47 |
3 | 10 | 21 | 28 | 34 | 47 |
实现方式
function bubleSort(arr) {
for(let i = 0; i < arr.length /*i代表轮数*/; i++) {
for(let j = 0; j < arr.length - i /*j代表当前轮选中的元素下标*/; j++) {
if(arr[j] > arr[j+1]) {
[ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ] /*交换元素*/
}
//console.log(arr)
}
}
}
var arr = [10, 34, 21, 47, 3, 28]
bubleSort(arr)
console.log(arr)
效率测试
下面我们测试排序性能。以下的代码中,randomArr 函数会生成一个随机数组, 数组长度默认是100, 最大值默认值是1000。 console.time 和 console.end 用来记录排序时间。
let arr = randomArr(10000, 100)
console.time('bubleSort')
bubleSort(arr)
console.timeEnd('bubleSort')
function randomArr( arrLen = 100, maxValue = 1000 ) {
let arr = []
for(let i = 0; i < arrLen; i++) {
arr[i] = Math.floor((maxValue+1)*Math.random())
}
return arr
}
function bubleSort(arr) {
for(let i = 0; i < arr.length; i++) {
for(let j = 0; j < arr.length - i; j++) {
if(arr[j] > arr[j+1]) {
[ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ] /*交换元素*/
}
}
}
}
经浏览器测试,数组长度增加10倍,排序时间约增加100倍
复杂度分析
时间复杂度(可以理解为排序的次数)计算: (n-1) + (n-2) + ... + 1 = n*(1 + (n-1))/2,所以时间复杂度为 O(n^2) ,和上面的测试基本一致