冒泡排序（Bubble Sort）

  • 冒泡排序的每一轮比较都是从左到右，进行单向的位置交换
  • 核心思想：比较数组中的两个相邻元素，较大的值需要排在后面，每一轮比较的时候都需要获取到最大值并将它排到最后面，下一轮比较的时候，需要排除前几轮获取到的最大值再进行比较。
  1. // 一个长度为 n 的数组，相邻元素之间的比较
  2. // 第一轮比较只需要 n-1 次，就可以将最大值排到数组的末尾
  3. // 第二轮比较的时候，不再需要比较上一轮比较得出的最大值，所以只需要 n-1-1 次，就可以将到第二大的值排到数组的倒数第二位
  4. // 第三轮比较的时候，不再需要比较前几轮比较得出的值，所以只需要 n-1-2 次，就可以将到第三大的值排到数组的倒数第三位
  5. // ...
  7. // 一个长度为 3 的数组，相邻元素之间的比较
  8. // 因为第一轮比较时，已经将最大值排到数组的末尾了，接下来只需要比较剩余的两个元素大小
  9. // 所以需要比较 2 轮     // [3,4,5] 和 [3,5,4] 都需要比较两轮，不能用肉眼去判断是否比较完了
  10. // 一个长度为 4 的数组，相邻元素之间的比较
  11. // 需要比较 3 轮
  12. // ...
  14. // 因此可以得出一个规律
  15. // 一个长度为 n 的数组，相邻元素之间的比较，最多需要进行 n-1 轮，每轮比较 n-1-i 次
  17. function bubbleSort(arr) {
  18.     var len = arr.length;
  19.     for (var i = 0; i < len - 1; i++) {
  20.         for (var j = 0; j < len - 1 - i; j++) {
  21.             if (arr[j] > arr[j + 1]) {        //相邻元素两两对比
  22.                 var temp = arr[j + 1];        //元素交换
  23.                 arr[j + 1] = arr[j];
  24.                 arr[j] = temp;
  25.             }
  26.         }
  27.     }
  28.     return arr;
  29. }
  31. var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
  32. var arr2 = [50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];
  33. var arr3 = [48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2, 50];
  34. console.log(bubbleSort(arr));
  35. console.log(bubbleSort(arr2));
  36. console.log(bubbleSort(arr3));

冒泡排序的优化

优化第一步

  • 使用 while 代替 for 循环，提高遍历速度
  1. function bubbleSort2(arr) {
  2.     var len = arr.length;
  3.     console.time('222改进后冒泡排序耗时');
  4.     var i = 0;
  5.     while (i < len - 1) {
  6.         var j = 0;
  7.         while (j < len - 1 - i) {
  8.             if (arr[j] > arr[j + 1]) {        //相邻元素两两对比
  9.                 var temp = arr[j + 1];        //元素交换
  10.                 arr[j + 1] = arr[j];
  11.                 arr[j] = temp;
  12.             }
  13.             j++;
  14.         }
  15.         i++;
  16.     }
  17.     console.timeEnd('222改进后冒泡排序耗时');
  18.     return arr;
  19. }

优化第二步

以一个 [3,4,5] 数组为例，当第一轮比较完的时候，通过肉眼可以观察到这个数组已经是一个有序的数组了。但是上面的排序算法还是兢兢业业地继续执行了第二轮的比较（比较3和4）。如果能判断出数列已经有序并作出标记，那么剩下的几轮排序就不必执行了，可以提前结束。

  1. function bubbleSort3(arr) {
  2.     var len = arr.length;
  3.     var i = 0;
  4.     while (i < len - 1) {
  5.         // 有序标记，每一轮的初始值都为 true
  6.         var j = 0, isSorted = true;
  7.         while (j < len - 1 - i) {
  8.             if (arr[j] > arr[j + 1]) {        //相邻元素两两对比
  9.                 var temp = arr[j + 1];        //元素交换
  10.                 arr[j + 1] = arr[j];
  11.                 arr[j] = temp;
  12.                 // 只要有元素进行了交换，那么就不是有序的，标记变成 false
  13.                 isSorted = false;
  14.             }
  15.             j++;
  16.         }
  17.         // 当有序标记成立时，提前退出循环
  18.         if (isSorted) {
  19.             break;
  20.         }
  21.         i++;
  22.         console.log(i);
  23.     }
  24.     return arr;
  25. }
  27. var arr1 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];
  28. var arr2 = [3, 2, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50, 52, 53, 55, 58, 60];
  29. bubbleSort3(arr1);// 打印 i 的值： 1-19
  30. bubbleSort3(arr2);// 打印 i 的值：1

