排序算法

复杂度

名称	最优复杂度	平均复杂度	最坏复杂度	空间复杂度	稳定	备注
冒泡排序	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, 1, 7, 9, 5, 8]，要求按照从左到右、从小到大的顺序进行排序。

解题思路

从左到右依次冒泡，把较大的数往右边挪动即可。

1. 首先指针指向第一个数，比较第一个数和第二个数的大小，由于 2 比 1 大，所以两两交换，[1, 2, 7, 9, 5, 8]。

2. 接下来指针往前移动一步，比较 2 和 7，由于 2 比 7 小，两者保持不动，[1, 2, 7, 9, 5, 8]。到目前为止，7 是最大的那个数。

3. 指针继续往前移动，比较 7 和 9，由于 7 比 9 小，两者保持不动，[1, 2, 7, 9, 5, 8]。现在，9 变成了最大的那个数。

4. 再往后，比较 9 和 5，很明显，9 比 5 大，交换它们的位置，[1, 2, 7, 5, 9, 8]。

5. 最后，比较 9 和 8，9 比 8 大，交换它们的位置，[1, 2, 7, 5, 8, 9]。经过第一轮的两两比较，9 这个最大的数就像冒泡一样冒到了数组的最后面。

接下来进行第二轮的比较，把指针重新指向第一个元素，重复上面的操作，最后，数组变成了：[1, 2, 5, 7, 8, 9]。

在进行新一轮的比较中，判断一下在上一轮比较的过程中有没有发生两两交换，如果一次交换都没有发生，就证明其实数组已经排好序了。

算法分析

空间复杂度

假设数组的元素个数是 n，由于在整个排序的过程中，我们是直接在给定的数组里面进行元素的两两交换，所以空间复杂度是 O(1)。

时间复杂度

1. 给定的数组按照顺序已经排好

在这种情况下，我们只需要进行 n−1 次的比较，两两交换次数为 0，时间复杂度是 O(n)。这是最好的情况。

2. 给定的数组按照逆序排列

在这种情况下，我们需要进行 n(n-1)/2 次比较，时间复杂度是 O(n2)。这是最坏的情况。

3. 给定的数组杂乱无章

在这种情况下，平均时间复杂度是 O(n2)。

由此可见，冒泡排序的时间复杂度是 O(n2)。它是一种稳定的排序算法。(稳定是指如果数组里两个相等的数，那么排序前后这两个相等的数的相对位置保持不变。)

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);
}

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let leftArr = [];
  let rightArr = [];
  let q = arr[0];
  for (let i = 1, l = arr.length; i < l; i++) {
    if (arr[i] > q) {
      rightArr.push(arr[i]);
    } else {
      leftArr.push(arr[i]);
    }
  }
  return [].concat(quickSort(leftArr), [q], quickSort(rightArr));
}

三向快速排序

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

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);

/**
 * 三向切分的快速排序指的是，将数组分为小于、等于和大于当前切分值的区域。
 * 切分点从开头字母开始
 * 擅长于有大量重复元素的情况
 */
/*
初始化状态
["S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
O < S swap(arr, lt++, i++)
["O", "S", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
R < S swap(arr, lt++, i++)
["O", "R", "S", "T", "E", "X", "A", "M", "P", "L", "E"]
T > S swap(arr, i, gt--)
["O", "R", "S", "E", "E", "X", "A", "M", "P", "L", "T"]
E < S
["O", "R", "E", "S", "E", "X", "A", "M", "P", "L", "T"]
E < S
["O", "R", "E", "E", "S", "X", "A", "M", "P", "L", "T"]
X > S
["O", "R", "E", "E", "S", "L", "A", "M", "P", "X", "T"]
["O", "R", "E", "E", "L", "S", "A", "M", "P", "X", "T"]
["O", "R", "E", "E", "L", "A", "S", "M", "P", "X", "T"]
["O", "R", "E", "E", "L", "A", "M", "S", "P", "X", "T"]
["O", "R", "E", "E", "L", "A", "M", "P", "S", "X", "T"]
S 切分完毕  ["O", "R", "E", "E", "L", "A", "M", "P",|<-| "S",|->| "X", "T"]
["O", "P", "E", "E", "L", "A", "M", "R", "S", "X", "T"]
["O", "M", "E", "E", "L", "A", "P", "R", "S", "X", "T"]
["M", "O", "E", "E", "L", "A", "P", "R", "S", "X", "T"]
["M", "E", "O", "E", "L", "A", "P", "R", "S", "X", "T"]
["M", "E", "E", "O", "L", "A", "P", "R", "S", "X", "T"]
["M", "E", "E", "L", "O", "A", "P", "R", "S", "X", "T"]
["M", "E", "E", "L", "A", "O", "P", "R", "S", "X", "T"]
["E", "M", "E", "L", "A", "O", "P", "R", "S", "X", "T"]
["E", "E", "M", "L", "A", "O", "P", "R", "S", "X", "T"]
["E", "E", "L", "M", "A", "O", "P", "R", "S", "X", "T"]
["E", "E", "L", "A", "M", "O", "P", "R", "S", "X", "T"]
["E", "E", "L", "A", "M", "O", "P", "R", "S", "X", "T"]
["E", "E", "A", "L", "M", "O", "P", "R", "S", "X", "T"]
["A", "E", "E", "L", "M", "O", "P", "R", "S", "X", "T"]
["A", "E", "E", "L", "M", "O", "P", "R", "S", "X", "T"]
["A", "E", "E", "L", "M", "O", "P", "R", "S", "T", "X"]
 */

实现

把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。

举例：把班里的所有同学按照高矮顺序排成一排。

解法：老师先随机地挑选了同学 A，让所有其他同学和 A 比高矮，比 A 矮的都站在 A 的左边，比 A 高的都站在 A 的右边。接下来，老师分别从左边和右边的同学里选择了同学 B 和 C，然后不断地筛选和排列下去。

在分成较小和较大的两个子数组过程中，如何选定一个基准值(也就是同学 A、B、C 等)尤为关键。

例题分析

对数组 [2, 1, 7, 9, 5, 8] 进行排序。

解题思路

1. 按照快速排序的思想，首先把数组筛选成较小和较大的两个子数组。

2. 随机从数组里选取一个数作为基准值，比如 7，于是原始的数组就被分成了两个子数组。注意：快速排序是直接在原始数组里进行各种交换操作，所以当子数组被分割出来的时候，原始数组里的排列也被改变了。

3. 接下来，在较小的子数组里选 2 作为基准值，在较大的子数组里选 8 作为基准值，继续分割子数组。

4. 继续将元素个数大于 1 的子数组进行划分，当所有子数组里的元素个数都为 1 的时候，原始数组也被排好序了。

时间复杂度

1. 最优情况：被选出来的基准值都是当前子数组的中间数。

这样的分割，能保证对于一个规模大小为 n 的问题，能被均匀分解成两个规模大小为 n/2 的子问题(归并排序也采用了相同的划分方法)，时间复杂度就是：T(n) = 2×T(n/2) + O(n)。

