排序-冒泡排序

冒泡排序(Bubble Sort)一种简单的计算机排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

代码实现

1.时间复杂度固定为O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 冒泡排序 
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 90]
function dubbleSort (arr) {
for(let i = 0; i < num.length;i++) {
for(let j = 0;j < num.length - i - 1;j++) {
if(num[j] < num[j + 1]) {
[num[j], num[j + 1]] = [num[j+1], num[j]]
}
}
}
return num
}
dubbleSort(num)
// 输出结果 [90, 89, 82, 64, 55, 50, 37, 34, 32, 22, 5, 3]

2.时间复杂度最优情况为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var num = [4, 3, 2, 1]
function dubbleSort (arr) {
let didSwap = false
for(let i = 0; i < num.length;i++) {
didSwap = false
for(let j = 0;j < num.length - i - 1;j++) {
if(num[j] < num[j + 1]) {
[num[j], num[j + 1]] = [num[j+1], num[j]]
didSwap = true
}
}
if (!didSwap) {
return arr
}
}
return arr
}
dubbleSort(num)
// 输出结果 [4, 3, 2, 1] 复杂度O(n)