고전 정렬 알고리즘 의 javascript 구현

정렬 의 안정성: 같은 몇 가지 요 소 는 정렬 한 후에 상대 적 인 선후 순서 가 변 하지 않 으 면 이 정렬 알고리즘 을 안정 적 이 라 고 부른다.정렬 알고리즘 이 안정 적 인지 여 부 는 구체 적 인 알고리즘 에 의 해 결정 되 고 불안정 한 알고리즘 은 특정한 조건 에서 안정 적 인 알고리즘 으로 변 할 수 있 으 며 안정 적 인 알고리즘 은 특정한 조건 에서 도 불안정 한 알고리즘 으로 변 할 수 있다.안정 적 인 정렬 알고리즘: 거품 정렬, 삽입 정렬, 병합 정렬, 기수 정렬, 통계 정렬 불안정 정렬 알고리즘: 정렬 선택, 빠 른 정렬, 힐 정렬, 쌓 기 정렬
내부 정렬: 원 데이터 구조 에서 요소 의 값 을 직접 교환 하여 정렬 합 니 다.
알고리즘 은 수치 요소 에 만 정렬 되 고 일부 알고리즘 은 비 마이너스 정수 나 0 이상 의 정수 에 만 적 용 됩 니 다.js 에서 undefined 의 부등식 연산 은 false 로 되 돌아 가기 때문에 일부 비교 작업 이 실행 되 기 전에 변수 에 초기 값 을 부여 하지 않 았 고 배열 의 경 계 를 검사 하지 않 았 으 며 다른 프로 그래 밍 언어 로 번역 할 때 주의해 야 합 니 다.
알고리즘 설명 은 다음 글 을 참고 하 십시오 @ kkun:http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html
addr: http://www.cnblogs.com/ecalf/archive/2013/04/15/3022193.htmlauthor: ecalf
 
잘못 과 결함 이 있 는 부분 을 지적 해 주 셨 으 면 좋 겠 습 니 다.
 

//    
function BubbleSort(arr){
    var swaped;
    for(var i=0,l=arr.length;i<l;i++){
        swaped = false;
        for(var j=l-1;j>=i+1;j--){
            if(arr[j]<arr[j-1]){
                arr[j] = [arr[j-1],arr[j-1]=arr[j]][0];
                swaped = true;
            }
        }
        if(!swaped){ break; }
    }

  return arr;
}

 

//    
function InsertSort(arr){  
    var  temp;
    for(var i=1,l=arr.length;i<l;i++){ 
        temp = arr[i];
        for(var j=i;j>0;j--){
            if(arr[j-1]>temp){
                arr[j] = arr[j-1];
            }else{                              
                break;
            } 
        }
        arr[j] = temp;   

    }

    return arr;
}

 

//    
function SelectSort(arr){
    for(var i=0,l=arr.length;i<l-1;i++){
        for(var j=i+1;j<l;j++){
            if(arr[j]<arr[i]){
                arr[i] = [arr[j],arr[j]=arr[i]][0];
            }
        }
    }

    return arr;
}

 
 

//    
function QuickSort(arr){
    if(arr.length<=1){    return arr;  }
    var self = arguments.callee;
    var left = [],right = [],middle=[];
    var mid = arr[Math.floor(arr.length/2)];
    for(var i=0;i<arr.length;i++){    
        if(arr[i]<mid){
            left.push(arr[i])
        }else if(arr[i]>mid){
            right.push(arr[i]);
        }else{
            middle.push(arr[i]);
        }
    }

  return [].concat(self(left),middle,self(right));
}

 

//    (2   ) 
function MergeSort(arr){
    if(arr.length<=1){ return arr;}
    var self = arguments.callee;
    var mid = Math.floor(arr.length/2);
    var left = self(arr.slice(0,mid));
    var right = self(arr.slice(mid));
    var result = [];

    while(left.length&&right.length){
        if(left[left.length-1]<=right[0]){
            result = result.concat(left);
            left = [];            
        }else if(right[right.length-1]<left[0]){
            result = result.concat(right);
            right = [];
        }else{            
            if(right[0]<left[0]){
                result.push(right.shift());
            }else{
                result.push(left.shift());
            }
        }          
    }
    result = result.concat(left,right);

    return result;
}

 