优化第三步

  • 上面那一步的优化方案，还有待改进的地方。以一个 [3, 4, 2, 1, 5, 6] 数组为例，前半部分的元素是无序的（3、4、2、1），后半部分的元素是有序的（5、6）。
    • 第一轮比较
      • 第一次比较：3和4比较 => 3,4,2,1,5,6
      • 第二次比较：4和2比较 => 3,2,4,1,5,6
      • 第三次比较：4和1比较 => 3,2,1,4,5,6
      • 第四次比较：4和5比较 => 3,2,1,4,5,6
      • 第五次比较：5和6比较 => 3,2,1,4,5,6
    • 第二轮比较
      • 第一次比较：3和2比较 => 2,3,1,4,5,6
      • 第二次比较：3和1比较 => 2,1,3,4,5,6
      • 第三次比较：3和4比较 => 2,1,3,4,5,6
      • 第四次比较：4和5比较 => 2,1,3,4,5,6
      • 第五次比较：5和6比较 => 2,1,3,4,5,6

可以明显的看到，右边的元素很早就是有序的了（已经排序好了），但是每一轮还是白白的比较了很多次。这个问题的关键点在于对数列有序区的界定，每一轮比较的时候只比较无序区的数列。
解决方案：在每一轮比较完后，记录最后一次元素交换的位置，该位置就是无序区的边界，再往后就是有序区。

  1. function bubbleSort4(arr) {
  2.     var len = arr.length;
  3.     // 无序数列的边界，每次只需要比较无序数列
  4.     var sortBorder = len - 1;
  6.     // for (var i = 0; i < len - 1; i++) {
  7.     //     // 有序标记，每一轮的初始值为 true
  8.     //     var isSorted = true;
  9.     //     // 记录最后一次元素交换的位置
  10.     //     var lastExchangeIndex = 0;
  11.     //     // 每次只需要比较无序数列
  12.     //     for (var j = 0; j < sortBorder; j++) {
  13.     //         if (arr[j] > arr[j + 1]) {        //相邻元素两两对比
  14.     //             var temp = arr[j + 1];        //元素交换
  15.     //             arr[j + 1] = arr[j];
  16.     //             arr[j] = temp;
  17.     //             // 只要有元素进行了交换，那么就不是有序的，标记变成 false
  18.     //             isSorted = false;
  19.     //             lastExchangeIndex = j;
  20.     //         }
  21.     //     }
  22.     //     sortBorder = lastExchangeIndex;
  23.     //     // 当有序标记成立时，提前退出循环
  24.     //     if (isSorted) {
  25.     //         break;
  26.     //     }
  27.     //     console.log(i);
  28.     // }
  30.     while (sortBorder < len ) {
  31.         // 有序标记，每一轮的初始值为 true
  32.         var isSorted = true;
  33.         var j = 0;
  34.         // 记录最后一次元素交换的位置
  35.         var lastExchangeIndex = 0;
  36.         while (j < sortBorder) {
  37.             if (arr[j] > arr[j + 1]) {        //相邻元素两两对比
  38.                 var temp = arr[j + 1];        //元素交换
  39.                 arr[j + 1] = arr[j];
  40.                 arr[j] = temp;
  41.                 // 只要有元素进行了交换，那么就不是有序的，标记变成 false
  42.                 isSorted = false;
  43.                 lastExchangeIndex = j;
  44.             }
  45.             j++;
  46.         }
  47.         sortBorder = lastExchangeIndex;
  48.         // 当有序标记成立时，提前退出循环
  49.         if (isSorted) {
  50.             break;
  51.         }
  52.         console.log(sortBorder);
  53.     }
  55.     return arr;
  56. }
  58. var arr1 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];
  59. var arr2 = [3, 4, 2, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50, 52, 53, 55, 58, 60];
  60. bubbleSort4(arr1);
  61. bubbleSort4(arr2);

问题/疑问

