# 排序

# 复杂度

名称 最优复杂度 平均复杂度 最坏复杂度 空间复杂度 稳定 备注
冒泡排序 n n^2 n^2 1 Yes
插入排序 n n^2 n^2 1 Yes
选择排序 n^2 n^2 n^2 1 No
堆排序 n log(n) n log(n) n log(n) 1 No
归并排序 n log(n) n log(n) n log(n) n Yes
快速排序 n log(n) n log(n) n^2 log(n) No 在 in-place 版本下,内存复杂度通常是 O(log(n))
希尔排序 n log(n) 取决于差距序列 n (log(n))^2 1 No
计数排序 n + r n + r n + r n + r Yes r - 数组里最大的数
基数排序 n * k n * k n * k n + k ? O(n) ? Yes k - 最长 key 的升序

|

# 稳定

  • 冒泡排序(Bubble Sort) — O(n²)
  • 插入排序(Insertion Sort)— O(n²)
  • 桶排序(Bucket Sort)— O(n); 需要 O(k) 额外空间
  • 计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间
  • 合并排序(Merge Sort)— O(nlogn); 需要 O(n) 额外空间
  • 二叉排序树排序 (Binary tree sort) — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
  • 基数排序(Radix sort)— O(n·k); 需要 O(n) 额外空间

# 不稳定

  • 选择排序(Selection Sort)— O(n²)
  • 希尔排序(Shell Sort)— O(nlogn)
  • 堆排序(Heapsort)— O(nlogn)
  • 快速排序(Quicksort)— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序

# O(n^2)

  • 插入排序
  • 选择排序
  • 希尔排序
  • 冒泡排序

# O(nlogn)

  • 快排
  • 归并排序
  • 堆排序

# O(n)

  • 桶排序
  • 计数排序
  • 基数排序

# 详细

# 1. 冒泡排序(稳定)

原地排序、稳定排序。每次两两比较,大的放到后面。每一次遍历都会将最后一位“就位”。

  • 最好 O(n)
  • 最坏 O(n^2)
  • 平均 O(n^2)
function sort(arr = []) {
  const len = arr.length;
  // 外层,需要遍历的次数
  for (let i = 0; i < len - 1; i++) {
    // 内层,每次比较
    for (let j = i + 1; j < len; j++) {
      if (arr[i] > arr[j]) {
        // 大的放到后面
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
  return arr;
}

# 2. 快速排序(不稳定)

原理:分治 + 递归

随机选取一个数组中的值作为基准值,从左至右取值与基准值对比大小。比基准值小的放数组左边,大的放右边,对比完成后将基准值和第一个比基准值大的值交换位置。然后将数组以基准值的位置分为两部分,继续递归以上操作。

  • 最好 O(nlogn)
  • 最坏 O(n^2)
  • 平均 O(nlogn)
/**
 * 将数组 arr 分为两部分,前一部分整体小于后一部分
 */
function partition(arr, left, right) {
  // 交换数组最左元素与数组的中间元素
  let midIndex = ((left + right) / 2) >> 0;
  swap(arr, left, midIndex);
  // 基准元素
  const flagItem = arr[left];
  let i = left + 1,
    j = right;
  while (true) {
    while (i <= right && arr[i] < flagItem) {
      i++;
    }
    while (j >= left && arr[j] > flagItem) {
      j--;
    }
    if (i > j) {
      break;
    } else {
      swap(arr, i, j);
      i++;
      j--;
    }
  }
  swap(arr, left, j);
  return j;
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) {
    return;
  }
  const mid = partition(arr, left, right);
  quickSort(arr, left, mid - 1);
  quickSort(arr, mid + 1, right);
}

# 三向快速排序

类似快速排序,但是分为了左中右三个部分,中间部分为等于当前值的所有值。适用于有大量重复元素的排序。

const arr = [];
const str = 'SORTEXAMPLE';

for (let char of str) {
  arr.push(char);
}

function sort(arr, lo, hi) {
  if (hi <= lo) return;
  let lt = lo,
    i = lo + 1,
    gt = hi;
  let v = arr[lo];
  while (i <= gt) {
    if (arr[i] < v) swap(arr, lt++, i++);
    else if (arr[i] > v) swap(arr, i, gt--);
    else i++;
    console.log(arr);
  }
  sort(arr, lo, lt - 1);
  sort(arr, gt + 1, hi);
}

function swap(arr, a, b) {
  let x = arr[a];
  arr[a] = arr[b];
  arr[b] = x;
}

sort(arr, 0, arr.length - 1);

/**
 * 三向切分的快速排序指的是,将数组分为小于、等于和大于当前切分值的区域。
 * 切分点从开头字母开始
 * 擅长于有大量重复元素的情况
 */

# 3. 选择排序(不稳定)

选择排序,从头至尾扫描序列,找出最小的一个元素,和第一个元素交换,接着从剩下的元素中继续这种选择和交换方式,最终得到一个有序序列。

原地排序;不稳定排序

复杂度:

  • 最好 O(n^2)
  • 最坏 O(n^2)
  • 平均 O(n^2)
function sort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    let min = i;
    // 找到第 n 个最小值。 在 arr[i + 1, arr.length - 1] 中找最小值索引, i+1 代表有序的下一个数,我们默认第一个元素是最小的
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[min]) min = j;
    }
    // 每次循环, a[i] 位都将是未选择出的数据中的最小值
    if (min !== i) {
      [arr[i], arr[min]] = [arr[min], arr[i]];
    }
  }
  return arr;
}