//    (  10  ),    
function RadixSort(arr,scale){
    scale = scale||10;    
    var max = Math.max.apply(Math,arr);
    var remMask=1,buckets=[],radix;
    while(max>remMask){        
        for(var i=0;i<arr.length;i++){
            radix = Math.floor(arr[i]/remMask)%scale;
            if(!buckets[radix]){
                buckets[radix] = [];
            }
            buckets[radix].push(arr[i]);            
        }

        arr = [];
        for(var k=0;k<buckets.length;k++){
            if(buckets[k]){
                arr = arr.concat(buckets[k]);  
            }        
        }

        remMask *= scale;       
    }
    
    return arr;
}

 

//   ,   ,    
function BucketSort(arr){
    var buckets = [];
    for(var i=0;i<arr.length;i++){
        buckets[arr[i]] = arr[i];
    }
    arr = [];
    for(var i=0;i<buckets.length;i++){
        if(buckets[i]!==undefined){
            arr.push(buckets[i]);
        }
    }

    return arr;
}

 

//    ,    
function PigeonholeSort(arr){
    var tempArr = [];
    for(var i=0,l=arr.length;i<l;i++){
        tempArr[arr[i]] = (tempArr[arr[i]]+1)||1 ;
    }

    var result = [],count;
    for(var k=0;k<tempArr.length;k++){
        count = tempArr[k];
        if(count){
            for(var i=0;i<count;i++){
                result.push(k);
            }
        }      
    }

    return result;    
}

 

//    , fences：      ，        1 ,such as [5,3,1]
function ShellSort(arr,fences){
    var half = Math.floor(arr.length/2);
    while(fences.length){        
        var fence = fences.shift();
        if(fence>half){ continue; }

        var tempArr = [];
        while(arr.length){//  
            for(var i=0;i<fence&&arr.length;i++){
                tempArr[i] = tempArr[i]||[];
                tempArr[i].push(arr.shift());
            }
        }

        
        for(var i=0;i<tempArr.length;i++){  
            //                          
            for(var k=1,l=tempArr[i].length;k<l;k++){
                var temp = tempArr[i][k];
                for(var j=k;j>0;j--){
                    if(tempArr[i][j-1]>temp){
                        tempArr[i][j] = tempArr[i][j-1];
                    }else{
                        break;
                    } 
                }
                tempArr[i][j] = temp;  
            }
        }
        arr = [].concat.apply([],tempArr);
    }
    return arr;
}

 

//   (2  )
function HeapSort(arr){
    var findRoot = function(arr,p,length){
        p = p||0;
        length = length||arr.length;
        var self = arguments.callee;
        var l = p*2+1;
        var r = (p+1)*2;        
        var left,right;
        if(l<length){
            left = self(arr,l,length);
        }
        if(r<length){
            right = self(arr,r,length);
        }

  
        if(left>arr[p]){
            arr[p] = [left,arr[l]=arr[p]][0];
        }

        if(right>arr[p]){
            arr[p] = [right,arr[r]=arr[p]][0];
        }
        
        return arr[p];
    };  
    
    
    for(var i=arr.length;i>0;i--){
        findRoot(arr,0,i);
        arr[i-1] = [arr[0],arr[0]=arr[i-1]][0];
    }    
        
    return arr;
}

 

//    
function OddevenSort(arr){
    var swaped = true,k=0;
    while(swaped){
        if(k>0){
            swaped = false;
        }
        
        for(var i=k;i<arr.length-1;i+=2){
            if(arr[i]>arr[i+1]){
                arr[i] = [arr[i+1],arr[i+1]=arr[i]][0];                
                swaped = true;                 
            }            
        }

        k = [1,0][k];
    }

    return arr;
}

 

