排序算法

本文共--字 阅读约--分钟 | 浏览: -- Last Updated: 2022-02-19

基本排序

冒泡排序

冒泡排序属于交换排序，从第1位开始两两(i, i+1)比较，如果i > i+1 就换位，就会使得最大的值冒泡到最右侧，依次循环到第n-1位（不需要第n次循环，因为n个数进行排序，进行n-1次即可），具体解释如下：

例： 2, 1, 5, 4, 3

  • 第一轮循环：会将2与1做比较，2比1大，换位；然后换到第二个位置2再和5比较，小于则不用换；然后第三位5和4作比较，大于则换位；然后换到第四位的5和3继续比较，大于则换位；所以第一轮循环之后，结果为 1, 2, 4, 3, 5；

  • 第二轮循环：从第二位开始，2与4比，小于则不换；4与3比，大于则换位；结束循环；因为最后一位在第一轮循环中已经确定为最大，所以从第二轮循环开始每轮又比上一轮少比一次。

  • 继续循环到第四轮…

每一轮循环可以确定一个最“大”值。

具体实现如下：

function bubbleSort(arr) {
  // 循环次数为 arr.length - 1
  for (let i = 0; i < arr.length - 1; i++) {
    // 每轮之后少比一轮
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {                                                   
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]] 
      }
    }
    console.log(arr.join());
  }
}

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

如上输出，我们第2次的时候，就完成了排序，但是算法依然循环了4次，所以可以针对这一点，做一些优化。

function bubbleSort(arr) {
  let flag;
  for (let i = 0; i < arr.length - 1; i++) {
    flag = true;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {                                                   
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
        flag = false;
      }
    }
    // 因为冒泡排序是交换排序，每次都会比到“最后”
    // 如果比完了（内循环完成），一次交换都没有发生（flag没有被改变），说明之后的数据已经排好了
    if (flag) {
      break;
    }

    console.log(arr.join());
  }
}

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

选择排序

选择排序从数组的开头开始，将第一个元素和其他元素进行比较，检查完所有的元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续，这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。

例： 2, 1, 5, 4, 3

  • 第一轮循环：i = 0，min = i，即从第一位的2开始，和它的下一位1比，大于则设置min为1对应的下标(min = 1)，然后1依次与5，4，3相比，发现最小的还是1，就将1(index为1) 与当前循环的2 (index为0) 互换，一轮循环完成后，排序为 1, 2, 5, 4, 3，确定了第一小的值。

  • 第二轮循环：i = 1，min = i，即从第二位的2开始，和它的下一位5相比，小于则min不变依然为1，然后依次比下去发现最小的是2，则确定了数据中第二小的就是2，循环完成后，排序为 1, 2, 5, 4, 3。数据没有发生变换，但确定了第二小的值。

  • 第三轮循环：i = 2，min = i，即从第三位的5开始，和它之后的数据相比，最终发现最小的值是3，就将3(index为4)与当前循环的5(index为2)互换，排序为 1, 2, 3, 4, 5，确定了第三小的值。

  • 继续循环到第四轮….

每一轮循环可以确定一个最“小”值。

同样的，从第二轮循环开始每轮又比上一轮少比一次，但是和冒泡排序不一样的是，冒泡排序是确定了最大值，通过内循环语句中 j < arr.length - 1 - i实现；而选择排序，每一轮确定了最小值，所以内循环 j = i + 1 实现，每次只与“自己”之后的数据比。

具体实现如下：

function selectSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i;
    // 需要与“自己”之后的数据比完找到最小的，所以是 j < arr.length
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) {
        min = j;
      }
    }
    [arr[i], arr[min]] = [arr[min], arr[i]]
    console.log(arr.join());
  }
}

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

插入排序

也是双层循环，内循环对外循环中选中的元素及它前面的所有元素进行比较，如果外循环中选中的元素比内循环选中的元素小，那么数组元素就会向右移动，为外循环中选中的这个元素腾出位置。

例： 2, 1, 5, 4, 3

