前置知识

1.稳定排序

  • 稳定排序：如果 a 原本在 b 的前面，且 a = = b，排序之后 a 仍然在 b 的前面，则为稳定排序。

  • 非稳定排序：如果 a 原本在 b 的前面，且 a = = b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

    2.原地排序

  • 原地排序：指在排序过程中不需要多余的空间，只利用原来待排数据的存储空间去比较和交换的数据排序

  • 非原地排序：指需要利用额外的数组来辅助排序 | | 时间复杂度 | 空间复杂度 | 稳定排序 | 原地排序 | | —- | —- | —- | —- | —- | | 冒泡排序 | O(n2) | O(1) | 是 | 是 | | 选择排序 | O(n2) | O(1) | 否 | 是 | | 插入排序 | O(n2) | O(1) | 是 | 是 | | 希尔排序 | O(nlogn) | O(1) | 是 | 是 | | 归并排序 | O(nlogn) | O(n) | 是 | 否 | | 快速排序 | O(nlogn) | O(logn) | 否 | 是 | | 堆排序 | O(nlogn) | O(1) | 否 | 是 | | 计数排序 | O(n+k) | O(k) | 是 | 否 | | 桶排序 | O(n+k) | O(n+k) | 是 | 否 | | 基数排序 | O(n*k) | O(n+k) | 是 | 否 |

注：在桶排序和基数排序中，k为桶的个数

冒泡排序

