排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
冒泡排序 O(n2) O(n) O(n2) O(1) 稳定
快速排序 O(n log n) O(n log n) O(n2) O(log n) 不稳定
插入排序 O(n2) O(n) O(n) O(n) 稳定
希尔排序 O(n log n) O(n log2 n) O(n log2 n) O(1) 不稳定
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
桶排序
计数排序 O(n + k) O(n + k) O(n + k) O(n + k) 稳定
基数排序 O(n + k) O(n + k) O(n + k) O(n + k) 稳定
堆排序
归并排序 O(n log n) O(n log n) O(n log n) O(n) 稳定

冒泡排序

思想

  • 冒泡排序只会操作相邻的两个数据。
  • 每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。
  • 一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

特点

  • 优点：排序算法的基础，简单实用易于理解。

  • 缺点：比较次数多，效率较低。 ```javascript function bubbleSort(arr) { console.time(“冒泡排序耗时”);

    if (!Array.isArray(arr)) return;

    const { length = 0 } = arr; if (length <= 1) return;

    for (let i = 0; i < length - 1; i++) { for (let j = 0; j < length - i - 1; j++) {

    1. if (arr[j] > arr[j + 1]) {
    2.   [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    3. }

    } } console.timeEnd(“冒泡排序耗时”); return arr; }

function bubbleSortOptimize(arr) { console.time(“优化-冒泡排序耗时”);

if (!Array.isArray(arr)) return;

const { length } = arr; if (length <= 1) return;

for (let i = 0; i < length - 1; i++) { let changeState = false; for (let j = 0; j < length - i - 1; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; changeState = true; } }

  1. if (!changeState) break;

} console.timeEnd(“优化-冒泡排序耗时”); return arr; }

const array = Array.from(new Array(10), () => ~~(Math.random() * 100)); console.log(原始array: ${array}); const newArr = bubbleSort(array); console.log(bubbleSort排序之后newArr: ${newArr});

console.log(“——————————————“);

const array2 = Array.from(new Array(10), () => ~~(Math.random() * 100)); console.log(原始array: ${array2}); const newArr2 = bubbleSortOptimize(array2); console.log(bubbleSortOptimize排序之后newArr: ${newArr2});

  1. <a name="DLTry"></a>
  2. # 快速排序
  3. 思想
  5. - 先找到一个基准点（一般指数组的中部），然后数组被该基准点分为两部分，依次与该基准点数据比较，如果比它小，放左边；反之，放右边。
  6. - 左右分别用一个空数组去存储比较后的数据。
  7. - 最后递归执行上述操作，直到数组长度 <= 1;
  9. 特点：
  11. - 优点：快速，常用。
  12. - 缺点：需要另外声明两个数组，浪费了内存空间资源。
  13. ```javascript
  14. function quickSort(arr) {
  15.   if (!Array.isArray(arr)) return;
  17.   const { length } = arr;
  19.   if (length <= 1) return arr;
  21.   const pivotIndex = length >> 1;
  22.   const pivot = arr.splice(pivotIndex, 1)[0];
  23.   const left = [];
  24.   const right = [];
  26.   for (let i of Object.keys(arr)) {
  27.     arr[i] <= pivot ? left.push(arr[i]) : right.push(arr[i]);
  28.   }
  29.   return quickSort(left).concat(pivot, quickSort(right));
  30. }
  32. const array = Array.from(new Array(10), () => ~~(Math.random() * 100));
  33. console.log(`原始array: ${array}`);
  34. const newArr = quickSort(array);
  35. console.log(`quickSort排序之后newArr: ${newArr}`);

插入排序