# 4. 插入排序 (稳定)

插入排序的原理如下: 当前元素保存一个副本,依次向前遍历前面的元素是否比自己大,如果比自己大就直接把前一个元素赋值到当前元素的位置,当前某位置的元素不再比当前元素大的时候,将当前元素的值赋值到这个位置。

插入排序也是一个简单的排序算法,它的思想是,每次只处理一个元素,从后往前查找,找到该元素合适的插入位置,最好的情况下,即正序有序(从小到大),这样只需要比较 n 次,不需要移动。因此时间复杂度为 O(n) ,最坏的情况下,即逆序有序,这样每一个元素就需要比较 n 次,共有 n 个元素,因此实际复杂度为 O(n²) 。

插入排序:选中某个值,将这个值移动到 a[i - 1] < a[i] < a[i + 1] 位置。

复杂度:

  • 最好 O(n)
  • 最坏 O(n^2)
  • 平均 O(n^2)
// 插入排序
function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i],
      j;
    for (j = i; j > 0 && arr[j - 1] > temp; j--) {
      arr[j] = arr[j - 1];
    }
    arr[j] = temp;
  }
  return arr;
}

# 5. 希尔排序 (缩小增量排序, 不稳定)

希尔排序:类似插入排序,但是对调的间隔扩大(插入排序是相邻元素对调位置的)。

按步长进行分组,组内直接插入,缩小增量再次进行此步骤,增量为 1 时相当于一次直接插入。

复杂度:最好 O(n) - 最坏 O(n^s 1<s<2) - 平均 O(n^1.3)

function sort(arr) {
  const len = arr.length;
  let h = 1;
  while (h < parseInt(len / 3)) {
    h = 3 * h + 1;
  }
  while (h >= 1) {
    for (let i = h; i < len; i++) {
      for (let j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
        swap(arr, j, j - h);
        console.log(arr);
      }
    }
    h = parseInt(h / 3);
  }
  return arr;
}
// 希尔排序
// 从 start 开始,间隔为 gap 数组进行插入排序
function insertSort(a, start, gap) {
  let temp;
  for (let i = start; i < length; i++) {
    for (let j = i + gap; j < length; j += gap) {
      if (a[j] < a[i]) {
        temp = a[j];
        a[j] = a[i];
        a[i] = temp;
      } else {
        break;
      }
    }
  }
  return a;
}