当同时运行多个排序方法时，会有奇怪的现象

  1. function bubbleSort1(arr) {
  2.     var len = arr.length;
  3.     console.time('改进前冒泡排序耗时');
  4.     for (var i = 0; i < len - 1; i++) {
  5.         for (var j = 0; j < len - 1 - i; j++) {
  6.             if (arr[j] > arr[j + 1]) {        //相邻元素两两对比
  7.                 var temp = arr[j + 1];        //元素交换
  8.                 arr[j + 1] = arr[j];
  9.                 arr[j] = temp;
  10.             }
  11.         }
  12.     }
  13.     console.timeEnd('改进前冒泡排序耗时');
  14.     return arr;
  15. }
  17. function bubbleSort2(arr) {
  18.     var len = arr.length;
  19.     console.time('222改进后冒泡排序耗时');
  20.     var i = 0;
  21.     while (i < len - 1) {
  22.         var j = 0;
  23.         while (j < len - 1 - i) {
  24.             if (arr[j] > arr[j + 1]) {        //相邻元素两两对比
  25.                 var temp = arr[j + 1];        //元素交换
  26.                 arr[j + 1] = arr[j];
  27.                 arr[j] = temp;
  28.             }
  29.             j++;
  30.         }
  31.         i++;
  32.     }
  33.     console.timeEnd('222改进后冒泡排序耗时');
  34.     return arr;
  35. }
  37. function bubbleSort3(arr) {
  38.     var i = arr.length - 1;  //初始时,最后位置保持不变
  39.     console.time('333改进后冒泡排序耗时');
  40.     while (i > 0) {
  41.         var pos = 0; //每趟开始时,无记录交换
  42.         for (var j = 0; j < i; j++) {
  43.             if (arr[j] > arr[j + 1]) {
  44.                 pos = j; //记录交换的位置
  45.                 var tmp = arr[j];
  46.                 arr[j] = arr[j + 1];
  47.                 arr[j + 1] = tmp;
  48.             }
  49.         }
  50.         i = pos; //为下一趟排序作准备
  51.     }
  52.     console.timeEnd('333改进后冒泡排序耗时');
  53.     return arr;
  54. }
  56. function bubbleSort4(arr) {
  57.     var i = arr.length - 1;  //初始时,最后位置保持不变
  58.     console.time('444改进后冒泡排序耗时');
  59.     while (i > 0) {
  60.         var pos = 0, j = 0; //每趟开始时,无记录交换
  61.         while (j < i) {
  62.             if (arr[j] > arr[j + 1]) {
  63.                 pos = j; //记录交换的位置
  64.                 var tmp = arr[j];
  65.                 arr[j] = arr[j + 1];
  66.                 arr[j + 1] = tmp;
  67.             }
  68.             j++;
  69.         }
  70.         i = pos; //为下一趟排序作准备
  71.     }
  72.     console.timeEnd('444改进后冒泡排序耗时');
  73.     return arr;
  74. }
var arr1 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];
var arr2 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];
var arr3 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];
var arr4 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];

// 第一个先运行的耗时最长，如果注释第一个函数的话，第二个函数运行的耗时会变成最长的
// 后面的函数运行的耗时会很低
console.log(bubbleSort1(arr1));
console.log(bubbleSort2(arr2));
console.log(bubbleSort3(arr3));
console.log(bubbleSort4(arr4));

image.png

var arr1 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];
var arr2 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];
var arr3 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];
var arr4 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];

// 第一个先运行的耗时最长，如果注释第一个函数的话，第二个函数运行的耗时会变成最长的
// 后面的函数运行的耗时会很低
// console.log(bubbleSort1(arr1));
console.log(bubbleSort2(arr2));
console.log(bubbleSort3(arr3));
console.log(bubbleSort4(arr4));

image.png

var arr2 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];
console.log(bubbleSort1(arr2));
console.log(bubbleSort1(arr2));
console.log(bubbleSort1(arr2));

image.png

鸡尾酒排序（双向排序）

  • 冒泡排序的每一轮比较都是从左到右，进行单向的位置交换
  • 鸡尾酒排序是一种基于冒泡排序的升级排序法，元素的比较和交换过程是双向的
  • 优点：在特定的条件下，减少排序的回合数；
  • 缺点：代码量增加，不好阅读理解
  • 使用场景：在大部分元素已经有序的情况下，可以使用鸡尾酒排序

