摘自wiki和http://bubkoo.com/2014/01/17/sort-algorithm/archives/
什么是算法
https://zh.wikipedia.org/zh-hans/%E7%AE%97%E6%B3%95
排序演示 https://visualgo.net/zh/sorting
以下是高德纳在他的著作《计算机程序设计艺术》里对算法的特征归纳：
输入：一个算法必须有零个或以上输入量。
输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望，通常要求实际运行结果是确定的。
有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现
什么是数据结构
就是数据的结构。
一般来说是这样的：
我们要解决一个跟数据相关的问题
分析这个问题，想出对应的数据结构
分析数据结构，想出算法
数据结构和算法是互相依存、不可分开的
你学习完排序算法，就能了解常见的数据结构
大分类
分治法：把一个问题分区成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。
动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。
贪婪算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。
线性规划法：见词条。
简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。
我们前端主要使用分治法——分而治之。
快速排序
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
从数列中挑出一个元素，称为"基准"（pivot），
重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
Array.prototype.quick_sort = function() {
var len = this.length;
if (len <= 1)
return this.slice(0);
var left = [];
var right = [];
var mid = [this[0]];
for (var i = 1; i < len; i++)
if (this[i] < mid[0])
left.push(this[i]);
else
right.push(this[i]);
return left.quick_sort().concat(mid.concat(right.quick_sort()));
};
var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quick_sort();
for (i = 0; i < arr.length; i++)
document.body.innerHTML += arr[i] + " ";
document.body.innerHTML += "<br>";
冒泡排序
冒泡排序算法的运作如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
Array.prototype.quick_sort = function() {
var len = this.length;
if (len <= 1)
return this.slice(0);
var left = [];
var right = [];
var mid = [this[0]];
for (var i = 1; i < len; i++)
if (this[i] < mid[0])
left.push(this[i]);
else
right.push(this[i]);
return left.quick_sort().concat(mid.concat(right.quick_sort()));
};
var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quick_sort();
for (i = 0; i < arr.length; i++)
document.body.innerHTML += arr[i] + " ";
document.body.innerHTML += "<br>";
插入排序
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
function insertionSort(array) {
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
var length = array.length,
i,
j;
for (i = 1; i < length; i++) {
for (j = i; j > 0; j--) {
if (array[j - 1] > array[j]) {
swap(array, j - 1, j);
} else {
break;
}
}
}
return array;
}
下面这种方式可以减少交换次数：
function insertionSort(array) {
var length = array.length,
i,
j,
temp;
for (i = 1; i < length; i++) {
temp = array[i];
for (j = i; j >= 0; j--) {
if (array[j - 1] > temp) {
array[j] = array[j - 1];
} else {
array[j] = temp;
break;
}
}
}
return array;
}
桶排序
设置一个定量的数组当作空桶子。
寻访序列，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的序列中。
首先用最笨的方法，每一个桶只能放相同的数字，最大桶的数量为数组中的正数最大值加上负数最小值的绝对值。
function bucketSort(array) {
var bucket = [], // 正数桶
negativeBucket = [], // 负数桶
result = [],
l = array.length,
i,
j,
k,
abs;
// 入桶
for (i = 0; i < l; i++) {
if (array[i] < 0) {
abs = Math.abs(array[i]);
if (!negativeBucket[abs]) {
negativeBucket[abs] = [];
}
negativeBucket[abs].push(array[i]);
} else {
if (!bucket[array[i]]) {
bucket[array[i]] = [];
}
bucket[array[i]].push(array[i]);
}
}
// 出桶
l = negativeBucket.length;
for (i = l - 1; i >= 0; i--) {
if (negativeBucket[i]) {
k = negativeBucket[i].length;
for (j = 0; j < k; j++) {
result.push(negativeBucket[i][j]);
}
}
}
l = bucket.length;
for (i = 0; i < l; i++) {
if (bucket[i]) {
k = bucket[i].length;
for (j = 0; j < k; j++) {
result.push(bucket[i][j]);
}
}
}
return result;
}
下面这种方式就是文中举例分析的那样，每个桶存放一定范围的数字，用 step 参数来设置该范围，取 step 为 1 就退化成前一种实现方式。关键部位代码有注释，慢慢看，逻辑稍微有点复杂。
/*
* @array 将要排序的数组
*
* @step 划分桶的步长，比如 step = 5，表示每个桶存放的数字的范围是 5，像 -4<sub>1、0</sub>5、6~11
*/
function bucketSort(array, step) {
var result = [],
bucket = [],
bucketCount,
l = array.length,
i,
j,
k,
s,
max = array[0],
min = array[0],
temp;
for (i = 1; i < l; i++) {
if (array[i] > max) {
max = array[i]
}
if (array[i] < min) {
min = array[i];
}
}
min = min - 1;
bucketCount = Math.ceil((max - min) / step); // 需要桶的数量
for (i = 0; i < l; i++) {
temp = array[i];
for (j = 0; j < bucketCount; j++) {
if (temp > (min + step * j) && temp <= (min + step * (j + 1))) { // 判断放入哪个桶
if (!bucket[j]) {
bucket[j] = [];
}
// 通过插入排序将数字插入到桶中的合适位置
s = bucket[j].length;
if (s > 0) {
for (k = s - 1; k >= 0; k--) {
if (bucket[j][k] > temp) {
bucket[j][k + 1] = bucket[j][k];
} else {
break;
}
}
bucket[j][k + 1] = temp;
} else {
bucket[j].push(temp);
}
}
}
}
for (i = 0; i < bucketCount; i++) { // 循环取出桶中数据
if (bucket[i]) {
k = bucket[i].length;
for (j = 0; j < k; j++) {
result.push(bucket[i][j]);
}
}
}
return result;
}