把规模大小为 n 的问题分解成 n/2 的两个子问题时，和基准值进行了 n-1 次比较，复杂度就是 O(n)。很显然，在最优情况下，快速排序的复杂度也是 O(nlogn)。

2. 最坏情况：基准值选择了子数组里的最大或者最小值

每次都把子数组分成了两个更小的子数组，其中一个的长度为 1，另外一个的长度只比原子数组少 1。

举例：对于数组来说，每次挑选的基准值分别是 9、8、7、5、2。

解法：划分过程和冒泡排序的过程类似。

算法复杂度为 O(n2)。

提示：可以通过随机地选取基准值来避免出现最坏的情况。

空间复杂度

和归并排序不同，快速排序在每次递归的过程中，只需要开辟 O(1) 的存储空间来完成交换操作实现直接对数组的修改，又因为递归次数为 logn，所以它的整体空间复杂度完全取决于压堆栈的次数，因此它的空间复杂度是 O(logn)。

举例：LeetCode 第 215 题，给定一个尚未排好序的数组，要求找出第 k 大的数。

解法 1：直接将数组进行排序，然后得出结果。

解法 2：快速排序。

每次随机选取一个基准值，将数组分成较小的一半和较大的一半，然后检查这个基准值最后所在的下标是不是 k，算法复杂度只需要 O(n)。

3. 选择排序(不稳定)

选择排序的原理如下。遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。

原地排序；不稳定排序

选择排序：选中数组中第 i 小的值与第 i 个值进行调换位置。

原理：每次从无序序列选择一个最小的。每一轮从数组的未排序部分加一开始，找到一个最小的值的索引，然后与未排序将其放到未排序部分的最左位置。

复杂度：

• 最好 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;
}

import Sort from '../Sort';

export default class SelectionSort extends Sort {
  sort(originalArray) {
    // Clone original array to prevent its modification.
    const array = [...originalArray];

    for (let i = 0; i < array.length - 1; i += 1) {
      let minIndex = i;

      // Call visiting callback.
      this.callbacks.visitingCallback(array[i]);

      // Find minimum element in the rest of array.
      for (let j = i + 1; j < array.length; j += 1) {
        // Call visiting callback.
        this.callbacks.visitingCallback(array[j]);

        if (this.comparator.lessThan(array[j], array[minIndex])) {
          minIndex = j;
        }
      }

      // If new minimum element has been found then swap it with current i-th element.
      if (minIndex !== i) {
        [array[i], array[minIndex]] = [array[minIndex], array[i]];
      }
    }

    return array;
  }
}

/**
 * 选择排序
 * @param       : <Array> target数组
 * @description : 一次内循环得到最大值的下标，然后只交换一次次序，将最大值和内循环末尾对调。
 */
module.exports.selectSort = function selectSort(target) {
  for (var j = target.length; j > 0; j--) {
    var maxIndex = 0;
    for (var i = 1; i < j; i++) {
      maxIndex = target[maxIndex] > target[i] ? maxIndex : i;
    }
    target.swap(maxIndex, j - 1);
  }
  return target;
};

4. 插入排序 (稳定)

插入排序的原理如下。第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。

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

原理：从有序序列中选择合适的位置进行插入

复杂度：

• 最好 O(n)
• 最坏 O(n^2)
• 平均 O(n^2)

function sort(arr) {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    // 0 - i 已经是有序序列。
    for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
      swap(arr, j, j - 1);
      console.log(arr);
    }
  }
  return arr;
}

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

为当前元素保存一个副本，依次向前遍历前面的元素是否比自己大，如果比自己大就直接把前一个元素赋值到当前元素的位置，当前某位置的元素不再比当前元素大的时候，将当前元素的值赋值到这个位置。

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let j,
      temp = arr[i];
    for (j = i; j > 0 && arr[j - 1] > temp; j--) {
      arr[j] = arr[j - 1];
    }
    arr[j] = temp;
  }
}

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

function insertSort(a) {
  for (let i = 1; i < length - 1; i++) {
    // console.log(a[i])
    // 内循环执行完之后排序好前面的队列
    // i + 1 就是当前需要插入的值.
    for (let j = i + 1; j >= 0; j--) {
      if (a[j] < a[j - 1]) {
        [a[j - 1], a[j]] = [a[j], a[j - 1]];
        // console.log('交换: ', a)
      } else {
        // 如果比当前最大的值还大，就不用继续比较了
        break;
      }
    }
  }
  return a;
}

console.log(insertSort(b));

优化版

let intensifyInsertArray = copyArray(arr);
function intensifyInsertSort(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;
}

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

算法实现：

export default function InsertionSort(items: Array<number>): Array<number> {
  const itemsCopy = [...items];
  let value; // the value currently being compared
  let i; // index of first element in unsorted section
  let j; // index going into sorted section

  for (i = 0; i < itemsCopy.length; i++) {
    value = itemsCopy[i];
    j = i - 1;
    while (j >= 0 && itemsCopy[j] > value) {
      itemsCopy[j + 1] = itemsCopy[j];
      j--;
    }
    itemsCopy[j + 1] = value;
  }

  return itemsCopy;
}

/**
 * 直接插入排序
 * @param       : <Array> target数组
 * @description : 将当前元素与前面元素逐一比较，比前方元素小时则将前方元素后移，直到比前方元素大则落位
 */
module.exports.straightInsertionSort = function straightInsertionSort(target) {
  for (let i = 1; i < target.length; i++) {
    var j = i;
    var base = target[i];
    while (j > 0 && base < target[j - 1]) {
      target[j] = target[j - 1];
      j--;
    }
    if (j < i) {
      target[j] = base;
    }
  }
  return target;
};

插入排序(Insertion Sort)

基本思想

不断地将尚未排好序的数插入到已经排好序的部分。

特点

在冒泡排序中，经过每一轮的排序处理后，数组后端的数是排好序的；而对于插入排序来说，经过每一轮的排序处理后，数组前端的数都是排好序的。

例题分析

对数组 [2, 1, 7, 9, 5, 8] 进行插入排序。

解题思路

首先将数组分成左右两个部分，左边是已经排好序的部分，右边是还没有排好序的部分，刚开始，左边已排好序的部分只有第一个元素 2。接下来，我们对右边的元素一个一个进行处理，将它们放到左边。

1. 先来看 1，由于 1 比 2 小，需要将 1 插入到 2 的前面，做法很简单，两两交换位置即可，[1, 2, 7, 9, 5, 8]。

2. 然后，我们要把 7 插入到左边的部分，由于 7 已经比 2 大了，表明它是目前最大的元素，保持位置不变，[1, 2, 7, 9, 5, 8]。

3. 同理，9 也不需要做位置变动，[1, 2, 7, 9, 5, 8]。

4. 接下来，如何把 5 插入到合适的位置。首先比较 5 和 9，由于 5 比 9 小，两两交换，[1, 2, 7, 5, 9, 8]，继续，由于 5 比 7 小，两两交换，[1, 2, 5, 7, 9, 8]，最后，由于 5 比 2 大，此轮结束。

5. 最后一个数是 8，由于 8 比 9 小，两两交换，[1, 2, 5, 7, 8, 9]，再比较 7 和 8，发现 8 比 7 大，此轮结束。到此，插入排序完毕。

