js实现常见排序方法

js实现常见排序方法

// 交换函数
function swap(arr,i,j) {
    var temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}

// 冒泡排序
function bubleSort(arr) {
    var flag=true;
    for(var i=0,len=arr.length;ii;j--){
            if(arr[j]temp;j--){
                arr[j+1]=arr[j];
            }
            arr[j+1]=temp;
        }

    }
    return arr;
}
console.log('直接插入排序：',insertSort([8,3,5,1,5,2,1]));

//希尔排序
function shellSort(arr){
    var increment=arr.length;
    do{
        increment=Math.floor(increment/3)+1; // 注意js中的取整运算
        for(var i=increment,len=arr.length;i=0&&temp1);
    return arr;
}
console.log('希尔排序：',shellSort([8,3,5,1,5,2,1]));

//堆排序
function heapSort(arr) {
    for(var i=Math.floor(arr.length/2)-1;i>=0;i--){ // 构建大顶堆
        heapAdjust(arr,i,arr.length-1);
    }

    for(var j=arr.length-1;j>=0;j--){
        //将堆顶元素与最后一个元素交换
        var temp=arr[0];
        arr[0]=arr[j];
        arr[j]=temp;
        //调整前j-1个元素组成的堆
        heapAdjust(arr,0,j-1);
    }
    return arr;
}

function heapAdjust(arr,s,m) { // s是要调整元素的下标，m是堆中最后一个元素的下标
    var temp,j;
    temp=arr[s];
    for(j=2*s+1;j<=m;j=2*j+1){
        if(j<>=arr[j]) // 如果arr[s]比其左右子节点都大，则跳出循环，此结点调整完毕
            break;
        arr[s]=arr[j]; // 否则当前结点的值被较大子节点代替
        s=j;    // 并将当前结点（接下来要调整的结点）设为较大子节点
    }
    arr[s]=temp;
}
console.log('堆排序：',heapSort([8,3,5,1,5,2,1]));
console.log('堆排序：',heapSort([1,2]));

//归并排序
function mergeSort(arr) {
    if(arr.length===0){return [];}
    Msort(arr,arr,0,arr.length-1);
    return arr;
}

function Msort(arr,res,s,t) {
    var m;
    var TR2=[];
    if(s===t){
        res[s]=arr[s];
    }else{
        m=Math.floor((s+t)/2);
        Msort(arr,TR2,s,m);
        Msort(arr,TR2,m+1,t);
        Merge(TR2,res,s,m,t);
    }
}
// 将有序的SL[i...m]和SL[m+1...n]合并为有序的res[i...n]
function Merge(SL,res,i,m,n) {
    var j,k,p;
    for(k=i,j=m+1;i<=m&&j<=n;k++){ //从头开始遍历两个有序数组，直到有一个遍历到最后
        if(SL[i]arr[high])
        swap(arr,low,high);
    if(arr[m]>arr[high])
        swap(arr,m,high);
    if(arr[m]>arr[low])
        swap(arr,m,low);
    var pivotkey=arr[low];// 此时low已经是三者中的中间值

    var temp=pivotkey;// 替换的方法，而非交换的方法
    while (low=pivotkey){high--;}

        //swap(arr,high,low); // 交换的方法
        arr[low]=arr[high]; //采用替换的方法

        while (low