详解冒泡排序

算法
  1. 冒泡排序思想

bubbleSort.gif

可以通过上面这张图对冒泡排序有个简单的理解。
思想：将数组中的元素从头开始两两进行比较，如果比较中的两个元素第一个元素大于第二个元素，则两元素进行交换，最终，通过一趟比较，数组的最后一个元素就是所有元素中的最大值。同理，第二趟比较，会得到次大值。经过 n - 1 趟比较（n 为元素个数），会得到一个由小到大排列的有序数组。我们把每趟排序得到的最大值看作是冒出水面的泡泡的话，整个过程像是一个冒泡的过程。

  1. 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
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]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  console.log(arr);
  return arr;
}

第一趟扫描: i = 0，从第 0 个元素比较到第 n - i - 1 个元素，得出最大值 v1，索引为 n -1(最后一个元素), 有序序列为 [n - 1];
第二趟扫描: i = 1，从第 0 个元素比较到第 n - i - 1 - 1 个元素，得出最大值 v2，索引为 n -2(最后一个元素), 有序序列为 [n - 2, n - 1];
第 k 趟扫描: i = k - 1，从第 0 个元素比较到第 n - i - k 个元素，得出最大值 v2，索引为 n - k(最后一个元素), 有序序列为 [n - k, n - 1];
当 k = n - 1 时，有序序列为 [1, n-1], 第 0 个元素自然为最小值， 整个排序过程结束;

  1. 优化

（1) 优化外层循环。
思想：当某趟循环未发生过元素交换时，说明整个序列早已有序，不需要再进行比较，可立即结束排序过程。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 优化外层循环
function bubbleSort2(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let flag = false;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        flag = true; // 当一趟排序中有过元素交换时，置为 true;
      }
    }
    if (!flag) { // 整趟排序未发生元素交换，排序完成
      break;
    }
  }
  console.log(arr);
  return arr;
}

（2) 优化内层循环。
思想：记录内存循环时最后一次进行元素交换的位置，该位置之后的元素为有序序列，不需要再参与比较。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 优化内层循环
function bubbleSort3(arr) {
  let k = arr.length - 1;
  let pos = 0;

  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < pos; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        pos = j; // 记录本趟排序中，最后一次的位置变化，该位置之后的为有序序列，无需再进行比较
      }
    }
    
    k = pos;
  }

  console.log(arr);
  return arr;
}

（3) 同时优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 优化内外层循环
function bubbleSort4(arr) {
  let k = arr.length - 1;
  let pos = 0;

  for (let i = 0; i < arr.length - 1; i++) {
    let flag = false;
    for (let j = 0; j < k; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        pos = j;
        flag = true;
      }
    }
    
    k = pos;
    
    if (!flag) { // 整趟排序未发生元素交换，排序完成
      break;
    }
  }
  console.log(arr);
  return arr;
}
  1. 运行时间比较

写了个方法来打印运行时间，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const arr = [44, 3, 5, 2, 15, 38, 47, 19, 27, 36, 46, 48, 50];

logger(bubbleSort)(arr.slice());
logger(bubbleSort2)(arr.slice());
logger(bubbleSort3)(arr.slice());
logger(bubbleSort4)(arr.slice());


function logger(func) {
  const start = Date.now();
  return function(...args) {
    const res = func(...args);
    const end = Date.now();
    console.log(`${func.name} costs time(ms):`, end - start);
    return res;
  }
}