工夫复杂度 & 空间复杂度
由图可知，工夫复杂度应尽力管制在 O(nlogn) 以下。
空间复杂度，就是对一个算法在运行过程中长期占用存储空间大小的度量
js 排序依据它们的个性，能够大抵分为两种类型：比拟类排序和非比拟类排序。
- 比拟类排序：通过比拟来决定元素间的绝对秩序，其工夫复杂度不能冲破 O(nlogn)，因而也称为非线性工夫比拟类排序。
- 非比拟类排序：不通过比拟来决定元素间的绝对秩序，它能够冲破基于比拟排序的工夫下界，以线性工夫运行，因而也称为线性工夫非比拟类排序。
比拟类排序
-
替换排序
- 冒泡排序
- 疾速排序
- 插入排序
-
抉择排序
- 一般抉择排序
- 堆排序
- 归并排序
冒泡排序
接触的第一个排序算法, 逻辑比较简单
let testArr = [1, 3, 5, 3, 4, 54, 2423, 321, 4, 87];
function bubbleSort(arr) {
const len = arr.length
if (len < 2) return arr;
for (let i = 0; i < len; i++) {for (let j = 0; j < i; j++) {if (arr[j] > arr[i]) {const tmp = arr[j];
arr[j] = arr[i]
arr[i] = tmp
}
}
}
return arr
}疾速排序
疾速排序的根本思维是通过一趟排序，将待排记录分隔成独立的两局部，其中一部分记录的关键字均比另一部分的关键字小，则能够别离对这两局部记录持续进行排序，以达到整个序列有序。
最次要的思路是从数列中挑出一个元素，称为“基准”（pivot）；而后从新排序数列，所有元素比基准值小的摆放在基准后面、比基准值大的摆在基准的前面；在这个辨别搞定之后，该基准就处于数列的两头地位；而后把小于基准值元素的子数列（left）和大于基准值元素的子数列（right）递归地调用 quick 办法排序实现，这就是快排的思路。
function quickSort(array) {let quick = function (arr) {if (arr.length <= 1) return arr;
// Math.floor() 返回小于或等于一个给定数字的最大整数
// 获取数组两头位数索引值
const index = Math.floor(arr.length >> 1)
// 取出索引值
const pivot = arr.splice(index, 1)[0]
const left = []
const right = []
for (let i = 0; i < arr.length; i++) {if (arr[i] > pivot) {right.push(arr[i])
} else if (arr[i] <= pivot) {left.push(arr[i])
}
}
return quick(left).concat([pivot], quick(right))
}
const result = quick(array)
return result
}插入排序
一种简略直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应地位并插入，从而达到排序的成果。
function insertSort(array) {
const len = array.length
let current // 以后值
let prev // 前值索引
// 从 1 开始，拿到以后值 current，和前值比拟，如果前值大于以后值，就进行替换
for (let i = 1; i < len; i++) {
// 记录下以后值
current = array[i]
prev = i - 1;
while (prev >= 0 && array[prev] > current) {array[prev + 1] = array[prev]
prev--
}
array[prev + 1] = current
}
return array
}抉择排序
抉择排序是一种简略直观的排序算法。它的工作原理是，首先将最小的元素寄存在序列的起始地位，再从残余未排序元素中持续寻找最小元素，而后放到已排序的序列前面……以此类推，直到所有元素均排序结束。最稳固的排序算法之一，因为无论什么数据进去都是 O(n 平方) 的工夫复杂度，所以用到它的时候，数据规模越小越好
function selectSort(array) {
const len = array.length
let tmp;
let minIdx;
for (let i = 0; i < len - 1; i++) {
minIdx = i;
for (let j = i + 1; j < len; j++) {if (array[j] < array[minIdx]) {minIdx = j}
}
tmp = array[i]
array[i] = array[minIdx]
array[minIdx] = tmp
}
return array
}堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法。沉积是一个近似齐全二叉树的构造，并同时满足沉积的性质，即子结点的键值或索引总是小于（或者大于）它的父节点。堆的底层实际上就是一棵齐全二叉树，能够用数组实现。根节点最大的堆叫作大根堆，根节点最小的堆叫作小根堆。
外围点
- 堆排序最外围的点就在于排序前先建堆；
-
因为堆其实就是齐全二叉树，如果父节点的序号为 n，那么叶子节点的序号就别离是 2n 和 2n+1
function heapSort(arr) { let len = arr.length // 构建堆 function buildMaxHeap(arr) { // 最初一个有子节点开始构建堆 for (let i = Math.floor(len / 2 - 1); i >= 0; i--) { // 对每一个非叶子节点进行堆调整 maxHeapify(arr, i) } } function swap(arr, i, j) {[arr[j], arr[i]] = [arr[i], arr[j]] } function maxHeapify(arr, i) { let left = 2 * i + 1; let right = 2 * i + 2 // i 为该子树的根节点 let largest = i; if (left < len && arr[left] > arr[largest]) {largest = left} if (right < len && arr[right] > arr[largest]) {largest = right} // 当下面两个判断有一个失效时 if (largest !== i) {swap(arr, i, largest) // 替换之后，arr[i] 下沉，持续进行调整 maxHeapify(arr, largest) } } buildMaxHeap(arr) for (let i = arr.length - 1; i > 0; i--) {swap(arr, 0, i) len--; maxHeapify(arr, 0) } return arr }归并排序
归并排序是建设在归并操作上的一种无效的排序算法，该算法是采纳分治法的一个十分典型的利用。将已有序的子序列合并，失去齐全有序的序列；先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
function mergeSort(arr) {const merge = (right, left) => {const result = [] let idxLeft = 0 let idxRight = 0 while (idxLeft < left.length && idxRight < right.length) {if (left[idxLeft] < right[idxRight]) {result.push(left[idxLeft++]) } else {result.push(right[idxRight++]) } } while (idxLeft < left.length) {result.push(left[idxLeft++]) } while (idxRight < right[idxRight]) {result.push(right[idxRight++]) } return result } const mergeSort = arr => {if (arr.length === 1) return arr const mid = Math.floor(arr.length / 2) const left = arr.slice(0, mid) const right = arr.slice(mid, arr.length) return merge(mergeSort(left), mergeSort(right)) } return mergeSort(arr) }归并排序是一种稳固的排序办法，和抉择排序一样，归并排序的性能不受输出数据的影响，但体现比抉择排序好得多，因为始终都是 O(nlogn) 的工夫复杂度。而代价是须要额定的内存空间。
工夫复杂度，空间复杂度比拟
Array 中 Sort 办法
arr.sort([compareFunction])
compareFunction 用来指定按某种程序进行排列的函数，如果省略不写，元素依照转换为字符串的各个字符的 Unicode 位点进行排序
const months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();
console.log(months) // ['Dec', 'Feb', 'Jan', 'March']
const testArr = [1, 3, 5, 6, 3, 4, 54, 2423, 321, 4, 87];
testArr.sort();
console.log(testArr) // [1, 2423, 3, 3, 321, 4, 4, 5, 54, 6, 87]如果指明了 compareFunction 参数，那么数组会依照调用该函数的返回值排序，即 a 和 b 是两个将要被比拟的元素：
- 如果 compareFunction（a, b）小于 0，那么 a 会被排列到 b 之前；
- 如果 compareFunction（a, b）等于 0，a 和 b 的绝对地位不变；
- 如果 compareFunction（a, b）大于 0，b 会被排列到 a 之前。
底层 sort 源码剖析
- 当 n<=10 时，采纳插入排序；
- 当 n>10 时，采纳三路疾速排序；
- 10<n <=1000，采纳中位数作为哨兵元素；
- n>1000，每隔 200~215 个元素挑出一个元素，放到一个新数组中，而后对它排序，找到两头地位的数，以此作为中位数。
1. 为什么元素个数少的时候要采纳插入排序？
尽管插入排序实践上是均匀工夫复杂度为 O(n^2) 的算法，疾速排序是一个均匀 O(nlogn) 级别的算法。然而别忘了，这只是实践上均匀的工夫复杂度估算，然而它们也有最好的工夫复杂度状况，而插入排序在最好的状况下工夫复杂度是 O(n)。
在理论状况中两者的算法复杂度后面都会有一个系数，当 n 足够小的时候，疾速排序 nlogn 的劣势会越来越小。假使插入排序的 n 足够小，那么就会超过快排。而事实上正是如此，插入排序通过优化当前，对于小数据集的排序会有十分优越的性能，很多时候甚至会超过快排。因而，对于很小的数据量，利用插入排序是一个十分不错的抉择。
2. 为什么要花这么大的力量抉择哨兵元素？
因为疾速排序的性能瓶颈在于递归的深度，最坏的状况是每次的哨兵都是最小元素或者最大元素，那么进行 partition（一边是小于哨兵的元素，另一边是大于哨兵的元素）时，就会有一边是空的。如果这么排下去，递归的层数就达到了 n , 而每一层的复杂度是 O(n)，因而快排这时候会进化成 O(n^2) 级别。
这种状况是要尽力防止的，那么如何来防止？就是让哨兵元素尽可能地处于数组的两头地位，让最大或者最小的状况尽可能少。
function ArraySort(comparefn) {CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");
var array = TO_OBJECT(this);
var length = TO_LENGTH(array.length);
return InnerArraySort(array, length, comparefn);
}
function InnerArraySort(array, length, comparefn) {
// 比拟函数未传入
if (!IS_CALLABLE(comparefn)) {comparefn = function (x, y) {if (x === y) return 0;
if (% _IsSmi(x) && % _IsSmi(y)) {return %SmiLexicographicCompare(x, y);
}
x = TO_STRING(x);
y = TO_STRING(y);
if (x == y) return 0;
else return x < y ? -1 : 1;
};
}
function InsertionSort(a, from, to) {
// 插入排序
for (var i = from + 1; i < to; i++) {var element = a[i];
for (var j = i - 1; j >= from; j--) {var tmp = a[j];
var order = comparefn(tmp, element);
if (order > 0) {a[j + 1] = tmp;
} else {break;}
}
a[j + 1] = element;
}
}
function GetThirdIndex(a, from, to) { // 元素个数大于 1000 时寻找哨兵元素
var t_array = new InternalArray();
var increment = 200 + ((to - from) & 15);
var j = 0;
from += 1;
to -= 1;
for (var i = from; i < to; i += increment) {t_array[j] = [i, a[i]];
j++;
}
t_array.sort(function (a, b) {return comparefn(a[1], b[1]);
});
var third_index = t_array[t_array.length >> 1][0];
return third_index;
}
function QuickSort(a, from, to) { // 疾速排序实现
// 哨兵地位
var third_index = 0;
while (true) {if (to - from <= 10) {InsertionSort(a, from, to); // 数据量小，应用插入排序，速度较快
return;
}
if (to - from > 1000) {third_index = GetThirdIndex(a, from, to);
} else {
// 小于 1000 间接取中点
third_index = from + ((to - from) >> 1);
}
// 上面开始快排
var v0 = a[from];
var v1 = a[to - 1];
var v2 = a[third_index];
var c01 = comparefn(v0, v1);
if (c01 > 0) {
var tmp = v0;
v0 = v1;
v1 = tmp;
}
var c02 = comparefn(v0, v2);
if (c02 >= 0) {
var tmp = v0;
v0 = v2;
v2 = v1;
v1 = tmp;
} else {var c12 = comparefn(v1, v2);
if (c12 > 0) {
var tmp = v1;
v1 = v2;
v2 = tmp;
}
}
a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1;
var high_start = to - 1;
a[third_index] = a[low_end];
a[low_end] = pivot;
partition: for (var i = low_end + 1; i < high_start; i++) {var element = a[i];
var order = comparefn(element, pivot);
if (order < 0) {a[i] = a[low_end];
a[low_end] = element;
low_end++;
} else if (order > 0) {
do {
high_start--;
if (high_start == i) break partition;
var top_elem = a[high_start];
order = comparefn(top_elem, pivot);
} while (order > 0);
a[i] = a[high_start];
a[high_start] = element;
if (order < 0) {element = a[i];
a[i] = a[low_end];
a[low_end] = element;
low_end++;
}
}
}
// 快排的外围思路，递归调用疾速排序办法
if (to - high_start < low_end - from) {QuickSort(a, high_start, to);
to = low_end;
} else {QuickSort(a, from, low_end);
from = high_start;
}
}
}
} 从下面的源码剖析来看，当数据量小于 10 的时候用插入排序；当数据量大于 10 之后采纳三路快排；当数据量为 10~1000 时候间接采纳中位数为哨兵元素；当数据量大于 1000 的时候就开始寻找哨兵元素。
疾速排序是不稳固排序，均匀和最好工夫复杂度都是 O(nlogn), 最差是 O(n^2)，空间复杂度是 O(nlogn)
插入排序是稳固排序，最好时时 O(n), 均匀和最差是 O(n^2), 空间复杂度是 O(1)