什么是冒泡排序？
顾名思义，数组元素就像水中的泡泡一样，越往上越大，越往下越小。也就是说，数组元素值越小在数组中的位置越前，反之则越靠后，由此可以使整个数组元素得到排序。
具体实现思路：

  1. 从第一个元素开始，让其与右边相邻元素比较，如果左边元素大于右边元素则交换并且左右下标同时向右移动，再次比较。
  2. 若左边元素小于右边元素，则右边元素向右移动。如此一次遍历，最右边元素为数组中最大

  3. 分别对剩下的元素依次进行第一步和第二步即可。

    1. const bubbleSort = function(arr) {
    2.  const len = arr.length;
    3. if (len < 2) return arr;
    4.  for (let i = len-1; i >= 0; i--) {
    5.      let flag = false;
    6.      for (let j = 0; j < i; j++) {
    7.          if (arr[j] > arr[j+1]) {
    8.              flag = true;
    9.      // 交换
    10.              [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
    11.          }
    12.      }
    13.  // 优化：如果在一次遍历中，没有发生任何交换，则说明数组已有序，结束循环
    14.      if (!flag) break 
    15.  }
    16.  return arr;
    17. }

    选择排序

    什么是选择排序？
    所谓选择排序就是在无序序列的每次循环中选择一个最小数字放在前面的有序序列中。
    具体思路：

  4. 假设第一个元素为有序集合

  5. 然后不断遍历数组中元素，找到元素最小值后将其与第一个元素交换
  6. 后续每次遍历时将无序集合的第一个元素与寻找到的最小值元素交换

  7. 当无序集合长度为 0 时，结束循环

    1. const selectSort = function(arr) {
    2.  const len = arr.length;
    3.  if (len < 2) return arr;
    4.  for (let i = 0; i < len-1; i++) {
    5.      // 记录无序集合中最小值的位置
    6.      let minIndex = i
    7.      for (let j = i+1; j < len; j++) {
    8.          // 如果遇到更小值，更新位置
    9.          if (arr[j] < arr[minIndex]) {
    10.              minIndex = j
    11.          }
    12.      }
    13.      // 交换位置
    14.      [ arr[i], arr[minIndex] ] = [arr[minIndex], arr[i]]
    15.  }
    16.  return arr
    17. }

    插入排序

    什么是插入排序？
    插入排序有点类似于选择排序的优化版，它不像选择排序那样一次次地选择无序集合中的最小元素，然后将其放置在有序集合之后；而是将遍历到的元素一个个的插入到有序集合中恰当的位置。
    具体思路：

  8. 假设第一个元素为有序集合

  9. 将无序集合中的第一个元素设为inserted，然后从后往前地与有序集合的元素比较，比inserted大的元素往后移动，然后将其插入。

  10. inserted插入后，待插入元素往后移动一位后，继续执行第二步即可。

    1. const insertSort = function(arr) {
    2.  const len = arr.length;
    3.  if (len < 2) return arr;
    4.  for (let i = 1; i < len; i++) {
    5.      let inserted = arr[i];
    6.      let j = i-1;
    7.      for (j; j >= 0 && arr[j] > inserted; j--) {
    8.          arr[j+1] = arr[j];
    9.      }
    10.      arr[j+1] = inserted;
    11.  }
    12.  return arr
    13. }

    希尔排序

    什么是希尔排序？
    希尔排序其实就是将数组进行逻辑上的分组，然后对每一个分组进行插入排序。在插入排序完成后，减少数组分割的距离，如此循环直至分割距离为1后结束。
    希尔排序一般是用于数据量较大的情况，当数据量较小可以选择采用插入排序。
    具体思路：

  11. 首先设置增量gap为length/2，将数组分为length/2个小组

  12. 然后分别对每个小组进行插入排序
  13. 每个小组插入排序完毕后，将增量gap/2，再分组进行插入排序
  14. 当增量小于1时，结束循环 ```javascript const shellSort = function(arr) { const len = arr.length; if (len < 2) return arr; for (let gap = Math.floor(len/2); gap >= 1; gap = Math.floor(gap/2)) {
    1.  for (let i = gap; i < len; i++) {
    // arr[i]为无序集合中的第一个元素，即待插入元素
    1.      insertSort(arr, gap, i);
    2.  }
    } return arr }

const insertSort = function(arr, gap, i) { let inserted = arr[i]; let j = i - gap; // 此时 arr[j] 为有序集合中的最后一个元素 for (j; j >= 0 && arr[j] > inserted; j -= gap) { // 有序集合中大于inserted的元素，后退gap个位置 arr[j+gap] = arr[j] } arr[j+gap] = inserted; }

  1. <a name="oQMMV"></a>
  2. ## 归并排序
  3. 什么是归并排序？<br />所谓归并排序，就是利用分治法，将数组从中点开始分割，然后不断递归分割直到子数组长度小于2时，开始合并子数组。<br />具体思路：
  5. 1. 把长度为n的输入序列分成两个长度为n/2的子序列；
  6. 2. 对这两个子序列分别采用归并排序；
  7. 3. 将两个排序好的子序列合并成一个最终的排序序列。
  8. ```javascript
  9. const mergeSort = function(arr) {
  10.     const len = arr.length;
  11.     if (len < 2) return arr;
  12.     let mid = Math.floor(len / 2);
  13.     const leftArr = arr.slice(0, mid);
  14.     const rightArr = arr.slice(mid);
  15.     return merge(mergeSort(leftArr), mergeSort(rightArr));
  16. }
  18. const merge = function(leftArr, rightArr) {
  19.     const res = [];
  20.     // 当左右数组有一个为空，直接加入另一个有序数组剩余元素
  21.     while(leftArr.length && rightArr.length) {
  22.         if (leftArr[0] > rightArr[0]) {
  23.             res.push(rightArr.shift());
  24.         } else {
  25.             res.push(leftArr.shift());
  26.         }
  27.     }
  28.     while (leftArr.length) {
  29.         res.push(leftArr.shift());
  30.     }
  31.     while (rightArr.length) {
  32.         res.push(rightArr.shift())
  33.     }
  34.     return res
  35. }

快速排序

什么是快速排序？
快速排序就是通过选择一个主元privot作为基准，将大于该主元的元素放在元素右侧，小于该主元的元素放在左侧，由此该主元为有序的。接下来对该主元的左右两侧数组进行同样的操作即可。
具体思路：

  1. 选择第一个元素为基准
  2. 将比基准小的数交换到前面，比基准大的数交换到后面
  3. 对左右区间递归执行第二步操作，直到区间只有一个数

  • 递归版本

    1. const quickSort = function(arr) {
    2.   const len = arr.length;
    3.   if (len < 2) return arr;
    4.   let privot = arr[0]
    5.   const leftArr = [], rightArr = []
    6.   for (let i = 1; i < len; i++) {
    7.       if (privot > arr[i]) {
    8.           leftArr.push(arr[i]);
    9.       } else {
    10.           rightArr.push(arr[i]);
    11.       }
    12.   }
    13.   return quickSort(leftArr).concat([privot], quickSort(rightArr))
    14. }

  • 双指针版本 — 优化

    • 利用额外两个数组户会增加空间复杂度，可以通过双指针解决。
      1. function sort(arr,begin,end){
      2. if(begin < end){
      3.    let i = begin;
      4.    let j = end;
      5.    let privot = arr[begin];
      6.    while(i < j){
      7.        while(arr[j] > privot && i < j){
      8.            j --;
      9.        }
      10.        arr[i] = arr[j];
      11.        while(arr[i] < privot && i < j){
      12.            i ++;
      13.        }
      14.        arr[j] = arr[i];
      15.    }
      16.    arr[i] = privot;
      17.    sort(arr,begin,i-1);
      18.    sort(arr,i+1,end);
      19. }else{
      20.    return;
      21. }
      22. }

      堆排序

      这里有一个讲得比较好的视频： https://www.bilibili.com/video/BV1vt4y1y7wR?from=search&seid=3993837508839965022

在将堆排序前，我们必须清楚，什么是堆？
堆具有两个特点：

  • 是一个完全二叉树
  • 所有父节点的值的都要大于（或小于）子节点的值

了解了堆，接下来讲讲堆排序。
堆排序可以说是一种利用堆的概念来排序的选择排序，分为两种方法：

  • 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列。
  • 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。

具体思路：

  1. 将待排序数组构造成一个大顶堆
  2. 此时，整个数组的最大值就是堆顶的根节点
  3. 将其与末尾元素进行交换，此时末尾就为最大值
  4. 然后将剩余 n - 1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。
  5. 重复执行第4步，随着元素个数的减少，最后就会得到一个有序序列。 ```javascript / 将最大的元素调整到堆顶/ function AdjustHeap(arr, pos, len){ var swap = arr[pos]; //保存当前节点 var child = pos * 2 + 1; //定位到当前节点的左边的子节点 while(child < len){ //递归遍历所有的子节点
    1.  //判断当前节点是否有右节点，若右节点较大，就采用右节点和当前节点进行比较
    2.  if(child + 1 < len && arr[child] < arr[child + 1]){
    3.      child += 1;
    4.  }
    5.  //比较当前节点和最大的子节点，小于就交换，交换后将当前节点定位到子节点上
    6.  if(arr[pos] < arr[child]){
    7.      arr[pos] = arr[child];
    8.      pos = child;
    9.      child = pos * 2 + 1;
    10.  }
    11.  else{
    12.      break;
    13.  }
    14.  arr[pos] = swap;
    } }

/* 构建堆：

  • 满足：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子结点的关键字。
  • 实现：从最后一个拥有子节点的节点开始，将该节点和其他节点进行比较，将最大的数交换给该节点，
  • 交换后再依次向前节点进行相同的交换处理，直到构建出大顶堆。 */ function BuildHeap(arr){ for(var i=arr.length/2; i>=0; i—){ //构建打顶堆 AdjustHeap(arr, i, arr.length); } }

/堆排序算法/ function HeapSort(arr){ BuildHeap(arr); //构建堆 for(var i=arr.length-1; i>0; i—){ //从数组的尾部进行调整 var swap = arr[i]; //堆顶永远是最大的元素,将堆顶和尾部元素交换，最大元素就保存在尾部，并且不参与后面的调整 arr[i] = arr[0]; arr[0] = swap; AdjustHeap(arr, 0, i); //将最大的元素进行调整，将最大的元素调整到堆顶 } }

  1. <a name="v4D39"></a>
  2. ## 计数排序
  3. 什么是计数排序？<br />所谓计数排序，就是把数组**元素**作为数组的**下标**，然后用一个临时数组统计该元素出现的次数。最后把临时数组统计的数据汇总起来，此时的数据是有序的。<br />具体思路：
  5. 1. 寻找数组中的最大值和最小值，确定临时数组长度
  6. 2. 遍历目标数组，统计数组元素出现次数
  7. 3. 把统计好的数据汇总到原数组
  8. ```javascript
  9. const countSort = function(arr) {
  10.     const len = arr.length;
  11.     if (len < 2) return arr;
  13.     // 寻找最大值与最小值
  14.     let max = -Infinity, min = Infinity;
  15.     for (let i = 0; i < len; i++) {
  16.         max = Math.max(max, arr[i]);
  17.         min = Math.min(min, arr[i]);
  18.     }
  20.     const temp = new Array(max - min + 1).fill(0);
  21.     // 统计数组元素数量
  22.     for (let x of arr) {
  23.         ++temp[x]
  24.     }
  26.     let k = 0;
  27.     // 将统计数据还原回原数组
  28.     for (let i = min; i <= max; i++) {
  29.         for (let j = temp[i]; j > 0; j--) {
  30.             arr[k++] = i;
  31.         }
  32.     }
  33.     return arr;
  34. }

桶排序

什么是桶排序？
所谓桶排序，就是将数组的最大值与最小值之间的元素进行瓜分，例如分成5个区间，则对应5个桶。将元素放入相应桶中，然后对桶中元素进行排序后合并。
具体思路：

  • 确定最大值和最小值，计算桶个数
  • 构造桶，将数组元素存入对应桶
  • 对桶内元素进行排序

  • 将所有桶进行合并

    1. const bucketSort = function(arr) {
    2.   const len = arr.length;
    3.   if (len < 2) return arr;
    5.   // 确定最大值、最小值和桶个数
    6.   let max = Math.max(...arr);
    7.   let min = Math.min(...arr);
    8.   let bucketNum = parseInt((max - min) / len) + 1;
    10.   // 构造桶
    11.   const bucketArr = new Array(bucketNum).fill().map(() => new Array());
    13.   // 将数组元素存入对应的桶中
    14.   for (let item of arr) {
    15.       const idx = parseInt((item - min) / len);
    16.       bucketArr[idx].push(item);
    17.   }
    19.   // 对每个桶进行排序
    20.   for (let item of bucketArr) {
    21.       item.sort();
    22.   }
    24.   // 整合所有桶
    25.   let k = 0;
    26.   for (let bucket of bucketArr) {
    27.       for (let item of bucket) {
    28.           arr[k++] = item;
    29.       }
    30.   }
    31.   return arr
    32. }

    基数排序

    什么是基数排序？
    所谓基数排序，其实就是一种基数“桶”的排序。
    先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小……
    当排序完毕后，就是有序的数组了。只不过在排序过程中，对于某位数是采用“桶”的方式来进行排序而已。
    具体思路：

  1. 计算出最大元素的位数
  2. 构建数组，存入十个桶
  3. 然后按照个位数到最大位数开始遍历

  4. 每遍历一次，先将元素按某位数入桶，然后再按桶顺序输出，桶元素的同时删除桶内元素 ```javascript const radixSort = function(arr) { let length = arr.length; if (length < 2) return arr;

    // 计算最大值的位数 let maxDigit = String(parseInt(Math.max(…arr))).length;

    let mod = 10, dev = 1;

    // 构建数组，存入十个桶 let counter = new Array(10).fill().map(() => new Array());

    // 将个位数遍历到最大位数 for (let i = 0; i < maxDigit; i++, dev = 10, mod = 10) {

    1.  // 元素入桶
    2.  for(let item of arr) {
    3.      // 计算元素的某位数
    4.      let idx = parseInt((item % mod) / dev);
    5.      counter[idx].push(item);
    6.  }
    8.  // 按顺序输出桶
    9.  let pos = 0;
    10.  for(let item of counter) {
    11.      let value = null;
    12.      if(item!=null) {
    13.          // 输出桶中元素
    14.          while ((value = item.shift()) != null) {
    15.              arr[pos++] = value;
    16.          }
    17.      }
    18.  }

    } return arr; }

```