x-note
Search…
冒泡排序
冒泡排序是最经典的排序算法之一,重复地走访要排序的数列,依次比较两个元素,如果顺序错误就把它们交换过来,直到排序完成。
  • 平均时间复杂度:
    O(n2)O(n^2)
  • 最好时间复杂度:
    O(n)O(n)
  • 最坏时间复杂度:
    O(n2)O(n^2)
  • 空间复杂度:
    O(1)O(1)
  • 稳定性:稳定
  • 排序方式:原地(In-place)
运作方式:
  1. 1.
    比较相邻的元素。如果第一个比第二个大,交换;
  2. 2.
    对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对;
  3. 3.
    针对所有的元素重复以上的步骤;
  4. 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!
Copy link