function hillSort(a) {
  for (let gap = parseInt(a.length / 2); gap >= 1; gap = parseInt(gap / 2)) {
    insertSort(a, 0, gap);
  }
  return a;
}

# 6. 归并排序(稳定)

原理:两个有序序列的合并,方法:分治 + 递归

复杂度:最好 O(nlogn) - 最坏 O(nlogn) - 平均 O(nlogn)

归并排序:通过去中间值分割数组,然后再对子数组分割,分割到最小单位进行比较,然后逐个合并。还有一种(bottom to top)的方法是先将数组切分为若干段,然后进行合并排序。核心思想就是分而治之

// 归并排序。分治思想,从数组中间开始将数组分成两个部分,然后分别对两个部分进行排序
// 效率为O(n log n)
const b = [3, 4, 6, 1, 3, 6, 32, 45, 21, 12],
  length = b.length;

const mergeSort = arr => {
  const length = arr.length;
  if (length < 2) return arr;

  const midIndex = parseInt(length / 2);
  const left = arr.slice(0, midIndex),
    right = arr.slice(midIndex, length);

  return [...mergeSort(left), ...mergeSort(right)];
};

# 7. 桶排序

// 桶排序. 值都是大于 0 的, 并且差不多都是均匀分布
// 桶排序的时间复杂度为 O(m+n)
function bucketSort(a) {
  // 找到最大和最小值
  let min = (max = a[0]);

  // O(n)
  for (let i = 1; i < a.length; i++) {
    if (min > a[i]) {
      min = a[i];
    }
    if (max < a[i]) {
      max = a[i];
    }
  }

  let bucket = new Array(max + 1).fill(0);

  for (let i = 0; i < a.length; i++) {
    bucket[a[i]]++;
  }

  let result = [];
  for (let i = 0; i < bucket.length; i++) {
    if (typeof bucket[i] === 'number' && bucket[i] !== 0) {
      result = [...result, ...new Array(bucket[i]).fill(i)];
    }
  }

  return result;
}

# 8. 基数排序(稳定)

原理:分配加收集

复杂度: O(d(n+r)) r 为基数 d 为位数 空间复杂度 O(n+r)

// 基数排序
const b = [3, 4, 6, 1, 3, 6, 32, 45, 21, 12],
  length = b.length;

function insertSort(a) {
  for (let i = 0; i < length - 1; i++) {
    for (let j = i + 1; j < length; j++) {
      if (a[i] > a[j]) {
        const temp = a[i];
        a[i] = a[j];
        a[j] = temp;
      }
      console.log(a);
    }
  }
  return a;
}

# 9. 计数排序

export default function CountingSort(elements) {
  let z = 0;
  let max = elements[0];
  let min = elements[0];
  for (let i = 1; i < elements.length; i++) {
    max = Math.max(max, elements[i]);
    min = Math.min(min, elements[i]);
  }
  const range = max - min;

  const finalArr = new Array(elements.length).fill(0);
  // Below is where algorithm may be inefficient (when range is too large)
  const countArr = new Array(range + 1 || 0).fill(0);

  for (let i = 0; i < elements.length; i++) {
    countArr[elements[i] - min]++;
  }

  for (let i = 0; i <= range; i++) {
    while (countArr[i]-- > 0) {
      finalArr[z++] = i + min;
    }
  }

  return finalArr;
}

# 10. 堆排序

堆排序利用了二叉堆的特性来做,二叉堆通常用数组表示,并且二叉堆是一颗完全二叉树(所有叶节点(最底层的节点)都是从左往右顺序排序,并且其他层的节点都是满的)。二叉堆又分为大根堆与小根堆。

  • 大根堆是某个节点的所有子节点的值都比他小
  • 小根堆是某个节点的所有子节点的值都比他大

