tags: [算法]

    1. 冒泡排序思想

    bubbleSort.gif

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

    1. 代码实现
    1. function bubbleSort(arr) {
    2.   for (let i = 0; i < arr.length - 1; i++) {
    3.     for (let j = 0; j < arr.length - i - 1; j++) {
    4.       if (arr[j] > arr[j + 1]) {
    5.         var temp = arr[j];
    6.         arr[j] = arr[j + 1];
    7.         arr[j + 1] = temp;
    8.       }
    9.     }
    10.   }
    11.   console.log(arr);
    12.   return arr;
    13. }

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

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

    1. // 优化内层循环
    2. function bubbleSort3(arr) {
    3.   let k = arr.length - 1;
    4.   let pos = 0;
    6.   for (let i = 0; i < arr.length - 1; i++) {
    7.     for (let j = 0; j < pos; j++) {
    8.       if (arr[j] > arr[j + 1]) {
    9.         var temp = arr[j];
    10.         arr[j] = arr[j + 1];
    11.         arr[j + 1] = temp;
    12.         pos = j; // 记录本趟排序中，最后一次的位置变化，该位置之后的为有序序列，无需再进行比较
    13.       }
    14.     }
    16.     k = pos;
    17.   }
    19.   console.log(arr);
    20.   return arr;
    21. }

    （3) 同时优化

    1. // 优化内外层循环
    2. function bubbleSort4(arr) {
    3.   let k = arr.length - 1;
    4.   let pos = 0;
    6.   for (let i = 0; i < arr.length - 1; i++) {
    7.     let flag = false;
    8.     for (let j = 0; j < k; j++) {
    9.       if (arr[j] > arr[j + 1]) {
    10.         var temp = arr[j];
    11.         arr[j] = arr[j + 1];
    12.         arr[j + 1] = temp;
    13.         pos = j;
    14.         flag = true;
    15.       }
    16.     }
    18.     k = pos;
    20.     if (!flag) { // 整趟排序未发生元素交换，排序完成
    21.       break;
    22.     }
    23.   }
    24.   console.log(arr);
    25.   return arr;
    26. }
    1. 运行时间比较

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

    1. const arr = [44, 3, 5, 2, 15, 38, 47, 19, 27, 36, 46, 48, 50];
    3. logger(bubbleSort)(arr.slice());
    4. logger(bubbleSort2)(arr.slice());
    5. logger(bubbleSort3)(arr.slice());
    6. logger(bubbleSort4)(arr.slice());
    9. function logger(func) {
    10.   const start = Date.now();
    11.   return function(...args) {
    12.     const res = func(...args);
    13.     const end = Date.now();
    14.     console.log(`${func.name} costs time(ms):`, end - start);
    15.     return res;
    16.   }
    17. }