【算法】排序
插入排序
1. 直接插入排序【稳定】
将待排序的记录Ri+1，插入到已排好序的记录表R0, R1 ,…., Ri中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。
如上图，将每一个数在比较之后，插入到适当的位置上。
（1）思路
比较过程中，首先第一个循环是从第1 ~ 第n-1的数进行比较，接着第二个循环将第i个数与前面的每个数进行比较。
（2）代码
function insertSort(arr) {
for (var i = 1; i < arr.length; i++) {
for (j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
//1. 使用解构赋值
[arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
/*2. 使用中间变量 var temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp;*/
}
}
}
}
（3）空间复杂度：O(1)
就地排序，没有用到单独空间，所以空间复杂度为O(1)。
（4）时间复杂度：O(2)
内外两个n次的循坏，所以时间复杂度为O(n²)。
最好的时间复杂度：O(n)。
2. 希尔排序【不稳定】
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
（1）思路
采用Knuth序列：h=h*3+1，对数组进行分组。分组后，基于直接插入排序对每个分组进行排序。
（2）代码
function shellSort(arr) {
var h = 1;
while (h <= arr.length) {
h = 3 * h + 1; //采用Knuth序列
}
for (var gap = h; gap > 0; gap = (gap - 1) / 3) {
for (var i = gap; i < arr.length; i++) {
for (var j = i; j > gap - 1; j -= gap) {
//基于直接插入排序
if (a[j] < a[j - gap]) {
[a[j - gap], a[j]] = [a[j], a[j - gap]];
}
}
}
}
}
（3）时间复杂度：O(1)
（4）时间复杂度：O(1.3)
效率比直接插入排序高的原因是：间隔大的时候，移动的次数少；间隔小的时候，移动的距离短。
选择排序
1. 直接选择排序【不稳定】
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
（1）思路
声明一个值min，将这个值指向待排序的数据元素中值最小的索引。若一次比较完，min不等于当前待排序元素的第一个索引，则将min索引的值与第一个值进行交换。
（2）代码
function selectSort(arr) {
for (var i = 0; i < arr.length - 1; i++) {
var min = i;
for (var j = i + 1; j < arr.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if (min !== i) {
[a[i], a[min]] = [a[min], a[i]];
}
}
}
（3）空间复杂度：O(1)
（4）时间复杂度：O(n2)
2. 堆排序【不稳定】
（1）创建堆（最大/小堆）
步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。
下图为创建最大堆。
（2）堆排序
- 步骤：
① 对一组待排序的记录，按堆的定义建立最大堆；
② 将堆顶记录和最后一个记录交换位置，则前n-1个记录是无序的，而最后一个记录是有序的；
③ 堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆，然后将堆顶记录和倒数第二个记录交换位置，即将整个序列中次小关键字值的记录调整(排除)出无序区；
④ 重复上述步骤，直到全部记录排好序为止。 - 堆的调整思想——筛选
① 输出堆顶元素之后，以堆中最后一个元素替代之；
②然后将根结点值与左、右子树的根结点值进行比较，并与其中大者进行交换；
③重复上述操作，直到是叶子结点或其关键字值大于等于左、右子树的关键字的值，将得到新的堆。
下图为堆排序图示：
（3）空间复杂度：O(1)
（4）时间复杂度：O(nlog2n)。
交换排序
1. 冒泡排序【稳定】
（1）思路
首先，数组n个元素，前后两个元素两两比较，大的元素往后移，一趟排序后，最大的元素排在最后的位置。接着，对n-1个元素进行相同的步骤。以此类推，直至排序完成。
（2）代码
代码中，设置标志量flag，标记一趟冒泡如果没有交换，则已经排好序，提前结束循环。
function bubbleSort(arr) {
var flag = 1;
for (i = arr.length - 1; i > 0 && flag === 1; i++) {
flag = 0;
for (j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
flag = 1;
[a[j], a[j + 1]] = [a[j + 1], a[j]];
}
}
}
}
（3）空间复杂度：O(1)
（4）时间复杂度：O(n2)
最好时间复杂度：O(n)
（ 初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动数据元素。【使用标志量flag判断】）
2. 快速排序【不稳定】
（1）思路
从序列的两端交替扫描各个记录，将关键字小于基准关键字的记录依次放置到序列的前边；而将关键字大于基准关键字的记录从序列的最后端起，依次放置到序列的后边，直到扫描完所有的记录。
（2）代码
function quickSort(arr, low, high) {
var i = low,
j = high,
temp = arr[i];
while (i < j) {
if (i < j && temp <= arr[j]) j--;
if (i < j) {
arr[i] = arr[j];
}
if (i < j && arr[i] <= temp) i++;
if (i < j) {
arr[j] = arr[i];
}
}
arr[i] = temp;
if (low < i) quickSort(arr, low, i - 1);
if (i < high) quickSort(arr, j + 1, high);
}
注意：调用时，第2、3个参数分别传入0、arr.length-1。
（3）空间复杂度：O(log2n)
（4）时间复杂度：O(nlog2n)
归并排序【稳定】
（1）思路
是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
首先，分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。
接着，治阶段，我们需要将两个已经有序的子序列合并成一个有序序列
（2）代码
function mergeSort(arr, left, right) {
if (left < right) {
let mid = parseInt((left + right) / 2);
mergeSort(arr, left, mid); //左边归并排序
mergeSort(arr, mid + 1, right); //右边归并排序
merge(arr, left, mid, right); //将两个有序子数组合并操作
}
}
function merge(arr, left, mid, right) {
let temp = [];
let len = 0;
let i = left,
j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[len++] = arr[i++];
} else {
temp[len++] = arr[j++];
}
}
while (i <= mid) {
temp[len++] = arr[i++];
}
while (j <= right) {
temp[len++] = arr[j++];
}
let t = 0;
while (t < len) {
arr[left++] = temp[t++];
}
}
注意：调用时，第2、3个参数分别传入0、arr.length-1。
（3）空间复杂度：O(log2n)
（4）时间复杂度：O(nlog2n)
基数（桶）排序【稳定】
（1）思路
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
（2）代码
function radixSort(arr, maxDigit) {
var counter = [];
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for (var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if (counter[bucket] == null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for (var j = 0; j < counter.length; j++) {
var value = null;
if (counter[j] != null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}
注意：第二个参数是待比较元素中的最大数位，在传入参数前，先算出最大数位，使用下列代码算出：
var dight = 0;
for (var j = 0; j < a.length; j++) {
var t = a[j].toString();
if (dight < t.length) dight = t.length;
}
（3）空间复杂度：O(n)
（4）时间复杂度：O(mn)
m为最大数位。