代码示例

void sort(int`[]` nums) {
// 将数组的第一个元素当作已经排好序的，从第二个元素，即 i 从 1 开始遍历数组
for (int i = 1, j, current; i < nums.length; i++) {
// 外围循环开始，把当前 i 指向的值用 current 保存
current = nums`[i]`;

        // 指针 j 内循环，和 current 值比较，若 j 所指向的值比 current 值大，则该数右移一位
        for (j = i \- 1; j >= 0 && nums`[j]` > current; j\-\-) {
            nums`[j + 1]` = nums`[j]`;
            }

        // 内循环结束，j+1 所指向的位置就是 current 值插入的位置
        nums`[j + 1]` = current;
    }

}

算法分析

空间复杂度

假设数组的元素个数是 n，由于在整个排序的过程中，是直接在给定的数组里面进行元素的两两交换，空间复杂度是 O(1)。

时间复杂度

1. 给定的数组按照顺序已经排好

只需要进行 n-1 次的比较，两两交换次数为 0，时间复杂度是 O(n)。这是最好的情况。

2. 给定的数组按照逆序排列

在这种情况下，我们需要进行 n(n-1)/2 次比较，时间复杂度是 O(n2)。这是最坏的情况。

3. 给定的数组杂乱无章

在这种情况下，平均时间复杂度是 O(n2)。

由此可见，和冒泡排序一样，插入排序的时间复杂度是 O(n2)，并且它也是一种稳定的排序算法。

建议：LeetCode 第 147 题，要求对一个链表进行插入排序，希望大家去试一试。

归并排序(Merge Sort)

基本思想

核心是分治，就是把一个复杂的问题分成两个或多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。归并排序将分治的思想体现得淋漓尽致。

实现

一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始排序。

排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。

例题分析

例题：利用归并排序算法对数组 [2, 1, 7, 9, 5, 8] 进行排序。

解题思路

首先不断地对数组进行切分，直到各个子数组里只包含一个元素。

接下来递归地按照大小顺序合并切分开的子数组，递归的顺序和二叉树里的前向遍历类似。

1. 合并 [2] 和 [1] 为 [1, 2]。

2. 子数组 [1, 2] 和 [7] 合并。

3. 右边，合并 [9] 和 [5]。

4. 然后合并 [5, 9] 和 [8]。

5. 最后合并 [1, 2, 7] 和 [5, 8, 9] 成 [1, 2, 5, 8, 9]，就可以把整个数组排好序了。

合并数组 [1, 2, 7] 和 [5, 8, 9] 的操作步骤如下。

1. 把数组 [1, 2, 7] 用 L 表示，[5, 8, 9] 用 R 表示。

2. 合并的时候，开辟分配一个新数组 T 保存结果，数组大小应该是两个子数组长度的总和

3. 然后下标 i、j、k 分别指向每个数组的起始点。

4. 接下来，比较下标 i 和 j 所指向的元素 L[i] 和 R[j]，按照大小顺序放入到下标 k 指向的地方，1 小于 5。

5. 移动 i 和 k，继续比较 L[i] 和 R[j]，2 比 5 小。

6. i 和 k 继续往前移动，5 比 7 小。

7. 移动 j 和 k，继续比较 L[i] 和 R[j]，7 比 8 小。

8. 这时候，左边的数组已经处理完毕，直接将右边数组剩余的元素放到结果数组里就好。

合并之所以能成功，先决条件必须是两个子数组都已经分别排好序了。

算法分析

空间复杂度

由于合并 n 个元素需要分配一个大小为 n 的额外数组，合并完成之后，这个数组的空间就会被释放，所以算法的空间复杂度就是 O(n)。归并排序也是稳定的排序算法。

时间复杂度

归并算法是一个不断递归的过程。

举例：数组的元素个数是 n，时间复杂度是 T(n) 的函数。

解法：把这个规模为 n 的问题分成两个规模分别为 n/2 的子问题，每个子问题的时间复杂度就是 T(n/2)，那么两个子问题的复杂度就是 2×T(n/2)。当两个子问题都得到了解决，即两个子数组都排好了序，需要将它们合并，一共有 n 个元素，每次都要进行最多 n-1 次的比较，所以合并的复杂度是 O(n)。由此我们得到了递归复杂度公式： T(n) = 2×T(n/2) + O(n)。

对于公式求解，不断地把一个规模为 n 的问题分解成规模为 n/2 的问题，一直分解到规模大小为 1。如果 n 等于 2，只需要分一次；如果 n 等于 4，需要分 2 次。这里的次数是按照规模大小的变化分类的。

以此类推，对于规模为 n 的问题，一共要进行 log(n) 层的大小切分。在每一层里，我们都要进行合并，所涉及到的元素其实就是数组里的所有元素，因此，每一层的合并复杂度都是 O(n)，所以整体的复杂度就是 O(nlogn)。

建议：归并算法的思想很重要，其中对两个有序数组合并的操作，在很多面试题里都有用到，建议大家一定要把这个算法练熟。

class BubbleSort extends Sort {
  sort(originalArray) {
    // Flag that holds info about whether the swap has occur or not.
    let swapped = false;
    // Clone original array to prevent its modification.
    const array = [...originalArray];

    for (let i = 1; i < array.length; i += 1) {
      swapped = false;

      // Call visiting callback.
      this.callbacks.visitingCallback(array[i]);

      for (let j = 0; j < array.length - i; j += 1) {
        // Call visiting callback.
        this.callbacks.visitingCallback(array[j]);

        // Swap elements if they are in wrong order.
        if (this.comparator.lessThan(array[j + 1], array[j])) {
          [array[j], array[j + 1]] = [array[j + 1], array[j]];

          // Register the swap.
          swapped = true;
        }
      }

      // If there were no swaps then array is already sorted and there is
      // no need to proceed.
      if (!swapped) {
        return array;
      }
    }

    return array;
  }
}

/**
 * 冒泡排序
 * @param       : <Array> target数组
 * @description : 冒泡排序，更贴切的形容应该是沉底排序，每一轮内循环就是最大数沉底了。
 */
module.exports.bubbleSort = function bubbleSort(target) {
  for (var j = target.length; j > 0; j--) {
    for (var i = 0; i < j - 1; i++) {
      if (target[i] > target[i + 1]) {
        target.swap(i, i + 1);
      }
    }
  }
  return target;
};

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;
}

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

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

// 从 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) {
      console.log('比较 ', i, j, a[i], a[j], a[j] < a[i] ? '交换' : '不交换');
      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)) {
    console.log('gap', gap);
    console.log('a', a);
    insertSort(a, 0, gap);
  }
  return a;
}

console.log(hillSort(b));

import Sort from '../Sort';

