hanyeah

前边提到的排序都是比较排序，通过比较两个数的值来进行排序，比价排序的时间复杂度下界是O(nlgn)，要想有更快的算法，就要抛弃比较的思想。

假设要排序的元素都是整数（或者可以转化成整数），而且分布的区间可知，比如[0,k]。

这样，只要把要排序的数放到相应的位置，然后按次序取出就行了。

对于n个元素，区间是[0,k]，计数排序的时间复杂度是O(n+k)。

具体实现代码如下：

var a = [6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2];
console.log(a);
var b = countingSort(a, Math.max.apply(Math ,a) + 1);
console.log(b);

function countingSort(a, k){
	var len = a.length;
	var c = [];
	for(var i = 0; i < k; i++){
		c[i] = 0;
	}
	for(var i = 0; i < len; i++){
		c[a[i]] = c[a[i]] + 1;
	}
	//console.log(c.join('\t'));
	for(var i = 1; i < k; i++){
		c[i] = c[i] + c[i - 1];
	}
	//console.log(c.join('\t'));
	var b = [];
	for(var i = len - 1; i >= 0; i--){
		b[c[a[i]]] = a[i];
		c[a[i]] = c[a[i]] - 1;
	}
	return b;
}

桶排序思想类似，将要排序的元素分到k个有序区间中，每个区间内进行排序，然后再按顺序取出合并。