这个算法我们可以这样设想，5张卡牌标记了5个数字，但是都是反面朝上，我们不知道每张卡牌对应的数字是什么。我们首先翻开第一张，是一张2。

  • 第一次循环：翻开第二张，是一张1，与前面已经翻开的2进行比较，1小于2，2向右移动，2之前没有数字了，那么当前循环中1就是最小的，那么就1放在最前面。当前排序为 1, 2, *, *, *，上帝视角则为 1, 2, 5, 4, 3

  • 第二次循环：翻开第三张，是一张5，与前面翻开的2进行比较，发现是大于2的，那么5的位置在当前是合理的，无需换位，排序为 1, 2, 5, *, *，上帝视角则为 1, 2, 5, 4, 3，与上一轮一致。

  • 第三次循环：翻开第四张，是一张4，与前面翻开的5进行比较，4小于5，5向右移动，然后继续与前面2的比较，发现前面的2小于自己，自己又会比刚刚移位的5小，那么4就应该放在2和5之前，当前排序为 1, 2, 4, 5, *，上帝视角则为 1, 2, 4, 5, 3。

  • 第四次循环：翻开第5张，是一张3，与前面翻开的5进行比较，5继续右移；再与前面翻开的4比较，4也右移一格，然后继续向前查找，终于找到比它小的，那么就插在找到的 第一个小于等于自己的卡牌 后面即可。结束算法，排序为 1, 2, 3, 4, 5。

与前面的牌进行比较，是想找到自己合适的位置：

  • 设翻开卡牌是x
  • 如果x比其前一位的大，则当前卡牌x是无需移位的。
  • 如果x比前一位小，那么x的前一位就向右移动，继续向前比较，直到找到第一个小于等于x的卡牌，插入其后。
  • 一直找到头了，都没有比当x更小的了，那比它的大都右移了，给它腾出了位置，它就直接插到第一个即可。

具体实现如下：

const arr = [2, 1, 5, 4, 3]

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let outer = arr[i];
    for (var j = i; j > 0 && arr[j-1] > outer; j--) {
      arr[j] = arr[j-1] // 如果前一位大于当前outer，则前一位arr[j-1]向右移动
    }

    // 走到这，说明循环结束
    // 1. 要么往前找，找不到比outer大的值了，此时的j对应的就是找到的比outer小的第一个数据的下标
    // 此时，比如 j = 3， arr[2] <= outer
    // 那么 outer就应该排在下标3，因为下标2比它小，原来的下标3比它大，移动到了下标4的位置。
    // 即 arr[j] = outer;

    // 2. 要么 j = 0 了，比到头了，该换位的已经换位了
    // 此时，outer比此刻的arr[0]还要小，那么就应该赋值 arr[0] = outer;
    arr[j] = outer;
    console.log(arr.join());
  }
}

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

基本排序算法的计时比较

function random() {
  return Math.floor(Math.random() * 100 + 1)
}

function compareSort(dataLength) {
  const arr = [];
  for (let i = 0; i < dataLength; i++) {
    arr.push(random())
  }
  console.log(`${dataLength}个数据三种排序的耗时如下：`);

  const bArr = [...arr];
  console.time('bubbleSort 耗时')
  bubbleSort(bArr);
  console.timeEnd('bubbleSort 耗时')

  const sArr = [...arr];
  console.time('selectSort 耗时')
  selectSort(sArr);
  console.timeEnd('selectSort 耗时')

  const iArr = [...arr];
  console.time('insertionSort 耗时')
  insertionSort(iArr);
  console.timeEnd('insertionSort 耗时')

  console.log();
}

compareSort(10)
compareSort(100)
compareSort(1000)

// 10个数据三种排序的耗时如下：
// bubbleSort 耗时: 0.270ms
// selectSort 耗时: 0.119ms
// insertionSort 耗时: 0.087ms

// 100个数据三种排序的耗时如下：
// bubbleSort 耗时: 1.661ms
// selectSort 耗时: 0.242ms
// insertionSort 耗时: 0.127ms

// 1000个数据三种排序的耗时如下：
// bubbleSort 耗时: 12.389ms
// selectSort 耗时: 4.176ms
// insertionSort 耗时: 1.603ms

由此，可以知道插入排序是最快的，因为其交换次数少。而选择排序又优于冒泡排序，因为冒泡排序每个内循环都要进行比较交换，而选择排序呢，只在每一次内循环结束后进行一次交换。

高级排序算法

希尔排序