export default class ShellSort extends Sort {
  sort(originalArray) {
    // Prevent original array from mutations.
    const array = [...originalArray];

    // Define a gap distance.
    let gap = Math.floor(array.length / 2);

    // Until gap is bigger then zero do elements comparisons and swaps.
    while (gap > 0) {
      // Go and compare all distant element pairs.
      for (let i = 0; i < array.length - gap; i += 1) {
        let currentIndex = i;
        let gapShiftedIndex = i + gap;

        while (currentIndex >= 0) {
          // Call visiting callback.
          this.callbacks.visitingCallback(array[currentIndex]);

          // Compare and swap array elements if needed.
          if (this.comparator.lessThan(array[gapShiftedIndex], array[currentIndex])) {
            const tmp = array[currentIndex];
            array[currentIndex] = array[gapShiftedIndex];
            array[gapShiftedIndex] = tmp;
          }

          gapShiftedIndex = currentIndex;
          currentIndex -= gap;
        }
      }

      // Shrink the gap.
      gap = Math.floor(gap / 2);
    }

    // Return sorted copy of an original array.
    return array;
  }
}

/**
 * 希尔排序
 * @param       : <Array> target数组
 * @description : 插入排序的改版：使用定好的偏移量分组，组内进行插入排序；减小偏移量重复进行分组排序直到偏移量为1.
 */
module.exports.shellSort = function shellSort(target) {
  const len = target.length;
  // 偏移量递减
  for (let dx = Math.floor(len / 2); dx > 0; dx = Math.floor(dx / 2)) {
    // 按偏移量分组[0,dx,2dx...], [1, 1+dx, 1+2dx...]
    for (let i = 0; i < dx; i++) {
      // 组内插入排序
      for (let j = i + dx; j < len; j += dx) {
        let k = j;
        let base = target[k];
        // 插入元素
        while (k > i && base < target[k - dx]) {
          target[k] = target[k - dx];
          k -= dx;
        }
        if (k < j) {
          target[k] = base;
        }
      }
    }
  }
  return target;
};

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)];
};

console.log(mergeSort(b));

优化版

let intensifyMergeArray = copyArray(arr);
function intensifyMerge(arr, l, mid, r) {
  let i = l,
    j = mid + 1,
    newArr = arr.slice(l, r + 1);
  for (let m = l; m <= r; m++) {
    if (i > mid) {
      arr[m] = newArr[j - l];
      j++;
    } else if (j > r) {
      arr[m] = newArr[i - l];
      i++;
    } else if (newArr[i - l] < newArr[j - l]) {
      arr[m] = newArr[i - l];
      i++;
    } else {
      arr[m] = newArr[j - l];
      j++;
    }
  }
}

function intensifyMergeEvent(arr, l, r) {
  if (l >= r) return;

  let mid = Math.floor((l + r) / 2);
  intensifyMergeEvent(arr, l, mid);
  intensifyMergeEvent(arr, mid + 1, r);

  if (arr[mid] > arr[mid + 1]) {
    intensifyMerge(arr, l, mid, r);
  }
}

function intensifyMergeSort(arr) {
  intensifyMergeEvent(arr, 0, arr.length - 1);
}

import Sort from '../Sort';

export default class MergeSort extends Sort {
  sort(originalArray) {
    // Call visiting callback.
    this.callbacks.visitingCallback(null);

    // If array is empty or consists of one element then return this array since it is sorted.
    if (originalArray.length <= 1) {
      return originalArray;
    }

    // Split array on two halves.
    const middleIndex = Math.floor(originalArray.length / 2);
    const leftArray = originalArray.slice(0, middleIndex);
    const rightArray = originalArray.slice(middleIndex, originalArray.length);

    // Sort two halves of split array
    const leftSortedArray = this.sort(leftArray);
    const rightSortedArray = this.sort(rightArray);

    // Merge two sorted arrays into one.
    return this.mergeSortedArrays(leftSortedArray, rightSortedArray);
  }

  mergeSortedArrays(leftArray, rightArray) {
    let sortedArray = [];

    // In case if arrays are not of size 1.
    while (leftArray.length && rightArray.length) {
      let minimumElement = null;

      // Find minimum element of two arrays.
      if (this.comparator.lessThanOrEqual(leftArray[0], rightArray[0])) {
        minimumElement = leftArray.shift();
      } else {
        minimumElement = rightArray.shift();
      }

      // Call visiting callback.
      this.callbacks.visitingCallback(minimumElement);

      // Push the minimum element of two arrays to the sorted array.
      sortedArray.push(minimumElement);
    }

    // If one of two array still have elements we need to just concatenate
    // this element to the sorted array since it is already sorted.
    if (leftArray.length) {
      sortedArray = sortedArray.concat(leftArray);
    }

    if (rightArray.length) {
      sortedArray = sortedArray.concat(rightArray);
    }

    return sortedArray;
  }
}

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

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

let aux = new Array(arr.length);
function sort(arr) {
  const len = arr.length;
  aux = new Array(len);
  for (let sz = 1; sz < len; sz = sz + sz) {
    for (let lo = 0; lo < len - sz; lo += sz + sz) {
      merge(arr, lo, lo + sz - 1, Math.min((len - 1, lo + sz + sz - 1)));
    }
  }
}

function merge(arr, lo, mid, hi) {
  let i = lo,
    j = mid + 1;
  for (let k = lo; k <= hi; k++) {
    aux[k] = arr[k];
  }
  for (let k = lo; k <= hi; k++) {
    if (i > mid) arr[k] = aux[j++];
    else if (j > hi) arr[k] = aux[i++];
    else if (aux[j] < aux[i]) arr[k] = aux[j++];
    else arr[k] = aux[i++];
  }
  console.log(arr);
}

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

/*
这是一种先两两对比，然后44对比，如此往复。
最后对比整个数组。
["S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
["O", "S", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
["O", "S", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
["O", "S", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
["O", "S", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
["O", "S", "R", "T", "E", "X", "A", "M", "L", "P", "E"]
["O", "R", "S", "T", "E", "X", "A", "M", "L", "P", "E"]
["O", "R", "S", "T", "A", "E", "M", "X", "L", "P", "E"]
["O", "R", "S", "T", "A", "E", "M", "X", "E", "L", "P", undefined]
["A", "E", "M", "O", "R", "S", "T", "X", "E", "L", "P", undefined]
["A", "E", "E", "L", "M", "O", "P", "R", "S", "T", "X", undefined, undefined, undefined, undefined, undefined]
*/

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

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

let aux = new Array(arr.length);
function sort(arr, lo, hi) {
  if (hi <= lo) return;
  let mid = lo + parseInt((hi - lo) / 2);

  sort(arr, lo, mid);
  sort(arr, mid + 1, hi);
  merge(arr, lo, mid, hi);
}

function merge(arr, lo, mid, hi) {
  let i = lo,
    j = mid + 1;
  for (let k = lo; k <= hi; k++) {
    aux[k] = arr[k];
  }
  for (let k = lo; k <= hi; k++) {
    if (i > mid) arr[k] = aux[j++];
    else if (j > hi) arr[k] = aux[i++];
    else if (aux[j] < aux[i]) arr[k] = aux[j++];
    else arr[k] = aux[i++];
  }
  console.log(arr);
}

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

