1 //排序算法
  2 window.onload = function(){
  3     var array = [0,1,2,44,4,
  4                 324,5,65,6,6,
  5                 34,4,5,6,2,
  6                 43,5,6,62,43,
  7                 5,1,4,51,56,
  8                 76,7,7,2,1,
  9                 45,4,6,7,8];
 10     //var array = [4,2,5,1,0,3];
 11     array = sorting.shellSort(array);
 12     alert(array);
 13 }
 14 
 15 var sorting = {
 16     //利用sort方法进行排序
 17     systemSort: function(arr){
 18         return arr.sort(function(a,b){
 19             return a-b;
 20         });
 21     },
 22 
 23     //冒泡排序
 24     bubbleSort: function(arr){
 25         var len=arr.length, tmp;
 26         for(var i=0;i<len-1;i++){
 27             for(var j=0;j<len-1-i;j++){
 28                 if(arr[j]>arr[j+1]){
 29                     tmp = arr[j];
 30                     arr[j] = arr[j+1];
 31                     arr[j+1] = tmp;
 32                 }
 33             }
 34         }
 35         return arr;
 36     },
 37 
 38     //快速排序
 39     quickSort: function(arr){
 40         var low=0, high=arr.length-1;
 41         sort(low,high);
 42         function sort(low, high){
 43             if(low<high){
 44                 var mid = (function(low, high){
 45                     var tmp = arr[low];
 46                     while(low<high){
 47                         while(low<high&&arr[high]>=tmp){
 48                             high--;
 49                         }
 50                         arr[low] = arr[high];
 51                         while(low<high&&arr[low]<=tmp){
 52                             low++;
 53                         }
 54                         arr[high] = arr[low];
 55                     }
 56                     arr[low] = tmp;
 57                     return low;
 58                 })(low, high);
 59                 sort(low, mid-1);
 60                 sort(mid+1,high);
 61             }
 62         }
 63         return arr;
 64     },
 65 
 66     //插入排序
 67     insertSort: function(arr){
 68         var len = arr.length;
 69         for(var i=1;i<len;i++){
 70             var tmp = arr[i];
 71             for(var j=i-1;j>=0;j--){
 72                 if(tmp<arr[j]){
 73                     arr[j+1] = arr[j];
 74                 }else{
 75                     arr[j+1] = tmp;
 76                     break;
 77                 }
 78             }
 79         }
 80         return arr;
 81     },
 82 
 83     //希尔排序
 84     shellSort: function(arr){
 85         console.log(arr);
 86         var h = 1;
 87         while(h<=arr.length/3){
 88             h = h*3+1;  //O(n^(3/2))by Knuth,1973
 89         }
 90         for( ;h>=1;h=Math.floor(h/3)){
 91             for(var k=0;k<h;k++){
 92                 for(var i=h+k;i<arr.length;i+=h){
 93                     for(var j=i;j>=h&&arr[j]<arr[j-h];j-=h){
 94                         var tmp = arr[j];
 95                         arr[j] = arr[j-h];
 96                         arr[j-h] = tmp;
 97                     }
 98                 }
 99             }
100         }
101         return arr;
102     }
103 }