insertion sort

插入排序 insertion sort

Worst case performance ：О(n2) comparisons, swaps
Best case performance ：O(n) comparisons, O(1) swaps
Average case performance： О(n2) comparisons, swaps
Worst case space complexity： О(n) total, O(1) auxiliary

參考資料：

• wiki insertion sort
• javascript dom reference

<style>
.container201312080935{
    width: 365px;
    height: 155px;
    border-style:solid;    
    /*border-color:#cccccc;*/
    border-width: 1px;
    padding-left: 5px;
    padding-right: 5px;  
    padding-top: 5px;
    padding-bottom: 5px;   
}

.rectangle201312080935{
    margin: 5px 5px 5px 5px;
    width: 40px;
    height: 40px;
    border-style:solid;
    border-width: 1px;  
    /*border-color:#cccccc;*/
    float: left;
    text-align: center;
    line-height: 40px;
}
</style>

<div id="container201312080935" class="container201312080935">    
</div>
<br/>
<input type="button" value="sort" id="sort201312080935" />
<input type="button" value="random" id="random201312080935"/>

<script type="text/javascript">
(function(){
    var container=document.getElementById('container201312080935'),
        sort=document.getElementById('sort201312080935'),
        random=document.getElementById('random201312080935');
        
    var init = function(){
        //create number  rectangle   
        for(var i=0 ; i < 21 ; i++){            
            container.appendChild(getDisplayObject());
        } 
        
        addListener();        
    }; 
    
    var addListener = function(){
        sort.addEventListener('click' ,doSort , false);
        random.addEventListener('click' ,doRandom , false);
    };
    
    var removeListener = function(){
        sort.removeEventListener('click' ,doSort , false);
        random.removeEventListener('click' ,doRandom , false);
    };
    
    var doSort = function(){
         removeListener();         
         var n1,n2,displays=container.children,count=displays.length,i=0;
         //console.log(displays);
         //insertion sort          
         while(i < count){
             n1 = parseInt(displays[i].textContent,10);
                        
             for(var j=i-1 ; j > -1 ; j--){                 
                 n2 = parseInt(displays[j].textContent,10);
                 
                 if(n1 < n2){
                    //do insert
                    container.insertBefore(displays[i],displays[j]);
                    i=j;
                 }
             }
             i++
         }        
         addListener();     
    };
    
    
    var doRandom = function(){
        removeListener();   
        var displays=container.children,     
            count = displays.length;
        for(var i=0 ; i < count ; i++){
            displays[i].textContent  = Math.floor((Math.random()*100)+1);
        }
        addListener();
    };

    
    var getDisplayObject = function(){
      var displayObject = document.createElement('div');
          displayObject.className = 'rectangle201312080935';
          displayObject.textContent  = Math.floor((Math.random()*100)+1);
      return displayObject;
    };    

    init();   
})(); 
</script>