/*
通过归并法缩小范围
["S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
left
["O", "S", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
["O", "R", "S", "T", "E", "X", "A", "M", "P", "L", "E"]
["O", "R", "S", "E", "T", "X", "A", "M", "P", "L", "E"]
["O", "R", "S", "E", "T", "X", "A", "M", "P", "L", "E"]
["E", "O", "R", "S", "T", "X", "A", "M", "P", "L", "E"]
["E", "O", "R", "S", "T", "X", "A", "M", "P", "L", "E"]
right
["E", "O", "R", "S", "T", "X", "A", "M", "P", "L", "E"]
["E", "O", "R", "S", "T", "X", "A", "M", "P", "E", "L"]
["E", "O", "R", "S", "T", "X", "A", "E", "L", "M", "P"]
all
["A", "E", "E", "L", "M", "O", "P", "R", "S", "T", "X"]
*/

// 常见排序算法

/**
 * 归并排序
 * @param       : <Array> target 要归并排序的数组
 * @description : 归并排序，将数组递归分割成两个子数组直至数组只有一个元素，然后将这两个有序数组合并成一个有序数组;
 */
function mergeSortedArray(arrA, arrB) {
  var result = [];
  var i = 0,
    j = 0,
    targetLen = arrA.length,
    toolLen = arrB.length;
  while (i < targetLen && j < toolLen) {
    if (arrA[i] < arrB[j]) {
      result.push(arrA[i++]);
    } else {
      result.push(arrB[j++]);
    }
  }
  while (i < targetLen) {
    result.push(arrA[i++]);
  }
  while (j < toolLen) {
    result.push(arrB[j++]);
  }
  return result;
}

module.exports.mergeSort = function mergeSort(target) {
  if (target.length === 1) {
    return target;
  }
  var mid = Math.floor(target.length / 2);
  var left = target.slice(0, mid);
  var right = target.slice(mid);
  return mergeSortedArray(mergeSort(left), mergeSort(right));
};

7. 桶排序

// 桶排序. 值都是大于 0 的， 并且差不多都是均匀分布
// 桶排序的时间复杂度为 O(m+n)
const b = [3, 4, 6, 1, 3, 6, 32, 45, 21, 12],
  length = b.length;

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;
}

console.log(bucketSort(b));

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;
}

console.log(insertSort(b));

import Sort from '../Sort';

// Using charCode (a = 97, b = 98, etc), we can map characters to buckets from 0 - 25
const BASE_CHAR_CODE = 97;
const NUMBER_OF_POSSIBLE_DIGITS = 10;
const ENGLISH_ALPHABET_LENGTH = 26;

export default class RadixSort extends Sort {
  /**
   * @param {*[]} originalArray
   * @return {*[]}
   */
  sort(originalArray) {
    // Assumes all elements of array are of the same type
    const isArrayOfNumbers = this.isArrayOfNumbers(originalArray);

    let sortedArray = [...originalArray];
    const numPasses = this.determineNumPasses(sortedArray);

    for (let currentIndex = 0; currentIndex < numPasses; currentIndex += 1) {
      const buckets = isArrayOfNumbers
        ? this.placeElementsInNumberBuckets(sortedArray, currentIndex)
        : this.placeElementsInCharacterBuckets(sortedArray, currentIndex, numPasses);

      // Flatten buckets into sortedArray, and repeat at next index
      sortedArray = buckets.reduce((acc, val) => {
        return [...acc, ...val];
      }, []);
    }

    return sortedArray;
  }

  /**
   * @param {*[]} array
   * @param {number} index
   * @return {*[]}
   */
  placeElementsInNumberBuckets(array, index) {
    // See below. These are used to determine which digit to use for bucket allocation
    const modded = 10 ** (index + 1);
    const divided = 10 ** index;
    const buckets = this.createBuckets(NUMBER_OF_POSSIBLE_DIGITS);

    array.forEach(element => {
      this.callbacks.visitingCallback(element);
      if (element < divided) {
        buckets[0].push(element);
      } else {
        /**
         * Say we have element of 1,052 and are currently on index 1 (starting from 0). This means
         * we want to use '5' as the bucket. `modded` would be 10 ** (1 + 1), which
         * is 100. So we take 1,052 % 100 (52) and divide it by 10 (5.2) and floor it (5).
         */
        const currentDigit = Math.floor((element % modded) / divided);
        buckets[currentDigit].push(element);
      }
    });

    return buckets;
  }

  /**
   * @param {*[]} array
   * @param {number} index
   * @param {number} numPasses
   * @return {*[]}
   */
  placeElementsInCharacterBuckets(array, index, numPasses) {
    const buckets = this.createBuckets(ENGLISH_ALPHABET_LENGTH);

    array.forEach(element => {
      this.callbacks.visitingCallback(element);
      const currentBucket = this.getCharCodeOfElementAtIndex(element, index, numPasses);
      buckets[currentBucket].push(element);
    });

    return buckets;
  }

  /**
   * @param {string} element
   * @param {number} index
   * @param {number} numPasses
   * @return {number}
   */
  getCharCodeOfElementAtIndex(element, index, numPasses) {
    // Place element in last bucket if not ready to organize
    if (numPasses - index > element.length) {
      return ENGLISH_ALPHABET_LENGTH - 1;
    }

    /**
     * If each character has been organized, use first character to determine bucket,
     * otherwise iterate backwards through element
     */
    const charPos = index > element.length - 1 ? 0 : element.length - index - 1;

    return element.toLowerCase().charCodeAt(charPos) - BASE_CHAR_CODE;
  }

  /**
   * Number of passes is determined by the length of the longest element in the array.
   * For integers, this log10(num), and for strings, this would be the length of the string.
   */
  determineNumPasses(array) {
    return this.getLengthOfLongestElement(array);
  }

  /**
   * @param {*[]} array
   * @return {number}
   */
  getLengthOfLongestElement(array) {
    if (this.isArrayOfNumbers(array)) {
      return Math.floor(Math.log10(Math.max(...array))) + 1;
    }

    return array.reduce((acc, val) => {
      return val.length > acc ? val.length : acc;
    }, -Infinity);
  }

  /**
   * @param {*[]} array
   * @return {boolean}
   */
  isArrayOfNumbers(array) {
    // Assumes all elements of array are of the same type
    return this.isNumber(array[0]);
  }

  /**
   * @param {number} numBuckets
   * @return {*[]}
   */
  createBuckets(numBuckets) {
    /**
     * Mapping buckets to an array instead of filling them with
     * an array prevents each bucket from containing a reference to the same array
     */
    return new Array(numBuckets).fill(null).map(() => []);
  }

  /**
   * @param {*} element
   * @return {boolean}
   */
  isNumber(element) {
    return Number.isInteger(element);
  }
}

9. 计数排序

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

function insertSort(a) {
  let min = (max = 0);
  for (let i = 0; i < a.length - 1; i++) {
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] > a[i]) {
        max = j;
      } else {
        min = i;
      }
    }
  }
  console.log('max', max, a[max]);
  console.log('min', min, a[min]);
  return a;
}

console.log(insertSort(b));

/**
 * Assumes each of the n input elements is an integer in the range 0 --> k,
 * for some integer k. If k = O(n), then CountingSort runs in ϴ(n) time
 *
 * Notes:
 * - Requires no user input of min or max
 * - Supports negative numbers
 *
 * @complexity: O(k) where k is the range
 * @flow
 */
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;
}

