js版本5种排序算法

//百度来的随机打乱数组用的函数
function randomsort(a, b) {
    return Math.random()>.5 ? -1 : 1
    //用Math.random()函数生成0~1之间的随机数与0.5比较，返回-1或1
}

//交换num数组索引a和b的值
function ex(num,a,b){
    let x=num[a]
    num[a]=num[b]
    num[b]=x
}


//希尔排序
function shellSort(num1){
    var num=JSON.parse(JSON.stringify(num1))
    arr=[]
    var i=1
    while(i<num.length){
        arr.unshift(i)
        i=i*3+1
    }
    for(let i in arr){
        let j=arr[i]
        //console.log(j,num)
        for(let x=j;x<num.length;x++){
            var y=x
            //这里不需要写num[y]<num[y-j]，用插入排序模拟即可
            while(y<num.length&&num[y]<num[y-j]){
                ex(num,y,y-j)
                y=y-j
            }
        }
    }
    return num
}


//归并排序
function mergeBUSort(num1){
    var num=JSON.parse(JSON.stringify(num1))
    mergeBUSort_(num,0,num.length-1)
    return num
}

function mergeBUSort_(num,lo,hi){
    if(lo>=hi)return			
    //lo比hi小5到15时建议切换插入排序，这里insertSort未实现				
    //if(hi-lo>5&&hi-lo<15){insertSort(num,lo,hi);return}			
    var mid=Math.floor((hi-lo)/2)+lo
    mergeBUSort_(num,lo,mid)
    mergeBUSort_(num,mid+1,hi)
    merge_(num,lo,mid,hi)
}

function merge_(num,lo,mid,hi){
    var arr=[]
    var i=lo
    var j=mid+1
    while(i<=mid&&j<=hi){
        if(num[i]>num[j]){arr.push(num[j++])}
        else{arr.push(num[i++])}
    }
    for(let x=i;x<=mid;x++){arr.push(num[x])}
    for(let x=j;x<=hi;x++){arr.push(num[x])}
    for(let x=lo;x<=hi;x++){num[x]=arr[x-lo]}
}


//快速排序
function quickSort(num1){
    var num=JSON.parse(JSON.stringify(num1))
    //console.log('-->',num)
    quickSort_(num,0,num.length-1)
    return num
}

function quickSort_(num,lo,hi){
    //console.log(num,lo,hi)
    if(lo>=hi)return						//lo比hi小5到15时建议切换插入排序，代码同上
    let mid=partition(num,lo,hi)
    quickSort_(num,lo,mid-1)
    quickSort_(num,mid+1,hi)
}

function partition(num,lo,hi){
    var i=lo+1
    var j=hi
    let temp=num[lo]
    while(i<=j&&i<=hi&&lo<j){
        while(num[i]<=temp&&i<=hi)i++
        while(num[j]>=temp&&lo<j)j--
        if(i<j){ex(num,i++,j--)}
    }
    ex(num,lo,j)
    return j
}


//三向切分的快速排序
function quick3WaySort(num1){
    var num=JSON.parse(JSON.stringify(num1))
    //console.log(num)
    quick3WaySort_(num,0,num.length-1)
    return num
}

function quick3WaySort_(num,lo,hi){
    //console.log(num,lo,hi)
    if(lo>=hi)return
    let mid=partition3Way(num,lo,hi)
    quick3WaySort_(num,lo,mid[0]-1)
    quick3WaySort_(num,mid[1]+1,hi)
}

function partition3Way(num,lo,hi){
    var c=lo
    var i=lo+1
    var j=hi
    let temp=num[lo]
    while(i<=j&&i<=hi&&lo<j){
        if(num[i]>temp)ex(num,i,j--)
        if(num[i]<temp)ex(num,c++,i++)
        if(num[i]==temp&&i<=hi)i++
    }
    return [c,j]
}


//堆排序heapSort,使用递增的二叉堆
function up(heap,maxIndex,i){
    var j=Math.floor(i/2)
    while(heap[i]<=heap[j]&&i>1){
        ex(heap,i,j)
        i=j
        j=Math.floor(i/2)
    }
}
function down(heap,maxIndex,i){
    var j=i*2
    while (j<=maxIndex){
        if(j<maxIndex&&heap[j+1]<heap[j])j++
        if(heap[i]>=heap[j])ex(heap,i,j)
        i=j
        j=i*2
    }
}
function generateHeap(num1){
    var num=JSON.parse(JSON.stringify(num1))
    num.unshift(undefined)
    return num
}
function getSortedHeap(heap){
    let len_=heap.length
    for(let i=Math.floor(len_/2);i>0;i--){
        down(heap,len_-1,i)
    }
    return heap
}
function heapSort(heap){
    let ind=heap.length-1
    while(ind>0){
        ex(heap,1,ind)
        down(heap,ind-1,1)
        ind--
    }
    heap.splice(0,1)
    return heap.reverse()
}

//开始测试
var N=100000
var num=[]
for(let i=1;i<1+N;i++){
    num.push(i)
    num.push(i)
}
let res=JSON.stringify(num)
num.sort(randomsort)
console.log(num)
console.log('shellSort-->',JSON.stringify(shellSort(num))==res)
console.log('mergeBUSort-->',JSON.stringify(mergeBUSort(num))==res)
console.log('quickSort-->',JSON.stringify(quickSort(num))==res)
console.log('quick3WaySort-->',JSON.stringify(quick3WaySort(num))==res)
console.log('heapSort-->',JSON.stringify(heapSort(getSortedHeap(generateHeap(num))))==res)

最后

以上就是伶俐铃铛为你收集整理的js版本5种排序算法的全部内容，希望文章能够帮你解决js版本5种排序算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。