希尔排序的核心概念与插入排序不同，它会首先比较距离较远的元素，而非相邻的元素。和简单地比较相邻元素相比，使用这种方案可以使离正确位置很远的元素更快地回到合适的位置，当开始用这个算法遍历数据集时，所有元素之间的距离会不断减小，直到处理到数据集的末尾，这时算法比较的就是相邻元素。

希尔排序的工作原理是，通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列，不过对于大部分的实际应用场景，算法用到的间隔序列可以提前定义好。有一些业界公开的间隔序列，使用它们会得到不同的结果。这里我们使用 701, 301, 132, 57, 23, 10, 4, 1 这个由 Marcin Ciura 在 2001 年发表的论文中定义的。

比如，我们定义间隔序列为 [5, 3, 1]，也就是说算法在第一次处理数据集的时候，会检查所有间隔为5的元素（即第一轮循环每次翻开的卡牌是第5+i张）。下一轮循环会检查所有间隔为3的元素，最后一次则会对间隔为1的元素，也就是与插入排序一样了，对相邻元素执行插入排序。

在开始做最后一次处理的时候，大部分元素都将在正确的位置，算法就不必对很多元素进行交换，这也是希尔排序比插入排序更高效的地方。

具体实现如下:

function shellSort(arr) {
  const gaps = [5, 3, 1];

  for (let g = 0; g < gaps.length; g++) { // gap层
    const gap = gaps[g];
    for (let i = gap; i < arr.length; i++) { // outer层
      let outer = arr[i];
      // 这里为什么是 j >= gap 是因为翻开的卡牌要大于gap才能往前继续数gap个数进行比较。
      for (var j = i; j >= gap && arr[j-gap] > outer; j -= gap) { // inner层
        arr[j] = arr[j - gap]
      }
      arr[j] = outer;
    }
    console.log(`间隔为${gap}排序后：${arr.join()}`); // 打印间隔为5，3，1排序之后的结果。
  }
}

const arr = [6, 0, 2, 9, 3, 5, 8, 0, 5, 4];
shellSort(arr);
// 间隔为5排序后：5,0,0,5,3,6,8,2,9,4
// 间隔为3排序后：4,0,0,5,2,6,5,3,9,8
// 间隔为1排序后：0,0,2,3,4,5,5,6,8,9
console.log(arr); // [ 0, 0, 2, 3, 4, 5, 5, 6, 8, 9 ]

就是在插入排序的外层又包了一层循环用来控制间隔，其排序原理与插入排序类似：

  • inner层的第一轮循环：gap = 5，i = 5，outer = 5，往后数gap个数，来到下标0的位置，数字为6，6大于5，则6移动到5的位置。此时 j = 0呢，就使得 arr[0] = outer，结果为 5, 0, 2, 9, 3, 6, 8, 0, 5, 4

  • inner层的第二轮循环：gap = 5，i = 6， outer = 8，往后数gap个数，来到下标1的位置，数字为0，0小于8，则不换位。

  • inner层的第三轮循环：gap = 5，i = 7， outer = 0，往后数gap个数，来到下标2的位置，数字为2，2大于0，则2移动到0的位置； j -= gap 为2，是小于gap的，结束循环，就使得 arr[2] = outer，即结果为下标2的2 与下标为7的0 互换位置，结果为 5, 0, 0, 9, 3, 6, 8, 2, 5, 4。

  • inner层的第四轮循环：gap = 5，i = 8， outer = 5，往后数gap个数，来到下标3的位置，数字为9，9大于5，则9移动到5的位置；j -= gap 为3，是小于gap的，结束循环，就使得 arr[3] = outer，即结果为下标3的9 与下标为8的5 互换位置，结果为 5, 0, 0, 5, 3, 6, 8, 2, 9, 4。

  • inner层的第五轮循环：gap = 5，i = 9， outer = 4，往后数gap个数，来到下标4的位置，数字为3，3小于4，则不换位。

  • i = 10，超过数组的length，直接不循环，则outer层第一次循环（被外层的gaps控制会执行3次循环）执行完毕，得到排序结果 5, 0, 0, 5, 3, 6, 8, 2, 9, 4。

  • 开始执行gap=3的循环…

使用上面的排序比较方法，可以得到如下结果，希尔排序在数据集超过万的级别后，优势才得以充分体现，甚至在数据为1000时，插入排序算法更优。