//     
function CocktailSort(arr){
    var swaped = true;
    var l=0,r=arr.length-1;
    while(swaped){
        swaped = false;
        for(var i=l;i<=r;i++){
            if(arr[i]>arr[i+1]){
                arr[i] = [arr[i+1],arr[i+1]=arr[i]][0];
                swaped = true;
            }
        }
        r--;

        for(var i=r;i>l;i--){
            if(arr[i]<arr[i-1]){
                arr[i] = [arr[i-1],arr[i-1]=arr[i]][0];
                swaped = true;
            }
        }
        l--;        
    }
    
    return arr;
}

 

//    
function GnomeSort(arr){
    var i=1;
    while(i<arr.length){        
        if(arr[i]<arr[i-1]){
            arr[i] = [arr[i-1],arr[i-1]=arr[i]][0];
            i = --i||1;
        }else{
            i++;
        }
    }

    return arr;
}

 

//   ,   
function BeadSort(arr){
    var result = [];
    var beads = [];
    for(var i=0;i<arr.length;i++){
        bead = arr[i];
        while(bead){
            bead--;
            beads[bead] = (beads[bead]||0)+1;
        }
    }

    for(var i=beads[0],l=i;i>0;i--){
        for(var j=0;j<beads.length;j++){
            if(i<=beads[j]){
                result[l-i] = (result[l-i]||0)+1;
            }
        }
    }

    while(arr.length-result.length){
        result.unshift(0);
    }

    return result;
}

 

//    
function CountingSort(arr){
    var count = [];
    for(var i=0;i<arr.length;i++){
        count[i] = count[i]||0;
        for(var j=i+1;j<arr.length;j++){            
            count[j] = count[j]||0;
            if(arr[i]>arr[j]){
                count[i]+=1;
            }else{
                count[j]+=1;
            }
        }
    }
    
    var result = [];
    for(var c=0;c<count.length;c++){
        result[count[c]] = arr[c];
    }

    return result;    
}

 

//   ，           
function CycleSort(arr){
    var count = [];
    for(var i=0;i<arr.length;i++){
        count[i] = count[i]||0;
        for(var j=i+1;j<arr.length;j++){            
            count[j] = count[j]||0;
            if(arr[i]>arr[j]){
                count[i]+=1;
            }else{
                count[j]+=1;
            }
        }
    }
    
    var temp,pos,cycleIndex;
    for(var cycleStart=0;cycleStart<arr.length;cycleStart++){
        if(count[cycleStart]==cycleStart){ continue; }

        temp = arr[cycleStart];
        pos = count[cycleStart];         
        do{
            cycleIndex= pos ;  
            temp  = [arr[pos],arr[pos]= temp][0]; 
            pos = [count[pos ],count[pos ]=pos][0];   
        }while(cycleIndex!=cycleStart);
    }

    
    return arr;    
}

 
 
 

//   
function CombSort(arr){
    var step = arr.length, swaped = true;
    while(swaped||step>1){
        swaped = false;
        if(step>1){
            step = Math.floor(step/1.3);            
        }
        step = step||1;
        
        
        for(var i=0;i+step<arr.length;i++){
            if(arr[i]>arr[i+step]){
                arr[i] = [arr[i+step],arr[i+step]=arr[i]][0];
                swaped = true;
            }
        }
    }

    return arr;
}

 

//    
function PatienceSort(arr){
    var buckets = [],temp;
    for(var i=0;i<arr.length;i++){
        temp = arr[i];
        for(var j=0;j<buckets.length;j++){
            if(buckets[j][buckets[j].length-1]<=temp){
                buckets[j].push(temp);
                temp = null;
                break;
            }            
        }
        if(temp!==null){
            buckets.push([temp]);
        }
    }
    arr = [].concat.apply([],buckets);
    for(var i=buckets[0].length;i<arr.length;i++){
        for(var j=i;j>0;j--){
            if(arr[j]<arr[j-1]){
                arr[j] = [arr[j-1],arr[j-1]=arr[j]][0];
            }else{
                break;
            }
        }        
    }

    return arr;
}