首先写个生成随机数和计算运行时间函数

 function rand(n=10,t=0){
    let arr=[]
    for(let i=0;i

1、归并排序

let {rand,stime} =require ("./fun");
let n=100000
let arr=rand(n)
function gb(arr,l,r){
    //递归结束条件
    if(l>=r) return   //判断条件可以优化
    //划分左右两边
    let mid=~~((l+r)/2)
    //递归划分  直到划分成l>=r时
    gb(arr,l,mid)
    gb(arr,mid+1,r)
    //只有左边》右边时才交换数据   （从小到大排序时
    if(arr[mid]>arr[mid+1]){
        merge(arr,l,r,mid)
    }
}
function merge(arr,l,r,mid){
  let newa=[]
  //左右指针
  let i=l,j=mid+1
  //复制一份新数组段
  for(let g=l;g<=r;g++){
    newa[g-l]=arr[g]
  }
//   console.log(newa,'////')
  //开始从左右边提取值  
  //左边小 提取arr[左] 左下标++    i
  //右边小 提取arr[右] 右下标++    j
 for(let k=l;k<=r;k++){
     if(i>mid){
        arr[k]=newa[j-l]
        j++
     }else if(j>r){
        arr[k]=newa[i-l]
        i++
     }else if(newa[i-l]>newa[j-l]){
        arr[k]=newa[j-l]
         j++
     }else{
        arr[k]=newa[i-l]
        i++
     }
 }
}
// stime(gb,arr,0,n-1)
// console.log(arr.slice(n-10,n))
//n=100      0ms
//n=1000     4ms
//n=10000    12ms
//n=100000   54ms
//向上归并排序
function gb2(arr,n){
    for(let s=1;s<=n;s+=s){
        for(let i=0;i+sarr[i+s]){
                merge(arr,i,Math.min(i+2*s-1,n-1),i+s-1)
            }
        }
    }
}
 stime(gb2,arr,n)
 console.log(arr.slice(n-10,n))
//n=100      1ms
//n=1000     3ms
//n=10000    19ms
//n=100000   71ms

2、快速排序

let {rand,stime} =require ("./fun");
let n=100000
let arr=rand(n)
function kuai(arr,l,r){
  if(l>=r) return
  let t=qs(arr,l,r)
  kuai(arr,l,t)
  kuai(arr,t+1,r)
}
function qs(arr,l,r){
    let v=arr[l]
    let i=l
    for(let j=l+1;jarr[j]){
            [arr[i+1],arr[j]]=[arr[j],arr[i+1]]
            i++
        }
    }
    [arr[l],arr[i]]=[arr[i],arr[l]]
    return i
}
stime(kuai,arr,0,n)
console.log(arr.slice(n-10,n))

//n=100     0ms
//n=1000    11ms
//n=10000   28ms
//n=100000  43ms

3、选择排序

let {rand,stime} =require ("./fun");
let n=100000
let arr=rand(n)
function xz(arr,n){
  for(let i=0;iarr[j]){
               [arr[i],arr[j]]=[arr[j],arr[i]]
          }
      }
  }
  console.log(arr.slice(0,10))
}
stime(xz,arr,100000)
//n=100     --12ms
//n=1000    --21ms
//n=10000   --318ms
//n=100000  --27651ms

4、插入排序

let {rand,stime} =require ("./fun");
let n=100000
let arr=rand(n)

function cr(arr,n){
   for(let i=1;i0&&arr[j]0&&arr[j]0&&tem