function compareSort(dataLength) {
  const arr = [];
  for (let i = 0; i < dataLength; i++) {
    arr.push(random())
  }
  console.log(`${dataLength}个数据两种排序的耗时如下：`);

  const iArr = [...arr];
  console.time('insertionSort 耗时')
  insertionSort(iArr);
  console.timeEnd('insertionSort 耗时')

  const sArr = [...arr];
  console.time('shellSort 耗时')
  shellSort(sArr);
  console.timeEnd('shellSort 耗时')

  console.log();
}
// 10个数据两种排序的耗时如下：
// insertionSort 耗时: 0.213ms
// shellSort 耗时: 0.095ms

// 100个数据两种排序的耗时如下：
// insertionSort 耗时: 0.154ms
// shellSort 耗时: 0.053ms

// 1000个数据两种排序的耗时如下：
// insertionSort 耗时: 2.750ms
// shellSort 耗时: 3.382ms

// 10000个数据两种排序的耗时如下：
// insertionSort 耗时: 38.730ms
// shellSort 耗时: 9.214ms

// 100000个数据两种排序的耗时如下：
// insertionSort 耗时: 3502.158ms
// shellSort 耗时: 847.344ms

希尔排序-动态计算间隔

在 《算法（第四版）》（人民邮电出版社）的合著者 Robort Sedgewick 定义了一个希尔排序函数，这个函数中通过一个公式来对希尔排序的间隔序列进行动态计算。

var N = arr.length;
var h = 1;
while (h < N/3) {
  h = 3 * h + 1;
}

间隔值确定好后，与希尔排序唯一的区别，就是回到外循环之前的最后一条语句会计算一个新的间隔值，h = (h-1)/3即还原了。

比如length为20，第一次h就是13，第二次h就是4，第三次h就是1，不管是动态计算间隔序列还是直接定义间隔序列，最后一个间隔一定是1。

具体实现如下：

function shellSort1(arr) {
  var N = arr.length;
  var h = 1;
  while (h < N/3) {
    h = 3 * h + 1;
  }

  while (h >= 1) {
    for (var i = h; i < N; i++) {
      let outer = arr[i];
      for (var j = i; j >= h && arr[j-h] > outer; j-=h) {
        arr[j] = arr[j - h]
      }
      arr[j] = outer;
    }
    console.log(arr.join());
    h = (h-1)/3;
  }
}

const arr = [6, 0, 2, 9, 3, 5, 8, 0, 5, 4];
shellSort1(arr);
// 3,0,2,0,5,4,8,9,6,5
// 0,0,2,3,4,5,5,6,8,9
console.log(arr); // [ 0, 0, 2, 3, 4, 5, 5, 6, 8, 9 ]

// 此例中，length为10，则h第一次为4，第二次为1。

继续比较这两个希尔排序的耗时，测试结果如下：

// 1000个数据两种排序的耗时如下：
// shellSort 耗时: 4.973ms
// shellSort1 耗时: 2.120ms

// 10000个数据两种排序的耗时如下：
// shellSort 耗时: 10.489ms
// shellSort1 耗时: 2.970ms

// 100000个数据两种排序的耗时如下：
// shellSort 耗时: 861.157ms
// shellSort1 耗时: 10.127ms

明显，当数据越大时，动态计算间隔的希尔排序算法更优；而当我们采用之前提到过的 701, 301, 132, 57, 23, 10, 4, 1 这个由 Marcin Ciura定义的序列去排序 100000 条数据时，结果如下：

function shellSort(arr) {
  // new line
  const gaps = [701, 301, 132, 57, 23, 10, 4, 1];

  // ...
}

function compareSort(dataLength) {
  const arr = [];
  for (let i = 0; i < dataLength; i++) {
    arr.push(random())
  }
  console.log(`${dataLength}个数据两种排序的耗时如下：`);

  const sArr = [...arr];
  console.time('shellSort 耗时')
  shellSort(sArr);
  console.timeEnd('shellSort 耗时')

  const s1Arr = [...arr];
  console.time('shellSort1 耗时')
  shellSort1(s1Arr);
  console.timeEnd('shellSort1 耗时')

  console.log();
}

compareSort(100000)
// 100000个数据两种排序的耗时如下：
// shellSort 耗时: 18.472ms
// shellSort1 耗时: 14.935ms

