什么是算法？《数据结构和算法分析》（推荐）
高纳德在《计算机程序设计艺术》里对算法的归纳：
1.输入：一个算法必须有0个或者0个以上的输入量；
2.输出：一个算法应该 有1个或以上的输出量；
3.明确性：算法的描述必须无歧义，实际运行结果是正确的；
4.有限性：必须在有限的个步骤内结束；
5.有效性：能够被执行者实现。
什么是排序？
排序（Sorting）就是将一组对象按照规定的次序重新排列的过程，排序往往是为检索而服务的，它是数据处理中一种很重要也很常用的运算。例如我们日常学习中的查字典或者书籍的目录，这些都事先为我们排好序，因此大大降低了我们的检索时间，提高工作效率。
基本上，排序算法的输出必须遵守下列两个原则：
- 输出结果为递增序列（递增是针对所需的排序顺序而言）
- 输出结果是原输入的一种排列或是重组
稳定排序：
- 冒泡排序（Bubble Sort） — O(n²)
- 插入排序（Insertion Sort）— O(n²)
- 桶排序（Bucket Sort）— O(n); 需要 O(k) 额外空间
- 计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间
- 合并排序（Merge Sort）— O(nlogn); 需要 O(n) 额外空间
- 二叉排序树排序 （Binary tree sort） — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
- 基数排序（Radix sort）— O(n·k); 需要 O(n) 额外空间
不稳定排序:
- 选择排序（Selection Sort）— O(n²)
- 希尔排序（Shell Sort）— O(nlogn)
- 堆排序（Heapsort）— O(nlogn)
- 快速排序（Quicksort）— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大* 的、乱数串行一般相信是最快的已知排序
简单比较
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序对 n个项目需要O( n²)的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。
冒泡排序算法的运作如下：
- 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 3.针对所有的元素重复以上的步骤，除了最后一个。
- 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
function bubble_sort(array, length) {
var i, j;
for (i from 0 to length - 1) {
for (j from 0 to length - 1 - i) {
if (array[j] > array[j + 1])
swap(array[j], array[j + 1])
}
}
}
函数 冒泡排序 输入 一个数组名称为array 其长度为length
i 从 0 到 (length - 1)
j 从 0 到 (length - 1 - i)
如果 array[j] > array[j + 1]
交换 array[j] 和 array[j + 1] 的值
如果结束
j循环结束
i循环结束
函数结束
JS实例
Array.prototype.bubble_sort = function() {
var i, j, temp;
for (i = 0; i < this.length - 1; i++)
for (j = 0; j < this.length - 1 - i; j++)
if (this[j] > this[j + 1]) {
temp = this[j];
this[j] = this[j + 1];
this[j + 1] = temp;
}
return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.bubble_sort();
for (var i = 0; i < num.length; i++)
document.body.innerHTML += num[i] + " ";
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序
JS实例
Array.prototype.insertion_sort = function() {
var i, j;
for (i = 1; i < this.length; i++) {
for (j = 0; j < i; j++) {
if (this[j] > this[i]) {
this.splice(j, 0, this[i]);
this.splice(i + 1, 1);
}
}
}
return this;
};
快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），一种[排序算法。在平均状况下，排列n个项目要O(n log n)次比较。在最坏状况下则需要O(n²)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他
算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
算法：
快速排序使用分治法策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
- 从数列中挑出一个元素，称为"基准"（pivot）
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
JS实例
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>";
归并排序
归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)，该算法是采用分治法的一个非常典型的应用，且各层分治递归可以同时进行。
递归法[
原理如下（假设序列共有 n个元素）：
- 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
- 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
- 重复步骤2，直到所有元素排序完毕，即序列数为1
Array.prototype.merge_sort = function() {
var merge = function(left, right) {
var final = [];
while (left.length && right.length)
final.push(left[0] <= right[0] ? left.shift() : right.shift());
return final.concat(left.concat(right));
};
var len = this.length;
if (len < 2) return this;
var mid = len / 2;
return merge(this.slice(0, parseInt(mid)).merge_sort(), this.slice(parseInt(mid)).merge_sort());
};