import Sort from '../Sort';

export default class CountingSort extends Sort {
  /**
   * @param {number[]} originalArray
   * @param {number} [smallestElement]
   * @param {number} [biggestElement]
   */
  sort(originalArray, smallestElement = undefined, biggestElement = undefined) {
    // Init biggest and smallest elements in array in order to build number bucket array later.
    let detectedSmallestElement = smallestElement || 0;
    let detectedBiggestElement = biggestElement || 0;

    if (smallestElement === undefined || biggestElement === undefined) {
      originalArray.forEach(element => {
        // Visit element.
        this.callbacks.visitingCallback(element);

        // Detect biggest element.
        if (this.comparator.greaterThan(element, detectedBiggestElement)) {
          detectedBiggestElement = element;
        }

        // Detect smallest element.
        if (this.comparator.lessThan(element, detectedSmallestElement)) {
          detectedSmallestElement = element;
        }
      });
    }

    // Init buckets array.
    // This array will hold frequency of each number from originalArray.
    const buckets = Array(detectedBiggestElement - detectedSmallestElement + 1).fill(0);

    originalArray.forEach(element => {
      // Visit element.
      this.callbacks.visitingCallback(element);

      buckets[element - detectedSmallestElement] += 1;
    });

    // Add previous frequencies to the current one for each number in bucket
    // to detect how many numbers less then current one should be standing to
    // the left of current one.
    for (let bucketIndex = 1; bucketIndex < buckets.length; bucketIndex += 1) {
      buckets[bucketIndex] += buckets[bucketIndex - 1];
    }

    // Now let's shift frequencies to the right so that they show correct numbers.
    // I.e. if we won't shift right than the value of buckets[5] will display how many
    // elements less than 5 should be placed to the left of 5 in sorted array
    // INCLUDING 5th. After shifting though this number will not include 5th anymore.
    buckets.pop();
    buckets.unshift(0);

    // Now let's assemble sorted array.
    const sortedArray = Array(originalArray.length).fill(null);
    for (let elementIndex = 0; elementIndex < originalArray.length; elementIndex += 1) {
      // Get the element that we want to put into correct sorted position.
      const element = originalArray[elementIndex];

      // Visit element.
      this.callbacks.visitingCallback(element);

      // Get correct position of this element in sorted array.
      const elementSortedPosition = buckets[element - detectedSmallestElement];

      // Put element into correct position in sorted array.
      sortedArray[elementSortedPosition] = element;

      // Increase position of current element in the bucket for future correct placements.
      buckets[element - detectedSmallestElement] += 1;
    }

    // Return sorted array.
    return sortedArray;
  }
}

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);
  }
}

const arr = [1, 2, 3, 11, 13, 12, 9, 8, 10, 15, 14, 7];
heapSort(arr, arr.length);
console.log(arr);

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

import MaxHeap from '../DataStructures/MaxHeap';

export default function HeapSort(items: Array<number>) {
  const heap = new MaxHeap();
  const list = [];

  // Insert every element in the node into the heap. Calling
  // insert() will maxHeapify()
  items.forEach(item => {
    heap.insert(item);
  });

  // For every element in the heap, delete the max value.
  // Right after deletion, the MaxHeap will automatically propogate
  // the next highest value of the heap to the root
  heap.get().forEach(() => {
    // Delete the roo
    const node = heap.deleteNodeIndex(0);
    list.push(node);
  });

  return list.reverse();
}

const pq = [];
let N = 0;

function less(i, j) {
  return pq[i] < pq[j];
}

function swap(i, j) {
  let tmp = pq[i];
  pq[i] = pq[j];
  pq[j] = tmp;
}

// 上浮
function swim(k) {
  while (k > 1 && less(parseInt(k / 2), k)) {
    swap(parseInt(k / 2), k);
    k = parseInt(k / 2);
  }
}

// 下沉
function sink(k) {
  while (2 * k <= N) {
    let j = 2 * k;
    if ((j < N) & less(j, j + 1)) j++;
    if (!less(k, j)) break;
    swap(k, j);
    k = j;
  }
}

function insert(v) {
  pq[++N] = v;
  swim(N);
  console.log(pq);
}

function deleteMax() {
  let max = pq[1];
  swap(1, N--);
  pq[N + 1] = null;
  sink(1);
  console.log(pq);
  return max;
}

insert('P');
insert('Q');
insert('E');
deleteMax();
insert('X');
insert('A');
insert('M');
deleteMax();
insert('P');
insert('L');
insert('E');
deleteMax();

/**
 * 堆排序
 * 将数组变为二叉字符树
 * 通过操作字符数的上浮和下沉来完成两个功能
 *  1. 删除并返回最大值
 *  2. 插入并求出最大值
 */
/*
[empty, "P"]
[empty, "Q", "P"]
[empty, "Q", "P", "E"]
[empty, "P", "E", null]
[empty, "X", "E", "P"]
[empty, "X", "E", "P", "A"]
[empty, "X", "M", "P", "A", "E"]
[empty, "P", "M", "E", "A", null]
[empty, "P", "P", "E", "A", "M"]
[empty, "P", "P", "L", "A", "M", "E"]
[empty, "P", "P", "L", "A", "M", "E", "E"]
[empty, "P", "M", "L", "A", "E", "E", null]
 */

// 上浮
// function swim(k) {
//     while (k > 1 && less(parseInt(k / 2), k)) {
//         swap(parseInt(k / 2), k)
//         k = parseInt(k / 2)
//     }
// }

// 下沉
function sink(arr, k, len) {
  while (2 * k <= len) {
    let j = 2 * k;
    if ((j < len) & (arr[j] < arr[j + 1])) j++;
    if (arr[k] >= arr[j]) break;
    swap(arr, k, j);
    k = j;
  }
  console.log('sink', arr);
}

function sort(arr) {
  let len = arr.length;
  console.log('step 01');
  for (let k = parseInt(len / 2); k >= 0; k--) {
    sink(arr, k, len);
  }
  len--;
  console.log('step 02');
  while (len > 0) {
    swap(arr, 0, len--);
    sink(arr, 0, len);
  }
  console.log(arr);
}

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

const arr = ['S', 'O', 'R', 'T', 'E', 'X', 'A', 'M', 'P', 'L', 'E'];
sort(arr);

/**
 * 堆排序
 * 先将数组进行堆有序化
 * 然后求出最大值移动到最后
 * 然后将堆的范围向前缩小一位
 */
