排序是非常基础、重要的算法，它将若干数据依照特定的顺序进行排列。如果排序的对象是数值，那么按数值递增或递减的顺序进行排序；如果排序的对象是字符串，那么按照字典顺序进行排序。由于数据排序之后能够利用二分查找算法提高查找的效率，因此很多数据都是排序之后再存储的。
冒泡排序 #
- 每次遍历数组时，两两对比并调整顺序，遍历完可以得到一个最大的在数组结尾。
- 继续下一次遍历，最后得到一个第二大的在倒数第二个位置。
- 以此类推。
function mopoSort(nums) {
for (let i = 0; i < nums.length; i ++) {
for (let j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j+1]) {
let temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
return nums
}
时间复杂度 $O(n^2)$
空间复杂度 $O(1)$
选择排序 #
- 第一次从待排序的数组中选出最小的一个元素放到起始位置。
- 第二次从剩余未排序的元素中寻找最小元素放到已排序的序列末尾。
- 以此类推。
function selectSort(nums) {
for (let i = 0; i < nums.length; i++) {
let min = i;
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[min]) {
min = j;
}
}
if (min !== i) {
let temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
}
}
return nums
}
时间复杂度 $O(n^2)$
空间复杂度 $O(1)$
插入排序 #
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。
在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
function insertionSort(nums) {
for (let i = 1; i < nums.length; i++) {
let temp = nums[i];
let j = i - 1;
while (j >= 0 && nums[j] > temp) {
nums[j+1] = nums[j];
j --;
}
nums[j+1] = temp;
}
return nums
}
时间复杂度 $O(n^2)$
空间复杂度 $O(1)$
希尔排序 #
希尔排序是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序（Diminishing Increment Sort）。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
希尔排序非常适合已经“基本有序”的数组排序，属于非稳定排序算法。刚开始看比较难理解，可以参考 B 站这个视频多看几遍就 OK 了。
function shellSort(nums) {
let gap = Math.floor(nums.length / 2);
while (gap > 0) {
for (let i = gap; i < nums.length; i++) {
let temp = nums[i];
let j = i - gap;
while (j >= 0 && nums[j] > temp) {
nums[j+gap] = nums[j];
j -= gap;
}
nums[j+gap] = temp;
}
gap = Math.floor(gap / 2);
}
return nums
}
时间复杂度最好是 $O(n^{3/2})$，最坏是 $O(n^2)$
空间复杂度 $O(1)$
堆排序 #
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
- 大顶堆：每个节点的值都大于或等于其子节点的值；
- 小顶堆：每个节点的值都小于或等于其子节点的值；
如果是排序，求升序用大顶堆，求降序用小顶堆。一般的 top K 问题，就可以用大顶堆或小顶堆来实现：
- 最大的 K 个：小顶堆
- 最小的 K 个：大顶堆
为什么升序却使用最大堆？
堆排序的核心逻辑就是利用最大堆中的根结点是最大值的特性，构建完堆结构后，在排序中需要再加一步：把根结点和最后一个元素交换位置，这样末尾就是最大元素了。然后再将剩下的元素重新构建最大堆，再重复交换根结点和末尾元素就可以了。
function heapSort(nums) {
function heapify(nums, start, end) {
let root = start;
while (2 * root + 1 <= end) {
let child = 2 * root + 1;
let swap = root;
if (nums[swap] < nums[child]) {
swap = child;
}
if (child + 1 <= end && nums[swap] < nums[child+1]) {
swap = child + 1;
}
if (swap === root) {
break;
}
let temp = nums[root];
nums[root] = nums[swap];
nums[swap] = temp;
}
}
for (let i = Math.floor(nums.length / 2); i >= 0; i--) {
heapify(nums, i, nums.length - 1);
}
for (let i = nums.length - 1; i > 0; i--) {
let temp = nums[0];
nums[0] = nums[i];
nums[i] = temp;
heapify(nums, 0, i - 1);
}
return nums
}
堆排序的平均时间复杂度为 $ O(nlog{n}) $。
归并排序 #
是分治思想的算法应用，特别适用于合并已经排好序的数组（比如 88. 合并两个有序数组），也特别适合使用多线程排序。
合并两个有序数组 #
合并两个有序数组是归并排序中归并操作外最核心的步骤。算法步骤如下：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
归并思想 #
- 分解（Divide）
- 解决（Conquer）
- 合并（Combine）
实现方法 #
归并的实现可以分为自顶向下（top-down）的递归或者自底向上（bottom-up）的迭代，先逐步将子数组一分为二，对于后再进行合并，合并时也可以分为原地（in-place）合并和非原地（out-place）合并，所以一共有四种实现方法。
自顶向下 - 非原地归并 #
function mergeSort(nums) {
function merge(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) {
result.push(left.shift());
}
while (right.length) {
result.push(right.shift());
}
return result;
}
if (nums.length < 2) {
return nums;
}
let middle = Math.floor(nums.length / 2);
let left = mergeSort(nums.slice(0, middle));
let right = mergeSort(nums.slice(middle));
return merge(left, right);
}
自顶向下 - 原地归并 #
原地归并需要通过一个原地旋转交换的算法（也叫手摇算法、内存反转算法、三重反转算法）。
自底向上 - 非原地归并 #
自底向上 - 原地归并 #
快速排序 #
快速排序也是采用分治思想的一种排序方法。
推导思路可参考 https://mp.weixin.qq.com/s/SXa2xjMALDy9iYbyn3Onqg
“快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历”1，体会下。
递归实现 #
核心思想
- 先通过“分区”得到一个可以将数组分成两个子数组的索引。
- 然后通过递归对子数组再次进行“分区”，直到最后
start===end，说明 nums 已经排序完毕。
function quickSort(nums) {
function partition(nums, start, end) {
let pivot = nums[end];
let i = start;
for (let j = start; j < end; j++) {
if (nums[j] <= pivot) {
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
}
}
nums[end] = nums[i];
nums[i] = pivot;
return i;
}
function sort(nums, start, end) {
if (start >= end) {
return;
}
let pivot = partition(nums, start, end);
sort(nums, start, pivot - 1);
sort(nums, pivot + 1, end);
}
sort(nums, 0, nums.length - 1);
return nums;
}
非递归实现 #
非递归就是将递归改为循环和栈的方式，自己控制入栈和出栈。
function quickSortStack(nums) {
function sort(nums, start, end) {
if (start >= end) {
return;
}
let stack = [[start, end]];
while (stack.length) {
let [left, right] = stack.pop();
if (left >= right) {
continue;
}
let pivot = partition(nums, left, right);
stack.push([left, pivot - 1]);
stack.push([pivot + 1, right]);
}
}
function partition(nums, start, end) {
let pivot = nums[end];
let i = start;
for (let j = start; j < end; j++) {
if (nums[j] <= pivot) {
let temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
}
}
nums[end] = nums[i];
nums[i] = pivot;
return i;
}
sort(nums, 0, nums.length - 1);
return nums;
}
复杂度 #
快速排序是不稳定的排序算法，最好情况的时间复杂度为 $ O(nlogn) $，最坏 $ O(n^2) $ 。当划分的两个子数组长度其中一直有一个为 0 时，就是最坏算法，此时相当于插入排序。
桶排序 #
桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 $O(n)$。但桶排序并不是比较排序，他不受到 $O(nlogn)$ 下限的影响。
function bucketSort(nums) {
let max = Math.max(...nums);
let min = Math.min(...nums);
let bucket = new Array(max - min + 1).fill(0);
for (let i = 0; i < nums.length; i++) {
bucket[nums[i] - min]++;
}
let i = 0;
for (let num = min; num <= max; num++) {
while (bucket[num - min] > 0) {
nums[i++] = num;
bucket[num - min]--;
}
}
return nums;
}
时间复杂度 $O(n)$
空间复杂度 $O(n)$
计数排序 #
计数排序的基本思想是先统计数组中每个整数在数组中出现的次数，然后按照从小到大的顺序将每个整数按照它出现的次数填到数组中。如果数组长度为 n，整数范围（数组中最大整数与最小整数的差值）为 k，对于 k 远小于 n 的场景，计数排序的时间复杂度优于其他基于比较的排序算法（如归并排序，快速排序）。
计数排序本质上是一种特殊的桶排序，当桶的个数最大的时候，就是计数排序。
function sort(nums) {
let min = Infinity;
let max = - Infinity;
for (let i = 0; i < nums.length; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
let counts = new Array(nums.length).fill(0);
for (let i = 0; i < nums.length; i++) {
counts[nums[i] - min] ++
}
let i = 0
for (let num = min; num <= max; num++) {
while (counts[num-min] > 0) {
nums[i++] = num;
counts[num-min] --;
}
}
return nums
}
当整数范围 k 较小时，无论是空间复杂度还是时间复杂度来看计数排序都是非常高效的算法。当 k 很大时，效果就不如其他算法了。
基数排序 #
基数排序也是一种桶排序。 桶排序是按值区间划分桶，基数排序是按数位来划分；基数排序可以看做是多轮桶排序，每个数位上都进行一轮桶排序。 当用最大值作为基数时，基数排序就退化成了计数排序。
function radixSort(nums) {
let max = Math.max(...nums);
let radix = Math.floor(Math.log10(max)) + 1;
for (let i = 0; i < radix; i++) {
let bucket = new Array(10).fill(0);
for (let j = 0; j < nums.length; j++) {
let digit = Math.floor((nums[j] % Math.pow(10, i + 1)) / Math.pow(10, i));
bucket[digit]++;
}
let i = 0;
for (let num = 0; num < 10; num++) {
while (bucket[num] > 0) {
nums[i++] = num;
bucket[num]--;
}
}
}
return nums;
}