以一个 [2, 3, 4, 5, 6, 1] 数组为例，前面部分的元素是有序的（2、3、4、5、6），后面部分的元素是无序的（1）。

  • 第一轮比较
    • 第一次比较：2和3比较 => 2, 3, 4, 5, 6, 1
    • 第二次比较：3和4比较 => 2, 3, 4, 5, 6, 1
    • 第三次比较：4和5比较 => 2, 3, 4, 5, 6, 1
    • 第四次比较：5和6比较 => 2, 3, 4, 5, 6, 1
    • 第五次比较：6和1比较 => 2, 3, 4, 5, 1, 6
  • 第二轮比较
    • 第一次比较：2和3比较 => 2, 3, 4, 5, 1, 6
    • 第二次比较：3和4比较 => 2, 3, 4, 5, 1, 6
    • 第三次比较：4和5比较 => 2, 3, 4, 5, 1, 6
    • 第四次比较：5和1比较 => 2, 3, 4, 1, 5, 6
  • 第 n 轮比较…

问题：前面的部分已经是有序的了，就因为 1 的位置不对，需要好几轮的排序，有点浪费
解决方案：双向排序（排序过程就像钟摆一样） => 第一轮从左到右比较并进行元素交换，第二轮从右到左比较并进行元素交换，第三轮再从左到右…
核心思想：代码外层的大循环控制着所有的排序回合，大循环内部有两个小循环，第一个循环从左到右比较并交换元素，第二个循环从右到左比较并交换元素。

function bubbleSort5(array) {
    var tmp = 0;
    for (var i = 0; i < array.length / 2; i++) {
        // 有序标记，每一轮的初始是 true
        var isSorted = true;
        // 奇数轮，从左向右比较和交换
        for (var j = i; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
                // 有元素交换，所以不是有序，标记变为 false
                isSorted = false;
            }
        }
        if (isSorted) {
            break;
        }

        // 偶数轮之前，重新标记为 true
        isSorted = true;
        // 偶数轮，从右向左比较和交换
        for (var k = array.length - i - 1; k > i; k--) {
            if (array[k] < array[k - 1]) {
                tmp = array[k];
                array[k] = array[k - 1];
                array[k - 1] = tmp;
                // 有元素交换，所以不是有序，标记变为 false
                isSorted = false;
            }
        }
        if (isSorted) {
            break;
        }
    }
    return array;
}

var arr = [2, 3, 4, 5, 6, 1];
var arr1 = [60, 58, 55, 53, 52, 50, 48, 47, 46, 44, 38, 36, 27, 26, 19, 15, 5, 4, 3, 2];
var arr2 = [3, 4, 2, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50, 52, 53, 55, 58, 60];
console.log(bubbleSort5(arr));
console.log(bubbleSort5(arr1));
console.log(bubbleSort5(arr2));

选择排序

思路：

  • 找到数组中的最小值，选中它并将其放置在第一位。
  • 接着找到第二小的值，选中它并将其放置在第二位。
  • 以此类推，执行n-1轮。
    Array.prototype.selectionSort = function () {
  for (let i = 0; i < this.length - 1; i += 1) {
      let indexMin = i;
      for (let j = i; j < this.length; j += 1) {
          if (this[j] < this[indexMin]) {
              indexMin = j;
          }
      }
      if (indexMin !== i) {
          [this[i], this[indexMin]] = [this[indexMin], this[i]];
          // const temp = this[i];
          // this[i] = this[indexMin];
          // this[indexMin] = temp;
      }
  }
}
const arr = [5, 4, 3, 2, 1];
arr.selectionSort();
console.log(arr);

插入排序

思路：

  • 从第二个数开始往前比；
  • 比它大就往后排；
  • 以此类推进行到最后一个数；
Array.prototype.insertionSort = function () {
    for (let i = 1; i < this.length; i += 1) {
        const tmp = this[i];
        let j = i;
        while (j > 0) {
            if (this[j - 1] > tmp) {
                this[j] = this[j - 1];
            } else {
                break;
            }
            j -= 1;
        }
        this[j] = tmp;
    }
}

const arr = [5, 4, 3, 2, 1];
arr.insertionSort();
console.log(arr);

归并排序

排序算法动画网站
思路：

  • 分：把数组劈成两半，再递归地对子数组进行“分”操作，直到分成一个个单独的数。时间复杂度为 O(nlogn)；
  • 合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组。时间复杂度为 O(n)；
  • 最终的时间复杂度为：O(nlogn)；