/*
step 01
["S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"]
["S", "O", "R", "T", "P", "X", "A", "M", "E", "L", "E"]
["S", "O", "R", "T", "P", "X", "A", "M", "E", "L", "E"]
["S", "O", "X", "T", "P", "R", "A", "M", "E", "L", "E"]
["S", "X", "R", "T", "P", "O", "A", "M", "E", "L", "E"]
["X", "T", "R", "S", "P", "O", "A", "M", "E", "L", "E"]
step 02
["T", "S", "R", "M", "P", "O", "A", "E", "E", "L", "X"]
["S", "R", "P", "M", "L", "O", "A", "E", "E", "T", "X"]
["R", "P", "O", "M", "L", "E", "A", "E", "S", "T", "X"]
["P", "O", "L", "M", "E", "E", "A", "R", "S", "T", "X"]
["O", "M", "L", "A", "E", "E", "P", "R", "S", "T", "X"]
["M", "L", "E", "A", "E", "O", "P", "R", "S", "T", "X"]
["L", "E", "E", "A", "M", "O", "P", "R", "S", "T", "X"]
["E", "E", "A", "L", "M", "O", "P", "R", "S", "T", "X"]
["E", "A", "E", "L", "M", "O", "P", "R", "S", "T", "X"]
["A", "E", "E", "L", "M", "O", "P", "R", "S", "T", "X"]
*/

/**
 * 堆排序
 * @param       : <Array> target
 * @description : 通过构建大(小)根堆的方式进行排序，PS：使用函数副作用来进行原地排序
 */
// 递归调整 i~j 层的大根堆
function adjustMaxHeap(target, i, j) {
  let parent = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;

  // 比较父节点与左右叶子节点，取最大值的下标设为父节点下标
  if (left < j && target[parent] < target[left]) {
    parent = left;
  }
  if (right < j && target[parent] < target[right]) {
    parent = right;
  }
  // 只有父节点发生改变才会破坏大根堆结构，此时才需要继续调整下级大根堆
  if (parent != i) {
    target.swap(i, parent);
    adjustMaxHeap(target, parent, j);
  }
}
// 构建大根堆就是不断调整最大堆的过程，只要从最后一个父节点往上调整到第一个父节点，就能构建出大根堆
// 从0开始的n层堆的结构：len = 2^n - 1，第n层全是叶子，所以第n-1层的最后一个父节点就是floor(len/2)-1
function buildMaxHeap(target) {
  const len = target.length;
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
    adjustMaxHeap(target, i, len);
  }
}

function sortMaxHeap(target) {
  for (let i = target.length - 1; i > 0; i--) {
    target.swap(0, i);
    adjustMaxHeap(target, 0, i);
  }
}
// 先构建一个大根堆，然后从最后一个元素开始交换堆顶元素，每次交换都调整根堆，直到数组头则完成排序
module.exports.heapSort = function heapSort(target) {
  buildMaxHeap(target);
  sortMaxHeap(target);
  return target;
};

/**
 * 堆排序提取部分记录
 * 从大数据中提取最大(小)的n条记录，也可以用小(大)根堆来实现
 * 先用数据集中前n条数据构造一个小根堆，然后将后面的数据依次通过这个小根堆：
 * 比堆顶小的数据直接丢弃，比堆顶大则替换堆顶，然后调整根堆。最后输出小根堆的排序
 */
module.exports.topSortViaHeap = function topSortViaHeap(target) {
  const len = 10;
  let ret = target.slice(0, len);
  buildMaxHeap(ret);
  for (var i = len; i < target.length; i++) {
    if (target[i] < ret[0]) {
      ret[0] = target[i];
      adjustMaxHeap(ret, 0, ret.length);
    }
  }
  sortMaxHeap(ret);
  return ret;
};

堆排序实战题

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

二分搜索树

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

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

11. V8 的排序

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

12. 拓扑排序 (Topological Sort)

基本思想

和前面介绍的几种排序不同，拓扑排序应用的场合不再是一个简单的数组，而是研究图论里面顶点和顶点连线之间的性质。拓扑排序就是要将这些顶点按照相连的性质进行排序。

要能实现拓扑排序，得有几个前提：

1. 图必须是有向图

2. 图里面没有环

拓扑排序一般用来理清具有依赖关系的任务。

举例：假设有三门课程 A、B、C，如果想要学习课程 C 就必须先把课程 B 学完，要学习课程 B，还得先学习课程 A，所以得出课程的学习顺序应该是 A -> B -> C。

实现

1. 将问题用一个有向无环图(DAG, Directed Acyclic Graph)进行抽象表达，定义出哪些是图的顶点，顶点之间如何互相关联。

2. 可以利用广度优先搜索或深度优先搜索来进行拓扑排序。

例题分析

有一个学生想要修完 5 门课程的学分，这 5 门课程分别用 1、2、3、4、5 来表示，现在已知学习这些课程有如下的要求：

• 课程 2 和 4 依赖于课程 1

• 课程 3 依赖于课程 2 和 4

• 课程 4 依赖于课程 1 和 2

• 课程 5 依赖于课程 3 和 4

那么这个学生应该按照怎样的顺序来学习这 5 门课程呢？

解题思路

可以把 5 门课程看成是一个图里的 5 个顶点，用有向线段按照它们的相互关系连起来，于是得出下面的有向图。

首先可以看到，这个有向图里没有环，无论从哪个顶点出发，都不会再回到那个顶点。并且，这个图里并没有孤岛的出现，因此，我们可以对它进行拓扑排序。

方法就是，一开始的时候，对每个顶点统计它们各自的前驱(也就是入度)：1(0)，2(1)，3(2)，4(1)，5(2)。

1. 选择其中一个没有前驱(也就是入度为 0)的顶点，在这道题里面，顶点 1 就是我们要找的那个点，将它作为结果输出。同时删除掉该顶点和所有以它作为起始点的有向边，更新顶点的入度表。

2. 接下来，顶点 2 就是下一个没有前驱的顶点，输出顶点 2，并将以它作为起点的有向边删除，同时更新入度表。

3. 再来，顶点 4 成为了没有前驱的顶点，输出顶点 4，删除掉它和顶点 3 和 5 的有向边。

4. 然后，顶点 3 没有了前驱，输出它，并删除它与 5 的有向边。

5. 最后，顶点 5 没有前驱，输出它，于是得出最后的结果为：1，2，4，3，5。

一般来说，一个有向无环图可以有一个或多个拓扑排序的序列。

代码示例

运用广度优先搜索的方法对这个图的结构进行遍历。在构建这个图的过程中，用一个链接矩阵 adj 来表示这个图的结构，用一个 indegree 的数组统计每个顶点的入度，重点看如何实现拓扑排序。

void sort() { Queue q = new LinkedList(); // 定义一个队列 q

// 将所有入度为 0 的顶点加入到队列 q
for (int v = 0; v < V; v++) {
    if (indegree`[v]` == 0) q.add(v);
}

// 循环，直到队列为空
while (!q.isEmpty()) {
    int v = q.poll();
    // 每次循环中，从队列中取出顶点，即为按照入度数目排序中最小的那个顶点
    print(v);

    // 将跟这个顶点相连的其他顶点的入度减 1，如果发现那个顶点的入度变成了 0，将其加入到队列的末尾
    for (int u = 0; u < adj`[v]`.length; u++) {
        if (\-\-indegree`[u]` == 0) {
            q.add(u);
        }
    }
}

}

算法分析

时间复杂度

统计顶点的入度需要 O(n) 的时间，接下来每个顶点被遍历一次，同样需要 O(n) 的时间，所以拓扑排序的时间复杂度是 O(n)。

import Sort from '../Sort';

