算法是程序的灵魂。虽然在前端的开发环境中排序算法不是很经常用到，但常见的排序算法还是应该要掌握的。我在这里从网上整理了一下常见排序算法的javascript实现，方便以后查阅。
归并排序：
1 function merge(left, right){
2 var result = [],
3 il = 0,
4 ir = 0;
5
6 while (il < left.length && ir < right.length){
7 if (left[il] < right[ir]){
8 result.push(left[il++]);
9 } else {
10 result.push(right[ir++]);
11 }
12 }
13
14 return result.concat(left.slice(il)).concat(right.slice(ir));
15 }
1 function mergeSort(items){
2
3 // 结束条件: 数组元素少于2个
4 if (items.length < 2) {
5 return items;
6 }
7
8 var middle = Math.floor(items.length / 2),
9 left = items.slice(0, middle),
10 right = items.slice(middle);
11
12 return merge(mergeSort(left), mergeSort(right));
13 }
1 function mergeSort2(items){
2
3 if (items.length < 2) {
4 return items;
5 }
6
7 var middle = Math.floor(items.length / 2),
8 left = items.slice(0, middle),
9 right = items.slice(middle),
10 params = merge(mergeSort(left), mergeSort(right));
11
12 params.unshift(0, items.length);
13 items.splice.apply(items, params);
14 return items;
15 }
插入排序：
function insertionSort(items) {
var len = items.length,
value,
i,
j;
for (i=0; i < len; i++) {
value = items[i];
for (j=i-1; j > -1 && items[j] > value; j--) {
items[j+1] = items[j];
}
items[j+1] = value;
}
return items;
}
选择排序：
1 function swap(items, firstIndex, secondIndex){
2 var temp = items[firstIndex];
3 items[firstIndex] = items[secondIndex];
4 items[secondIndex] = temp;
5 }
1 function selectionSort(items){
2
3 var len = items.length,
4 min;
5
6 for (i=0; i < len; i++){
7 min = i;
8 for (j=i+1; j < len; j++){
9 if (items[j] < items[min]){
10 min = j;
11 }
12 }
13
14 if (i != min){
15 swap(items, i, min);
16 }
17 }
18
19 return items;
20 }
冒泡排序：
1 function swap(items, firstIndex, secondIndex){
2 var temp = items[firstIndex];
3 items[firstIndex] = items[secondIndex];
4 items[secondIndex] = temp;
5 }
1 function bubbleSort(items){
2
3 var len = items.length,
4 i, j, stop;
5
6 for (i=0; i < len; i++){
7 for (j=0, stop=len-i; j < stop; j++){
8 if (items[j] > items[j+1]){
9 swap(items, j, j+1);
10 }
11 }
12 }
13
14 return items;
15 }
快速排序：
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
二分法查找：
1 function binarySearch(items, value){
2
3 var startIndex = 0,
4 stopIndex = items.length - 1,
5 middle = Math.floor((stopIndex + startIndex)/2);
6
7 while(items[middle] != value && startIndex < stopIndex){
8
9 if (value < items[middle]){
10 stopIndex = middle - 1;
11 } else if (value > items[middle]){
12 startIndex = middle + 1;
13 }
14
15 middle = Math.floor((stopIndex + startIndex)/2);
16 }
17
18 return (items[middle] != value) ? -1 : middle;
19 }
基数排序：
1 var countSort = function(array) {
2 var i, z = 0, count = [],
3 min = Math.min.apply({}, array),
4 max = Math.max.apply({}, array),
5 size = array.length;
6 //给新数组预填为零
7 for (i = min; i <= max; i++) {
8 count[i] = 0;
9 }
10 for (i=0; i < size; i++) {
11 count[array[i]]++;
12 }
13
14 for (i = min; i <= max; i++) {
15 while (count[i]-- > 0) {//循环新数组，如果不为零，则把i返回array
16 array[z++] = i;
17 }
18 }
19 return array;
20 }
希尔排序：
function shellSort(array) {
var j, i, v, h=1, s=3, k,n = array.length;
var result = "";
var count = 0;
while(h < n)
h=s*h+1;
while(h > 1) {
h=(h-1)/s;
for (k=0; k<h; k++)
for (i=k+h,j=i; i<n; i+=h, j=i) {
v=array[i];
while(true)
if ((j-=h) >= 0 && array[j] > v)
array[j+h]=array[j];
else
break;
array[j+h]=v;
}
count++;
result += "<br />第" + count + "遍排序的结果是:";
for (var n = 0; n < array.length; n++) {
result += array[n] + ",";
}
}
return result;
}
组合排序：
1 var combSort = function(array){
2 var gap = array.length;
3 do{
4 gap = gap * 10 / 13
5 if(gap === 9 || gap === 10)
6 gap = 11
7 if(gap < 1){
8 gap = 1
9 }
10 var swapped = false;
11 for(var i=0;i<array.length-gap;i++){
12 var j = i + gap
13 if(array[i]>array[j]){
14 var temp = array[i];
15 array[i] = array[j];
16 array[j] = temp;
17 test(array)
18 swapped = true
19 }
20 }
21 if(gap == 1 && !swapped){
22 break;
23 }
24 }while(1);
25 }
鸡尾酒排序：
var cocktailSort= function(array) {
var top = array.length - 1, bottom = 0,flag = true,i, j;
while (flag) {
flag = false;
//从左到右到大，把最大的放到每次范围的最右边
for (i = bottom; i < top; i++) {
if (array[i] > array[i + 1]) {
swap(array, i, i + 1);
flag = true;
}
}
top--;
//从右到到左，把最小的放到每次范围的最小边
for (j = top; j > bottom; j--) {
if (array[j] < array[j - 1]) {
swap(array, j, j - 1);
flag = true;
}
}
bottom++;
}
}
var swap = function(array,a,b){
var tmp = array[a];
array[a] = array[b]
array[b] = tmp;
}