image.png

分

// 先将数组拆分成一个个小的数组，每个数组里只包含一个元素
Array.prototype.mergeSort = function () {
    const rec = (arr) => {
        console.log('arr',arr);
        const len = arr.length;
        if (len === 1) {
            return arr;
        }
        const mid = Math.floor(len / 2);
        const left = arr.slice(0, mid);
        const right = arr.slice(mid, len);
        const orderLeft = rec(left);
        const orderRight = rec(right);
        console.log('orderLeft',orderLeft);
        console.log('orderRight',orderRight);
    }
   rec(this);
}

const arr = [5, 4, 3, 2, 1];
arr.mergeSort();

// arr [ 5, 4, 3, 2, 1 ]
// arr [ 5, 4 ]
// arr [ 5 ]
// arr [ 4 ]
// orderLeft [ 5 ]
// orderRight [ 4 ]
// arr [ 3, 2, 1 ]
// arr [ 3 ]
// arr [ 2, 1 ]
// arr [ 2 ]
// arr [ 1 ]
// orderLeft [ 2 ]
// orderRight [ 1 ]
// orderLeft [ 3 ]
// orderRight undefined
// orderLeft undefined
// orderRight undefined

// ==> 

//  [5, 4, 3, 2, 1]
//     /     \
//  [5,4]    [3,2,1]
//   /  \     /   \
// [5] [4]  [3]  [2,1]
// [5] [4]  [3]  [2] [1]

合

// 将之前拆分的数组进行合并：使用 while 循环判断两个数组的第一个元素的大小，哪个元素小就把该元素弹出放到新的数组中，继续判断...
Array.prototype.mergeSort = function () {
    const rec = (arr) => {
        const len = arr.length;
        if (len === 1) {
            return arr;
        }
        const mid = Math.floor(len / 2);
        const left = arr.slice(0, mid);
        const right = arr.slice(mid, len);
        const orderLeft = rec(left);
        const orderRight = rec(right);
        console.log('orderLeft',orderLeft);
        console.log('orderRight',orderRight);
        const res = [];
        while (orderLeft.length || orderRight.length) {
            if (orderLeft.length && orderRight.length) {
                res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
            } else if (orderLeft.length) {
                res.push(orderLeft.shift());
            } else if (orderRight.length) {
                res.push(orderRight.shift());
            }
        }
        return res;
    }
    const res = rec(this);
    res.forEach((it, i) => {
        this[i] = it;
    })
}

const arr = [5, 4, 3, 2, 1];
arr.mergeSort();
console.log(arr);

// orderLeft [ 5 ]
// orderRight [ 4 ]
// orderLeft [ 2 ]
// orderRight [ 1 ]
// orderLeft [ 3 ]
// orderRight [ 1, 2 ]
// orderLeft [ 4, 5 ]
// orderRight [ 1, 2, 3 ]
// [ 1, 2, 3, 4, 5 ]

题目

合并两个有序链表

  • 与归并排序中的合并两个有序数组很相似，将数组替换成链表就能解此题。

解体思路：

  1. 新建一个新链表，作为返回结果。
  2. 用指针遍历两个有序链表，并比较两个链表的当前节点，
  3. 较小者先接入新链表，并将指针后移一步。
  4. 链表遍历结束，返回新链表。

image.png

快速排序

思路：

  • 分区：从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面。
  • 递归：递归地对基准前后的子数组进行分区。

复杂度：

  • 递归的时间复杂度：O(logN)
  • 分区操作的时间复杂度：O(n)
  • 最终的时间复杂度：O(n*logN)
function sort(arr = []) {
    const len = arr.length;
    if (len <= 1) {
        return arr;
    }
    // 快排不一定要中间值，可以取任意值进行比较，这里取数组第一个元素进行比较
    // const midIdx = Math.floor(len / 2);
    const midVal = arr[0];
    let left = [];
    let right = [];
    for (let i = 1; i < len; i++) {
        const curVal = arr[i];
        if (curVal < midVal) {
            left.push(curVal);
        } else {
            right.push(curVal);
        }
    }
    return [...sort(left), midVal, ...sort(right)];
}

参考

排序算法动画网站

https://juejin.im/post/57dcd394a22b9d00610c5ec8
https://juejin.im/post/5e1182def265da5d691039ab
https://juejin.im/post/58c9d5fb1b69e6006b686bce