衡量指标

执行效率

最好情况、最坏情况、平均情况时间复杂度
时间复杂度的系数、常数、低阶
比较次数和交换（或移动次数）

内存消耗

即空间复杂度，空间复杂度为 O(1) 的排序算法，被称为原地排序算法

稳定性

待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序是否保持不变。如果能保持不变，就是稳定的排序算法，否则就是不稳定的排序算法。 eg: 有一个 10w 数据的订单列表，订单有 2 个属性 time（下单时间）和 price（订单金额）。需求是按照金额从小到大排序，金额相同的按下单时间从早到晚排序。

冒泡排序

只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较。一次冒泡会至少移动一个元素，n 个数据的排序会重复 n 次。

时间复杂度：
- 最好情况时间复杂度：一开始就是有序的，只需执行一轮，复杂度为 O(n)
- 最坏情况时间复杂度：数据是倒序的，要进行 n 次冒泡排序，复杂度为 O(n^2)。
- 平均情况时间复杂度：
属于稳定排序算法，因为相邻的 2 个元素相同的话不会产生交换
属于原地排序算法，因为只用到了一个临时变量 tmp，空间复杂度为 O(1)

const bulleSort = (array: number[], num: number) => {
  if (num <= 1) return;
  for (let i = 0; i < num; i++) {
    // 提前退出冒泡循环的标志位
    let flag = false;
    for (let j = 0; j < num - i - 1; j++) {
      const tmp = array[j];
      array[j] = array[j + 1];
      array[j + 1] = tmp;
      flag = true;
    }
    if (!flag) break;
  }
};

插入排序

先切割已排序区间（一开始只有一个元素）和未排序区间。提取未排序区间中的元素，在已排序中找到合适的插入位置将其插入，并保证已排序区间的数据一直有序。

时间复杂度：
- 最好情况时间复杂度：一开始就是有序的，只需执行一轮，复杂度为 O(n)
- 最坏情况时间复杂度：数据是倒序的，要进行 n 次插入排序，复杂度为 O(n^2)。
- 平均情况时间复杂度：
属于稳定排序算法，值相同的元素，可以将后面出现的元素，插入到前面出现元素的后面，保持原有顺序不变。
属于原地排序算法，因为没有用到额外的临时空间，空间复杂度为 O(1)

const insertSort = (array: number[], num: number) => {
  if (num <= 1) return;
  for (let i = 0; i < num; i++) {
    const value = array[i];
    let j = i - 1;
    for (; j >= 0; j--) {
      if (array[j] > value) {
        array[j + 1] = array[j];
      }
      break;
    }
    array[j + 1] = value;
  }
};

选择排序

先切割已排序区间（一开始只有一个元素）和未排序区间，每次从未排序区找到最小（大）的元素，将其放到已排序的末尾

归并排序

先把数组从中间分成前后 2 部分，然后对前后 2 部分分别排序，再将排序好的 2 部分合在一起。归并借助的是分治思想，借助算法：递归的编程技巧实现

/** 
 * 递推公式：
 * merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
 * 终止条件：
 * p >= r 不用再继续分解

以我所主，为我所用

探索

算法：排序