题解 | #排序#

第一种 归并排序,时间复杂ologn 空间n 稳定

 if(arr.length<2)return arr
    let  len=arr.length
 let   mid=parseInt((len)/2)
  let  left=arr.slice(0,mid)
  let  right=arr.slice(mid,len)
  let  mergeleft=MySort(left)
  let  mergeright=MySort(right)
    return merge( mergeleft,mergeright)

 function  merge(left,right){
     let  res=[]
        while(left.length!=0  &&right.length!=0){
            if(left[0]<=right[0]){
                res.push(left.shift())
            }
            else{
                res.push(right.shift())
            }
        } 
     while(left.length!=0){
         res.push(left.shift())
     }
     while(right.length!=0){
         res.push(right.shift())
     }
     return  res}

第二种快排,也是递归加分而治之 ,时间nlogn 空间nlogn 不稳定

if(arr.length<=1)return arr
    let  left=[]
     let right=[]
     let  len=arr.length
    let mid=parseInt(len/2)
  let   p=arr.splice(mid,1)[0]
     for(let i=0;i<arr.length;i++){
         if(arr[i]<=p){
            left.push(arr[i])
         }
         else{
            right.push(arr[i])
         }
     }
   return MySort(left).concat([p],MySort(right))  

第三种是插入排序 时间n2 空间1 不稳定 超时了.....就离谱 ,代码最简洁的....

for(let i=1;i,arr.length;i++){
         let  curr=arr[i]
       let  j=i-1
         while(j>=0  && curr<arr[j]){
             arr[j+1]=arr[j];
           j--
        }
         arr[j+1]=curr
    }
     return   arr