排序一直都是笔试面试爱考的内容，为了方便，自己把常考的排序用js写一遍。必要的时候还可以打开手机借鉴一下，嗯，抄自己写的东西不能算抄。
1.堆排序
通常使用大顶堆进行排序，排序后数据以升序排列。大顶堆使用数组进行存储，是一种完全二叉树，每个节点的左右子节点均小于等于它的父节点。所以，大顶堆的顶就是整个堆中最大的。
想要利用堆进行排序，最重要的就是调整一个二叉树为大顶堆。数组的第一个元素的下标是0，把它作为堆顶。对于一个节点，它的左节点下标为left(i)，右节点下标为right(i)，父节点parent(i)。
function left(i){
return 2*i+1;
}
function right(i){
return 2*i+2;
}
function parent(i){
return i<=2?0:Math.floor((i-1)/2);
}
我们写一个函数tiaozheng(array,i);用来进行调整，它的第一个参数为存储堆的数组，第二个参数为进行调整的“子树”的根节点。调整的结果是，把array[i]中的元素调整到一个何时的位置，即它的左右节点都比他小。而原先的array[i]位置会由它调整前左右节点中较大的一个占据。
function tiaozheng(array,i){
var largest = i;
var l = left(i);
var r = right(i);
if(l<=array.heap_size&&array[l]>array[i]){
largest = l;
}
if(r<=array.heap_size&&array[r]>array[largest]){
largest = r;
}
if(i!=largest){
var temp = array[largest];
array[largest] = array[i];
array[i] = temp;
tiaozheng(array,largest);
}
}
我们可以利用这个调整函数来将一个输入的函数调整为大顶堆。
function build(array){
var length = array.length;
array.heap_size = array.length-1;//heap_size指堆中剩余的节点个数，这里减1是由于我们的下标从0开始。
for(var i = parent(length-1);i>=0;i--){
tiaozheng(array,i);
}
}
最后，就是利用大顶堆的特性，将根节点的值一个一个取出，和数组结尾的元素交换，调整堆，重复之前操作。
function duipai(array){
var length = array.length;
build(array);
for(var i = length-1;i>0;i--){
var temp = array[0];
array[0] = array[i];
array[i] = temp;
array.heap_size-=1;
tiaozheng(array,0);
}
}
2.快速排序
快速排序的思想就是每次把比参照数大的放到他的一边，比他小的放到另一边。这样，参照数的位置就是他排序后的位置，也可以说，这个数已经排好序。之后，再以相同的方式对分出的左右两部分进行操作，递归进行，每个数就都排好了序，整个数组也就变为有序。
function quicksort(array,p,r){
if(p<r){
var q = partition(array,p,r);
quicksort(array,p,q-1);
quicksort(array,q+1,r);
}
}
程序的关键便是partition函数，常见的有两种实现方法
第一种：
function partition(array,p,r){
var x = array[r];
var i,j;
i = j = p;
for(j;j<r;j++){
if(array[j]<x){
var temp = array[i];
array[i] = array[j];
array[j] = temp;
++i;
}
}
var temp = array[i];
array[i] = array[r];
array[r] = temp;
return i;
}
这是算法导论一书中给出的方法，以数组的最后一个数为参照数，个人认为这种方法比第一种好理解。
过程就好像是一列火车向数组的末端开，当遇到比参照数小的数，就扔到车厢，遇到大的就加到车头，最后再把参照数扔到车厢和车头中间，返回它的位置。
第二种：
function partition(array,low,high){
var temp = array[low];
while(low<high){
while(low<high&&array[high]>temp)--high;
array[low] = array[high];
while(low<high&&array[low]<temp)++low;
array[high] = array[low];
}
array[low] = temp;
return low;
}
第二种方法看起来更简洁，但是理解起来比第一种费劲。大致过程就是从数组的两边向中间推进，反复覆盖，由于一开始把第一个被覆盖的数存了起来，所以最后不会有值“丢失”。
3.归并排序
归并函数主函数看起来和快排很像
function guibing(array,t,w){
if(t<w){
var q = Math.floor((t+w)/2);
arguments.callee(array,t,q);
arguments.callee(array,q+1,w);
merge(array,t,q,w);
}
}
他的思想是，先把整个数组分成两部分，将这两部分调整为有序，再合并这两部分。是一个递归的过程。
当数组被递归分为一个一个单独的元素时开始进行合并，因为每个单独的数都是有序的。
function merge(array,t,q,w){
var n1 = q-t+1;
var n2 = w-q;
var l = [];
var r = [];
for(var i = 0;i< n1;i++){
l[i] = array[t+i];
}
for(var j = 0;j<n2;j++){
r[j] = array[q+j+1]
}
l[i] = Infinity;
r[j] = Infinity;
i = j = 0;
for(var k = t;k<=w;k++){
if(l[i]<r[j]){
array[k] = l[i];
++i;
}else{
array[k] = r[j];
++j;
}
}
}