export default class QuickSort extends Sort {
  /**
   * @param {*[]} originalArray
   * @return {*[]}
   */
  sort(originalArray) {
    // Clone original array to prevent it from modification.
    const array = [...originalArray];

    // If array has less than or equal to one elements then it is already sorted.
    if (array.length <= 1) {
      return array;
    }

    // Init left and right arrays.
    const leftArray = [];
    const rightArray = [];

    // Take the first element of array as a pivot.
    const pivotElement = array.shift();
    const centerArray = [pivotElement];

    // Split all array elements between left, center and right arrays.
    while (array.length) {
      const currentElement = array.shift();

      // Call visiting callback.
      this.callbacks.visitingCallback(currentElement);

      if (this.comparator.equal(currentElement, pivotElement)) {
        centerArray.push(currentElement);
      } else if (this.comparator.lessThan(currentElement, pivotElement)) {
        leftArray.push(currentElement);
      } else {
        rightArray.push(currentElement);
      }
    }

    // Sort left and right arrays.
    const leftArraySorted = this.sort(leftArray);
    const rightArraySorted = this.sort(rightArray);

    // Let's now join sorted left array with center array and with sorted right array.
    return leftArraySorted.concat(centerArray, rightArraySorted);
  }
}

import Sort from '../Sort';

export default class QuickSortInPlace extends Sort {
  /** Sorting in place avoids unnecessary use of additional memory, but modifies input array.
   *
   * This process is difficult to describe, but much clearer with a visualization:
   * @see: http://www.algomation.com/algorithm/quick-sort-visualization
   *
   * @param {*[]} originalArray - Not sorted array.
   * @param {number} inputLowIndex
   * @param {number} inputHighIndex
   * @param {boolean} recursiveCall
   * @return {*[]} - Sorted array.
   */
  sort(originalArray, inputLowIndex = 0, inputHighIndex = originalArray.length - 1, recursiveCall = false) {
    // Copies array on initial call, and then sorts in place.
    const array = recursiveCall ? originalArray : [...originalArray];

    /**
     * The partitionArray() operates on the subarray between lowIndex and highIndex, inclusive.
     * It arbitrarily chooses the last element in the subarray as the pivot.
     * Then, it partially sorts the subarray into elements than are less than the pivot,
     * and elements that are greater than or equal to the pivot.
     * Each time partitionArray() is executed, the pivot element is in its final sorted position.
     *
     * @param {number} lowIndex
     * @param {number} highIndex
     * @return {number}
     */
    const partitionArray = (lowIndex, highIndex) => {
      /**
       * Swaps two elements in array.
       * @param {number} leftIndex
       * @param {number} rightIndex
       */
      const swap = (leftIndex, rightIndex) => {
        const temp = array[leftIndex];
        array[leftIndex] = array[rightIndex];
        array[rightIndex] = temp;
      };

      const pivot = array[highIndex];
      // visitingCallback is used for time-complexity analysis.
      this.callbacks.visitingCallback(pivot);

      let partitionIndex = lowIndex;
      for (let currentIndex = lowIndex; currentIndex < highIndex; currentIndex += 1) {
        if (this.comparator.lessThan(array[currentIndex], pivot)) {
          swap(partitionIndex, currentIndex);
          partitionIndex += 1;
        }
      }

      // The element at the partitionIndex is guaranteed to be greater than or equal to pivot.
      // All elements to the left of partitionIndex are guaranteed to be less than pivot.
      // Swapping the pivot with the partitionIndex therefore places the pivot in its
      // final sorted position.
      swap(partitionIndex, highIndex);

      return partitionIndex;
    };

    // Base case is when low and high converge.
    if (inputLowIndex < inputHighIndex) {
      const partitionIndex = partitionArray(inputLowIndex, inputHighIndex);
      const RECURSIVE_CALL = true;
      this.sort(array, inputLowIndex, partitionIndex - 1, RECURSIVE_CALL);
      this.sort(array, partitionIndex + 1, inputHighIndex, RECURSIVE_CALL);
    }

    return array;
  }
}

"快速排序"的思想很简单，整个排序过程只需要三步：

1. 在数据集之中，找一个基准点
2. 建立两个数组，分别存储左边和右边的数组
3. 利用递归进行下次比较

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr; //如果数组只有一个数，就直接返回；
  }

  var num = Math.floor(arr.length / 2); //找到中间数的索引值，如果是浮点数，则向下取整

  var numValue = arr.splice(num, 1); //找到中间数的值
  var left = [];
  var right = [];

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < numValue) {
      left.push(arr[i]); //基准点的左边的数传到左边数组
    } else {
      right.push(arr[i]); //基准点的右边的数传到右边数组
    }
  }

  return quickSort(left).concat([numValue], quickSort(right)); //递归不断重复比较
}

alert(quickSort([32, 45, 37, 16, 2, 87])); //弹出“2,16,32,37,45,87”

/**
 * 快速排序
 * @param       : <Array> target数组
 * @description : 选择一个元素将数组分隔成两部分，比该元素小的放该元素前面，比该元素大放后面；
 *                然后递归快速排序，最终得到一个排序后数组
 */
module.exports.quickSort = function quickSort(target) {
  // 先定义递归终止条件
  if (target.length < 2) {
    return target;
  }

  var baseIndex = 0;
  var left = [];
  var right = [];

  for (var i = 1; i < target.length; i++) {
    if (target[i] < target[baseIndex]) {
      left.push(target[i]);
    } else {
      right.push(target[i]);
    }
  }
  left = quickSort(left);
  right = quickSort(right);
  return left.concat(target[baseIndex], right); // 递归出口
};

/**
 * 原地快速排序
 * @param       : <Array> target
 * @description : 上面的快排每次都开辟一个数组，浪费空间。常规做法是两边查找到中间，两两交换位置
 */
function _inPlaceQuickSort(target, left, right) {
  // 先定义递归终止条件
  if (left >= right) {
    return target;
  }

  var base = target[left];
  var i = left;
  var j = right;
  while (i < j) {
    while (i < j && target[j] >= base) {
      j--;
    }
    target[i] = target[j];
    while (i < j && target[i] <= base) {
      i++;
    }
    target[j] = target[i];
  }
  target[i] = base;
  // 函数副作用已经改变了传入数组，但是用显式返回看起来更清晰
  target = _inPlaceQuickSort(target, left, i - 1);
  target = _inPlaceQuickSort(target, i + 1, right);
  return target;
}
module.exports.inPlaceQuickSort = function inPlaceQuickSort(target) {
  return _inPlaceQuickSort(target, 0, target.length - 1);
};

Other

function sort(array) {
  if (array.length < 2) {
    return array;
  }

  let mid = Math.floor(array.length / 2);
  let left = array.slice(0, mid);
  let right = array.slice(mid);

  return merge(sort(left), sort(right));
}

function merge(left, right) {
  let result = [];
  let indexLeft = 0;
  let indexRight = 0;

  while (indexLeft < left.length && indexRight < right.length) {
    result.push(left[indexLeft] < right[indexRight] ? left[indexLeft++] : right[indexRight++]);
  }

  return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight));
}