算法复杂度
不是科班生的我，第一次看见时间复杂度之类的名词表示很懵逼，所以就找了网上的资料补习了下：
- 时间复杂度：是指执行算法所需要的计算工作量
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量
- 排序算法稳定性： 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
这里不详细说
参考：算法的时间复杂度和空间复杂度-总结、理解排序算法的稳定性、算法和算法的复杂度
排序算法
排序算法
名词解释：
n：数据规模
k：“桶”的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
下面的算法实现升序
冒泡排序
顾名思义，从第一个开始比较相邻的两个，小的数网上冒。
实现
function bubleSort (arr) {
var len = arr.length;
var temp;
for (var i=0; i<len-1; i++) {
for(var j=0; j<len-1-i; j++) {
//前一个大于后一个则交换位置
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr
}
选择排序
假设第一个最小， 往后寻找比它小的，记下其index，一轮结束后将index上的数与开始假定的数交换位置。
实现
function selectionSort (arr) {
var len = arr.length;
var minIndex, temp;
for (var i=0; i<len-1; i++) {
minIndex = i;
for (var j=i+1; j<len; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
插入排序
直接插入排序
打扑克的同志应该比较好理解。假设第一个元素是已经排序好的，将后一个元素提取出来，往前依次比较，比自己大的数往后挪，插入到第一次遇见比自己小的元素后面，组成一个新的序列。
实现
function insertionSort (arr) {
var len = arr.length;
var current, preIndex;
for (var i=1; i<len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex>=0 && current < arr[preIndex]) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr
}
希尔排序
实质为分组插入排序。为了方便理解，借用网上某哥的图，参考链接在下文。
希尔排序
因为是在已经分组排序过的基础上进行插入排序，所以效率高。
实现
//因为核心是插入排序，所以我们改造直接插入排序
function directInsertionSort(arr, gap) {
var len = arr.length;
var current, preIndex;
for (var i=gap; i<len; i++) {
current = arr[gap];
preIndex = i - gap;
while (preIndex>=0 && arr[preIndex] > current) {
arr[preIndex+gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex+gap] = current;
}
return arr;
}
//编写希尔排序函数
function shellSort (arr) {
var len = arr.length;
var gap = 1;
//设置gap（希尔增量），这里我们给出比较常用的h值为h = 3 * h + 1
while (gap < len/3) {
gap = gap * 3 + 1;
}
for (gap; gap>0; gap = Math.floor(gap/3)) {
directInsertSort(arr, gap);
}
return arr;
}
遇见的问题，关于参数的传递：函数参数的传递可以分为按值传递和引用传递。
步长序列可以看一下wiki
折半插入排序
类似直接插入，后一个元素（拿来比较的元素）与已排序的中间值m = (i-1) >> 1(位移运算，相当于Math.floor((i-1)/2))进行比较,如果i上的值大于m上的值，则与高半区折半比较,最终将比i上值高的区域往后移，将i上的值插入。如
arr = [2, 6, 7, 6, 8]
//前三个是已经排好的。
//range = [low, high] = [0, 2], i = 3, current = arr[i]
// m = 1, arr[i] >= arr[m], rang = [2, 2]
// m = 2, arr[i] < arr[m]
// 变换位置 ==> arr = [2, 6, 6, 7, 8]
...
...
实现
function binaryInsertionSort (arr) {
var len = arr.length;
var low, height, current, m;
for (var i=1; i<len; i++) {
current = arr[i];
low = 0;
height = i-1;
while (low <= height) {
m = (low + height) >> 1;
if (current >= arr[m]) {// = 是为了保证稳定性
low = m + 1;
}else {
height = m - 1;
}
}
for (var j=i; j>low; j--) {
arr[j] = arr[j-1];
}
arr[low] = current;
}
return arr;
}
归并排序
采取分而治之的思想。递归分组、比较产生两个已排序序列，再依次比较两组开头元素，较小的元素放入申请的新数组中。
归并函数可以通过递归、迭代实现。
递归
主要做的两件事就是分解、合并(下面并不是按照执行顺序，只是思路)：
[3, 5, 6, 2, 9]
--------------------------------------
分： [3, 5] [6, 2, 9]
[3] [5] [6] [2, 9]
[2] [9]
--------------------------------------
合： [2, 9]
[3, 5] [2, 6, 9]
[2, 3, 5, 6, 9]
实现
function merge (left, right) {
var result = [];
while (left.length && right.length) {
var item = left[0] <= right[0] ? left.shift() : right.shift();
result.push(item);
}
return result.concat(left.length ? left : right);
}
function mergeSort (arr) {
var len = arr.length;
if (len === 1) {
return arr;
}
var m = len >> 1;
var left = arr.slice(0, m);
var right = arr.slice(m);
return merge(mergeSort(left), mergeSort(right))
}
递归可能会造成堆栈溢出的问题。
迭代
主要做的两件事就是分解、合并(下面并不是按照执行顺序，只是思路)：
[3, 5, 6, 2, 9]
--------------------------------------
分： [3] [5] [6] [2] [9]
--------------------------------------
合： [3, 5] [2, 6] [9]
[2, 3, 5, 6] [9]
[2, 3, 5, 6, 9]
实现
function merge (left, right) {
var result = [];
while (left.length && right.length) {
var item = left[0] <= right[0] ? left.shift() : right.shift();
result.push(item);
}
return result.concat(left.length ? left : right);
}
function mergeSort (arr) {
var len = arr.length;
var result = [];
//分组，每组有i个元素
for (var i=1; i<=len; i*=2) {
//比较相邻两组，有一组剩余就退出
for (var j=0; j+i<len; j+=2*i) {
left = arr.slice(j, j+i);
right = arr.slice(j+i, j+2*i);
result = merge(left, right);
arr.splice(j, 2*i, ...result)
}
}
return arr
}
快速排序
快速排序是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
步骤：选择一个元素作为基准，下面选择第一个，依次比较后面的元素，将小于基准的元素放在基准的左边，剩余放右边。形成左右两个分区，再递归按之前的步骤排序。
实现
function swap (arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function partition (arr, left, right) {
var pivot = left;
var index = left + 1;
for (var i=index; i<=right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, index, i);
index++;
}
}
swap(arr, index-1, pivot);
return index-1
}
function quickSort (arr, left, right) {
var len = arr.length;
var partitionIndex;
left = typeof left === 'number' ? left : 0;
right = typeof right === 'number' ? right : len-1;
if (left < right) {
partitionIndex = partition (arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
快速排序排序效率非常高. 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常, 平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高.
Chrome的v8引擎为了高效排序, 在排序数据超过了10条时, 便会采用快速排序. 对于10条及以下的数据采用的便是插入排序.
