js实现多种排序算法（算法导论第二章）

插入排序：

var a = [1,7,4,2,17,13,9]

function insertionSort(arr){

arr.map((d,index)=>{
       let i = index
       while(d<arr[i-1]&&i-1>0){
           [arr[i-1],arr[i]]=[arr[i],arr[i-1]]
           i--
       }
   })

}

insertionSort(a)

归并排序（非hack）

function merge (arr,l,m,r){

var left = []
   var right = []
   for (let i =l;i<m;i++){
       // console.log(i)
       left.push(arr[i])
   }
   for(let j = m;j<=r;j++){
       right.push(arr[j])
       // console.log(j)
   }
   left.push(Infinity)
   right.push(Infinity)
   console.log(left,right)
   var i =0
   var j =0
   for(let k =l;k<r+1;k++){

       if(left[i]<right[j]){
           arr[k]=left[i]
           i++
       }else{
           arr[k]=right[j]
           j++
       }
   }

}

function mergeSort(arr,l,r){

if(r>l){
       var m=Math.ceil((l+r)/2)
       // console.log(m)
       mergeSort(arr,l,m-1)
       mergeSort(arr,m,r)
       merge(arr,l,m,r)
   }

}

归并排序（酷炫简单）

function merge(left, right) {

var tmp = [];

 while (left.length && right.length) {
   if (left[0] < right[0])
     tmp.push(left.shift());
   else
     tmp.push(right.shift());
 }

 return tmp.concat(left, right);

}

function mergeSort(a) {

if (a.length === 1) 
   return a;

 var mid = ~~(a.length / 2)
   , left = a.slice(0, mid)
   , right = a.slice(mid);

 return merge(mergeSort(left), mergeSort(right));

}