js实现多种排序算法(算法导论第二章)

风和日丽 2019-07-01

  1. 插入排序:

    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)

  2. 归并排序(非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)
       }

    }

  3. 归并排序(酷炫简单)

    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));

    }

相关推荐