排序 | 易良同学的博客

# 排序

# 稳定

冒泡排序(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)];
};

# V8 的排序

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