思想：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

  1. function insertionSort(arr) {
  2.   console.time("插入排序耗时");
  3.   if (!Array.isArray(arr)) return;
  5.   const { length } = arr;
  7.   if (length <= 1) return arr;
  9.   for (let i = 1; i < length; i++) {
  10.     for (let j = i; j > 0; j--) {
  11.       if (arr[j] < arr[j - 1]) {
  12.         [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
  13.       }
  14.     }
  15.   }
  16.   console.timeEnd("插入排序耗时");
  17.   return arr;
  18. }
  20. const array = Array.from(new Array(10), () => ~~(Math.random() * 100));
  21. console.log(`原始array: ${array}`);
  22. const newArr = insertionSort(array);
  23. console.log(`insertionSort排序之后newArr: ${newArr}`);

希尔排序

hhttps://zh.wikipedia.org/wiki/希尔排序

注：gap >> 1 表示右移一位，等同于 gap 除以 2 再取整，即 gap >> 1 === Math.trunc(gap / 2)

思想

  • 希尔排序将序列分割成若干小序列（逻辑上分组），然后对每一个小序列进行插入排序，此时每一个小序列数据量小，插入排序的效率也提高了。 ```javascript function shellSort(arr) { console.time(“希尔排序耗时”);

    if (!Array.isArray(arr)) return;

    const { length } = arr; let temp, log, step = 1, gap = length;

    // (gap = Math.trunc(gap/2)) == (gap >>= 1) while (gap > 0 && (gap >>= 1)) { console.log(Gap is ${gap}); for (let i = gap; i < length; i++) {

    1. temp = arr[i];
    2. let j = i - gap;
    3. while (j >= 0 && arr[j] > temp) {
    4.   arr[j + gap] = arr[j];
    5.   j -= gap;
    6. }
    7. arr[j + gap] = temp;
    9. log = "";
    10. arr.forEach((v, i) => {
    11.   log += `${v}\t${(i + 1) % gap === 0 ? "\n" : ""}`;
    12. });
    13. console.log(`Step ${step++}: \n${log}`);

    } } console.timeEnd(“希尔排序耗时”); return arr; }

const array = Array.from(new Array(10), () => ~~(Math.random() * 100)); console.log(原始array: ${array}); const newArr = shellSort(array); console.log(shellSort排序之后newArr: ${newArr});

  1. <a name="Q45Bo"></a>
  2. # 选择排序
  3. 思想
  5. - 选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
  7. 特点
  9. - 优点：上手比较简单，比较符合人的正常思路逻辑。
  10. - 缺点：时间复杂度O(n^2)，运算速度很慢，当数组元素个数比较多时，时间增速惊人。
  11. ```javascript
  12. const selectionSort = (arr) => {
  13.   console.time("选择排序耗时");
  15.   if (!Array.isArray(arr)) return;
  17.   const { length } = arr;
  19.   for (let i = 0; i < length - 1; i++) {
  20.     let min = arr[i],
  21.       minIndex = i,
  22.       step = 0;
  23.     for (let j = i + 1; j < length; j++) {
  24.       step++;
  25.       if (min > arr[j]) {
  26.         min = arr[j];
  27.         minIndex = j;
  28.       }
  29.     }
  30.     console.log(
  31.       `Step${i + 1}: ${arr}, min: ${min}, minIndex: ${minIndex}, step: ${step}`
  32.     );
  34.     [arr[i], arr[minIndex]] = [min, arr[i]];
  35.   }
  37.   console.timeEnd("选择排序耗时");
  38.   return arr;
  39. };
  41. const array = Array.from(new Array(10), () => ~~(Math.random() * 100));
  42. console.log(`原始array: ${array}`);
  43. const newArr = selectionSort(array);
  44. console.log(`selectionSort排序之后newArr: ${newArr}`);

桶排序

计数排序

思想

  • 统计每个元素重复出现的次数
  • 从小到大按顺序填充数组即可

特点

  • 优点：计数排序是所有排序算法中最简单的，也是最符合直觉的算法。

  • 缺点：用在待排序数据范围不大的场景，若数据范围 k 比要排序的数据 n 大很多，浪费空间。 ```javascript function countingSort(arr) { console.time(“计数排序耗时”);

    if (!Array.isArray(arr)) return;

    const { length } = arr;

    if (length <= 1) return arr;

    let counts = [], result = []; let min = Math.min(…arr); for (let v of arr) { counts[v - min] = (counts[v - min] ?? 0) + 1; } for (let i = 0; i < counts.length; i++) { let count = counts[i]; while (count > 0) {

    1. result.push(i + min);
    2. count--;

    } }

    console.timeEnd(“计数排序耗时”); return result; }

const array = Array.from(new Array(10), () => ~~(Math.random() * 100)); console.log(原始array: ${array}); const newArr = countingSort(array); console.log(countingSort排序之后newArr: ${newArr});

console.log(“——————————————“);

// TODO: k远大于n，代码执行久,如下 const array1 = [1, 100000001, 9, 1000, 3000]; console.log(原始array: ${array1}); const newArr1 = countingSort(array1); console.log(countingSort排序之后newArr: ${newArr1}); // 原始array: 1,100000001,9,1000,3000 // 计数排序耗时: 4.344s // countingSort排序之后newArr: 1,9,1000,3000,100000001

  1. <a name="a8mPO"></a>
  2. # 基数排序
  3. 思想
  5. - 基数排序是基于数据位数的一种排序算法。
  6. - 位，是进位的位，比如十进制数的基数是10，就可以按照个十百千万等位来排序。
  7. ```javascript
  8. function radixSort(arr) {
  9.   console.time("基数排序耗时");
  11.   if (!Array.isArray(arr)) return;
  13.   let maxLength = 0;
  14.   for (let v of arr) {
  15.     const { length } = String(v);
  16.     if (length > maxLength) {
  17.       maxLength = length;
  18.     }
  19.   }
  20.   for (i = 0; i < maxLength; i++) {
  21.     arr = sort(arr, i);
  22.   }
  24.   function sort(arr, index) {
  25.     let buckets = [];
  26.     for (let i = 0; i < 10; i++) {
  27.       buckets.push([]);
  28.     }
  29.     for (let v of arr) {
  30.       let pad = String(v).padStart(maxLength, "0");
  31.       let num = pad[maxLength - 1 - index];
  32.       buckets[num].push(v);
  33.     }
  34.     let result = [];
  35.     for (let bucket of buckets) {
  36.       result.push(...bucket);
  37.     }
  38.     return result;
  39.   }
  40.   console.timeEnd("基数排序耗时");
  41.   return arr;
  42. }
  44. const array = Array.from(new Array(10), () => ~~(Math.random() * 100));
  45. console.log(`原始array: ${array}`);
  46. const newArr = radixSort(array);
  47. console.log(`radixSort排序之后newArr: ${newArr}`);

堆排序

归并排序

思想

  • “归并” 二字就是”递归”加”合并”。它是典型的分而治之算法。分治思想

  • 把数组一分为二，然后递归地排序好每部分，最后合并。 ```javascript function mergeSort(arr) { if (!Array.isArray(arr)) return;

    const { length } = arr;

    if (length < 2) return arr;

    const m = length >> 1, left = mergeSort(arr.slice(0, m)), right = mergeSort(arr.slice(m));

    let result = []; let i = 0, j = 0; while (i < left.length && j < right.length) { if (left[i] <= right[j]) {

    1. result.push(left[i++]);

    } else {

    1. result.push(right[j++]);

    } } if (i < left.length) { result.push(…left.slice(i)); } else { result.push(…right.slice(j)); } return result; }

const array = Array.from(new Array(10), () => ~~(Math.random() * 100)); console.log(原始array: ${array}); const newArr = mergeSort(array); console.log(mergeSort排序之后newArr: ${newArr});

```