动态计算间隔的希尔排序依然更快，但是差距被缩小了。

归并排序

参考: (图片及理论出处)

归并排序是利用归并的思想实现的排序方法，该方法采用经典的分治策略，将问题分成一些小的问题然后递归求解，而治的阶段将分的阶段得到的各答案修补在一起，即分而治之。

具体实现如下：

function mergeSort(arr) {
  let len = arr.length;
  if (len <= 1) {
    return arr;
  }

  // 分
  let mid = Math.floor(len / 2);
  let leftChild = mergeSort(arr.slice(0, mid));
  let rightChild = mergeSort(arr.slice(mid, arr.length));

  // 治 => 合并及排序数组
  function merge(left, right) {
    // 使用两个指针分别控制左子序列和右子序列
    let l = r = 0;
    let result = [];

    // 通过两个指针完成对子序列的遍历比较
    while (l < left.length && r < right.length) {
      if (left[l] < right[r]) {
        result.push(left[l]) // 小的先入队
        l++; // 对应指针往后移动
      } else {
        result.push(right[r])
        r++;
      }
    }

    // 处理当某一个指针走完，而另一个指针未走完的情况 即把剩下的那一个子序列直接连接起来即可
    // 比如此例中其中会有一组是 left是6,10 right是1,4,9
    // 上面的循环过程如下：result => [1] => [1, 4] => [1, 4, 6] => [1, 4, 6, 9]
    // l会变成2，是等于left.length的，循环结束，此时right还剩一个10
    // 剩下的永远都是比已入队的要大 所以直接concat即可
    if (l < left.length) {
      result = result.concat(left.slice(l, left.length));
    }

    if (r < right.length) {
      result = result.concat(right.slice(r, right.length));
    }
    return result;
  }

  return merge(leftChild, rightChild)
}

const arr = [6, 10, 1, 9, 4, 8, 2, 7, 3, 5, 11]
const newArr = mergeSort(arr);
console.log(newArr);

快速排序

快速排序是处理大数据最快的排序算法之一，也是采用一种分而治之的算法，但是与归并排序并不一样，这个算法的过程如下：

  • 选择一个基准元素，将列表分隔成两个子序列。将所有小于基准值的元素放在基准值的左子序列，所有大于基准值的元素放在右子序列。
  • 然后继续对左子序列、右子序列重复第一步，直到数组元素只有1个返回。
  • 将数组按照左子序列、基准值、右子序列的顺序连接并返回。

具体实现如下：

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  let left = []; // 左子序列
  let right = []; // 右子序列
  let pivot = arr[0]; // 基准值

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)]
}

const arr = [6, 10, 1, 9, 4, 8, 2, 7, 3, 5, 11]
console.log(quickSort(arr));

图示如下：

上面的快速排序是一种比较简单的实现，是以空间换时间，而针对于快速排序还有一种更优解，所有的排序都是通过操作交换原数组的元素实现。

function quickSort(arr, begin, end) {
  if(begin >= end) {
    return;
  }
  var l = begin;
  var r = end;
  var pivot = arr[begin];
  while(l < r) {
    
    // 从右向左找，找到第一个小于基准数的时候停住
    // 最终目的，将小于基准数的元素放到基准数的左边
    while(l < r && arr[r] >= pivot) {
      r--;
    }
    // 从左向右找，碰到第一个大于基准数的时候停住
    // 最终目的，将大于基准数的元素放到基准数的右边
    while(l < r && arr[l] <= pivot) {
      l++;
    }
    
    // 交换左右指针所停位置的数
    if (l < r) {
      [arr[l], arr[r]] = [arr[r], arr[l]];
    }
    
    // 如果l还是小于r，说明l和r没有碰到，循环继续
  }
  
  // 当循环结束之后
  // 交换基准数与『指针相遇位置』的数
  // 交换之后，基准值就来到了中间的位置 在基准值左边的就是小于基准值的数，在右边的就是大于基准值的数
  [arr[begin], arr[l]] = [arr[l], arr[begin]];
  
  // 递归处理左右数组
  quickSort(arr, begin, l - 1);
  quickSort(arr, l + 1, end);
}

const arr = [5, 2, 9, 3, 8, 4, 0, 1, 6, 7]
quickSort(arr, 0, arr.length - 1);
console.log('arr', arr);

图示如下：