js实现了一下几种基于比较的排序（常数时间的排序还没看！阿西吧！）
插排和冒泡平均时间复杂度o(n^2)，最优o(n)，前两种稳定。选择都是n^2不稳定。
提一下冒泡，一直以为它最坏最好都是n^2复杂度，不过写的时候发现每次冒泡可以检查本次是否交换过元素，如果没有直接退出，最优情况排好序的数组，一趟遍历退出。
通常小数据量选择和插排比较快。基本排好序，小数据量用插排.
1. 直接插入
function insertSort(arr) {
console.time("insert sort: ");
for (var i = 0; i < arr.length; i++) {
var j = i;
var value = arr[i];
while(j>0 && value < arr[j-1]) {
arr[j] = arr[j-1];
j--;
}
arr[j] = value;
}
console.timeEnd("insert sort: ");
return arr;
}
2. 冒泡
function bubbleSort(arr) {
console.time("bubble sort: ");
for(var i = 0; i < arr.length; ++i){ //n次遍历
var change = false;
for(var j = arr.length-1; j > i; --j) { //从最后冒泡至i，一次冒泡i最小
if(arr[j] < arr[j-1]) {
var temp = arr[j-1]
arr[j-1] = arr[j];
arr[j] = temp;
change = true;
}
}
if(!change) {
console.timeEnd("bubble sort: "); //0.074
return arr;
}
}
console.timeEnd("bubble sort: "); //0.095
return arr;
}
3. 选择
function selectSort(arr) {
console.time("select sort: ");
for(var i = 0; i < arr.length-1; ++i) {
var min = i;
for(var j = i; j < arr.length; ++j) {
if(arr[j] < arr[min]) {
min = j;
}
}
var temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
console.timeEnd("select sort: ");
return arr;
}
4. 快排
然后是快排，平均o(nlogn)，最差o(n^2)在原数据正序或逆序时。快排复杂度能到nlogn主要是每次选取pivot可以把元素划分为两段更小元素处理从而实现divide-conquer的目的，但是如果数据正序或逆序，每次划分后子问题规模是n-1就退化成了n^2复杂度。不稳定。
function qS(arr) {
var partition = function(a, l, h) {
var p = l;
l++;
while(l<h) {
while(l<h && a[h] > a[p]) {
h--;
}
while(l<h && a[l] <= a[p]) {
l++;
}
if(l < h) {
var temp = a[l];
a[l] = a[h];
a[h] = temp;
// h--;
// l++; //交换之后继续从当前位置扫
}
}
// console.log(h);
// console.log(l);
var temp = a[p];
a[p] = a[h];
a[h] = temp;
// console.log(a);
return h;
}
var sort = function(a, l, h) {
if(l<h) {
var pivot = partition(a, l, h);
// console.log(pivot);
sort(a, l, pivot-1);
sort(a, pivot+1, h);
}
}
return {sa:arr, sort:sort}
}
5. 堆排序
利用大顶堆或小顶堆性质排序，复杂度最优平均都是o(nlogn)，不稳定。核心是构建大顶堆，和每次取元素之后对堆的maxheapify——递归的方法调整堆，使得其满足根大于子节点的特性，注意停止条件。
[codesyntax lang=”php”]
function heapSort(arr) {
function maxHeapify(arr, index, size) {
var max = index;
var left = 2*index+1;
var right = 2*index+2
if(left < size && arr[left] > arr[max]) {
max = left;
}
if(right < size && arr[right] > arr[max]) {
max = right;
}
if(index != max){
swap(arr, index, max);
maxHeapify(arr, max, size);
}
}
function buildHeap(arr) {
for(var i = Math.floor((arr.length-1)/2); i >= 0; --i) {
maxHeapify(arr, i, arr.length);
}
}
function sort(arr) {
buildHeap(arr);
for(var i = 0; i < arr.length; ++i) {
swap(arr, 0, arr.length-i-1);
//console.log(arr);
maxHeapify(arr, 0, arr.length-i-1);
}
return arr;
}
function swap(arr, a, b) {
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
return{arr:arr, sort:sort};
}
6. 希尔排序
基于插排的改进，通过调整步长减少元素移动的次数（插排中相当于每次只能移动1位，如果调整2341中1的位置就需要比较3次移动3次）o(nlogn)
function shellSort(arr) {
var gap = 1;
while(gap < arr.length) {
gap = gap*3 + 1;
}
for(; gap > 0; gap=Math.floor(gap/3)) {
for(var j = gap; j < arr.length; ++j) {
var value = arr[j]
while(j>=0 && arr[j-gap] > value) {
arr[j] = arr[j-gap];
j = j-gap;
}
arr[j] = value;
var value = arr[j];
}
}
return arr;
}
7. 归并排序
典型分治思想，复杂度o(nlogn)，递归，空间需求大。（外排）
function mergeSort(arr) {
if(arr.length == 1) {
return arr;
}else {
var m = Math.floor(arr.length/2);
return merge(mergeSort(arr.slice(0,m)), mergeSort(arr.slice(m,arr.lenth)));
}
}
function merge(arr1, arr2) {
var i = 0;
var j = 0;
var result = [];
while(i + j < arr1.length + arr2.length) {
if(arr1[i] <= arr2[j] || j == arr2.length) {
result[i+j] = arr1[i];
i++;
}else if(i < arr1.length || i == arr1.length){
result[i+j] = arr2[j];
j++;
}
}
return result;
}