x-note
Search…
冒泡排序
冒泡排序是最经典的排序算法之一，重复地走访要排序的数列，依次比较两个元素，如果顺序错误就把它们交换过来，直到排序完成。
- 平均时间复杂度：
- 最好时间复杂度：
- 最坏时间复杂度：
- 空间复杂度：
- 稳定性：稳定
- 排序方式：原地（In-place）
运作方式：
- 1.比较相邻的元素。如果第一个比第二个大，交换；
- 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对；
- 3.针对所有的元素重复以上的步骤；
- 4.持续每次对越来越少的元素重复上述步骤，直到没有任何一组数字需要比较。
具体实现：
1
function bubbleSort(arr) {
2
const len = arr.length;
3
for (let i = 0; i < len - 1; ++i) {
4
for (let j = 0; j < len - 1 - i; ++j) {
5
if (arr[j] > arr[j+1]) {
6
swap(arr, j, j+1);
7
}
8
}
9
}
10
return arr;
11
}
12
13
// 交换数组的两个索引的值
14
function swap(arr, i, j) {
15
const tmp = arr[i];
16
arr[i] = arr[j];
17
arr[j] = tmp;
18
}
Copied!
冒泡排序虽然是简单的排序算法之一，但是大多数人多实现的方式都是错误的，最常见的错误的冒泡排序：
1
function errorBubbleSort(arr) {
2
const len = arr.length;
3
for (let i = 0; i < len; ++i) {
4
for (let j = 0; j < len; ++j) {
5
if (arr[i] < arr[j]) {
6
swap(arr, i, j);
7
}
8
}
9
}
10
return arr;
11
}
12
errorBubbleSort([5, 3, 1, 2, 4]); // [1, 2, 3, 4, 5]
13
14
function errorBubbleSort2(arr) {
15
const len = arr.length;
16
for (let i = 0; i < len; ++i) {
17
for (let j = i + 1; j < len; ++j) {
18
if (arr[i] > arr[j]) {
19
swap(arr, i, j);
20
}
21
}
22
}
23
return arr;
24
}
25
errorBubbleSort2([5, 3, 1, 2, 4]); // [1, 2, 3, 4, 5]
Copied!
Last modified 3yr ago
Copy link