ソートアルゴリズムのまとめ2(JavaScript)

1、並べ替え(上から下へ)
複雑度:O(nlogn)              安定している
レプリカを保持するには、時間効率と空間を交換するために、追加のn個の記憶空間を開く必要があります.

//            ，          ，                   ，             
function __merge(arr,l,mid,r){
    var copy=[];
    for(var m=l;m<=r;m++){
        copy[m]=arr[m];
    }
    var i=l,j=mid+1;
    for(var k=l;k<=r;k++){
        if(i>mid){              //         
            arr[k]=copy[j];
            j++;
        }
        else if(j>r){          //          
            arr[k]=copy[i];
            i++;
        }
        else if(copy[i];
            i++;
        }
        else{
            arr[k]=copy[j];      //        ，          ，     j   

            j++;
        }
    }

}

//                   
function __mergeSort(arr,l,r){
    if(l>=r){
        return;
    }
    var mid=Math.floor((l+r)/2);
    __mergeSort(arr,l,mid);
    __mergeSort(arr,mid+1,r);
    //             ，       ，          ，           
  if(arr[mid]>arr[mid+1]){
        __merge(arr,l,mid,r);
    }
}
function mergeSort(arr){
    var n=arr.length;
    __mergeSort(arr,0,n-1);
    return arr;
}

2、並べ替え(ボトムアップ)

function __merge(arr,l,mid,r){
    var copy=[];
    for(var m=l;m<=r;m++){
        copy[m]=arr[m];
    }
    var i=l,j=mid+1;
    for(var k=l;k<=r;k++){
        if(i>mid){
            arr[k]=copy[j];
            j++;
        }
        else if(j>r){
            arr[k]=copy[i];
            i++;
        }
        else if(copy[i];
            i++;
        }
        else{
            arr[k]=copy[j];
            j++;
        }
    }

}
//                    ，              
function mergeSortBU(arr){
    var n=arr.length;
    var size,i;
    //       ，          size
    for(size=1;size;size+=size){
        //        
        for(i=0;i+size;i+=size+size){
            //  ：               
            if(arr[i+size-1]>arr[i+size]){
                __merge(arr,i,i+size-1,Math.min(i+size+size-1,n-1));   //    
            }
        }
    }
    return arr;
}

3、快速並べ替え(3番の快速並べ替え)
複雑度:O(nlogn)          不安定です
追加のスペースを開く必要はありません.

function __quickSort(arr,l,r){
    if(l>=r){
        return;
    }
    //  ：              ：arr[l+1....lt]       ： arr[lt+1....i]       ： arr[gt...r];
    var v=arr[l];     //         
    var lt=l;
    var gt=r+1;
    var i=l+1;
    while(iif(arr[i]//        lt+1  
            var temp=arr[i]; arr[i]=arr[lt+1]; arr[lt+1]=temp;
            lt++;
            i++;
        }
        else if(arr[i]>v){     //        gt-1  
            var temp2=arr[i]; arr[i]=arr[gt-1]; arr[gt-1]=temp2;
            gt--;
        }
        else{           //           
            i++;
        }
    }
    //            
    var temp1=arr[l];
    arr[l]=arr[lt];
    arr[lt]=temp1;
    //             
    __quickSort(arr,l,lt-1);
    __quickSort(arr,gt,r);
}
function quickSort(arr){
    var n=arr.length;
    __quickSort(arr,0,n-1);
    return arr;
}

4、積み上げ順序
複雑度:O(nlogn)        不安定です
元の場所に並べ替えて、追加の空間を開発する必要はありません.

//left child (i)=2*i+1      right child (i)=2*i+2     parent(i)=(i-1)/2
//            ： (n-1)/2
//        
function shiftDown(arr,n,k){
    //       n                          
    while((2*k+1)2*k+1] || (arr[k]2*k+2]&&2*k+2//             
        if(2*k+22*k+1]2*k+2]){
            [arr[k],arr[2*k+2]]=[arr[2*k+2],arr[k]];
            k=2*k+2;
        }else{            //                    
            [arr[k],arr[2*k+1]]=[arr[2*k+1],arr[k]];
            k=2*k+1;
        }
    }
}
function heapSort(arr){
    var n=arr.length;
    //         
    for(var i=Math.floor((n-1)/2);i>=0;i--){
        shiftDown(arr,n,i);
    }
    for(var j=n-1;j>0;j--){
        //      ，                
        [arr[j],arr[0]]=[arr[0],arr[j]];
        //          1，      ；  1        
        if(j>1){
            shiftDown(arr,j,0);
        }else{
            break;
        }
    }
    return arr;
}