堆排序的原理就是组成一个大根堆或者小根堆。以小根堆为例,某个节点的左边子节点索引是 i * 2 + 1,右边是 i * 2 + 2,父节点是 (i - 1) /2

  1. 首先遍历数组,判断该节点的父节点是否比他小,如果小就交换位置并继续判断,直到他的父节点比他大
  2. 重新以上操作 1,直到数组首位是最大值
  3. 然后将首位和末尾交换位置并将数组长度减一,表示数组末尾已是最大值,不需要再比较大小
  4. 对比左右节点哪个大,然后记住大的节点的索引并且和父节点对比大小,如果子节点大就交换位置
  5. 重复以上操作 3 - 4 直到整个数组都是大根堆。

原理:利用堆的特性。堆排序的思想就是堆的根肯定是最大的。

  1. 把最大的与最后一个元素交换
  2. 除最后一个元素外, 对根节点进行一次堆重组(heapify)
  3. 重复 1 和 2

复杂度:平均 - 最好 - 最坏 都是 O(nlogn)

function heapSort(tree, n) {
  // 先把一个数组组成一个堆
  buildHeap(tree, n);
  // 从最后一个节点开始
  for (let i = n - 1; i >= 0; i--) {
    swap(tree, i, 0);
    // 1.把最大的与最后一个元素交换
    heapify(tree, i, 0);
  }
}

// 根据数组创建一个堆
function buildHeap(tree, n) {
  // n = tree.length
  // last_node = tree.length - 1 也就是下标
  let last_node = n - 1;
  // 节点 i 的父节点的索引 i = (i - 1) / 2
  let parent = (last_node - 1) / 2;
  // 从最后一个父节点进行堆重组
  for (let i = parent; i >= 0; i--) {
    heapify(tree, n, i);
  }
}

// 交换两个元素的值
function swap(tree, max, i) {
  let temp = tree[i];
  tree[i] = tree[max];
  tree[max] = temp;
}

// 对第 i 个节点进行堆重组,n 为数组 tree 元素的个数
function heapify(tree, n, i) {
  // 递归出口
  if (i >= n) {
    return;
  }
  // 左孩子节点索引
  let c1 = 2 * i + 1;
  // 右孩子节点索引
  let c2 = 2 * i + 2;
  // 最大节点索引。 也就是根节点
  let max = i;
  if (c1 < n && tree[c1] > tree[max]) {
    max = c1;
  }
  if (c2 < n && tree[c2] > tree[max]) {
    max = c2;
  }
  // 说明不是 大根堆(每个节点的值都大于左右孩子节点),需要对其子树进行一次堆重组
  if (max != i) {
    // 交换 i 与 max 对应的值
    swap(tree, max, i);
    // 继续对子树进行堆重组
    heapify(tree, n, max);
  }
}

堆排序:利用优先队列可以方便查找最大值的特点,逐个求出最大值,从右到左、从大到小排序。

# 堆排序实战题

在 100000 个浮点数中找出最大的 1000 个数,时间复杂度最优 (用 堆排序 O(nlogn))

# 二分搜索树

堆排序 应用:用尺寸为 n 的最小堆(最大堆)来筛选大数据集里面最大(小)的 n 个数 流程:

  1. 先使用数据集里面的前 n 条数据来构造最小堆
  2. 遍历数据集,将每个数据与堆顶元素比较,若小于堆顶则抛弃,否则替换掉堆顶
  3. 调整替换后的堆,继续 2
  4. 用有序数组+2 分查找也是类似的,不过效率低一些。

# 11. V8 的排序

对于 JS 来说,数组长度大于 10 会采用快排,否则使用插入排序 源码实现 (opens new window) 。选择插入排序是因为虽然时间复杂度很差,但是在数据量很小的情况下和 O(N * logN)相差无几,然而插入排序需要的常数时间很小,所以相对别的排序来说更快。