希爾和堆排序

//希爾排序(插入)
Array.prototype.shellSort = function(){
  var increment = this.length;
  console.info('初始化步長：'+increment);
  var temp,j;
  do{
    increment = parseInt(increment/3)+1;
    console.info('步長變?yōu)椋?+increment);
    for (var i = increment; i < this.length; i++) {
      console.info('對比 第'+i+'個元素:'+this[i]+',第'+(i-increment)+'個元素:'+
        this[i-increment]);
      if(this[i]<this[i-increment]){
        temp = this[i];
        for(j = i-increment;j>=0&&temp<this[j];j-=increment){
          console.info('賦值 第'+(j+increment)+'個元素'+this[j+increment]
            +'賦值為第'+j+'元素'+this[j]);
          this[j+increment] = this[j];
        }
        this[j+increment] = temp;
        console.info('賦值 第'+(j+increment)+'個元素'+this[j+increment]
          +'賦值為第'+i+'元素'+temp);
      }
    }
  }
  while(increment>1);
}
//堆排序
//調整函數(shù)
Array.prototype.headAdjust = function(pos, len){
  //將當前節(jié)點值進行保存
  var swap = this[pos];
  //定位到當前節(jié)點的左邊的子節(jié)點
  var child = pos * 2 + 1;
  //遞歸光督，直至沒有子節(jié)點為止
  while(child < len){
    //如果當前節(jié)點有右邊的子節(jié)點阳距，并且右子節(jié)點較大的場合，采用右子節(jié)點
    //和當前節(jié)點進行比較
    if(child + 1 < len && this[child] < this[child + 1]){
      child += 1;
    }
    //比較當前節(jié)點和最大的子節(jié)點结借，小于則進行值交換筐摘，交換后將當前節(jié)點定位
    //于子節(jié)點上
    if(this[pos] < this[child]){
      this[pos] = this[child];
      pos = child;
      child = pos * 2 + 1;
    }
    else{
      break;
    }
    this[pos] = swap;
  }
}

//構建堆
Array.prototype.buildHeap = function(){
  //從最后一個擁有子節(jié)點的節(jié)點開始，將該節(jié)點連同其子節(jié)點進行比較船老，
  //將最大的數(shù)交換與該節(jié)點,交換后咖熟，再依次向前節(jié)點進行相同交換處理，
  //直至構建出大頂堆（升序為大頂努隙，降序為小頂）
  for(var i=parseInt(this.length/2); i>=0; i--){
    this.headAdjust(i, this.length);
  }
}

Array.prototype.heapSort = function(){
  //構建堆
  this.buildHeap();
  //從數(shù)列的尾部開始進行調整
  for(var i=this.length-1; i>0; i--){
    //堆頂永遠是最大元素球恤，故，將堆頂和尾部元素交換荸镊，將
    //最大元素保存于尾部咽斧，并且不參與后面的調整
    var swap = this[i];
    this[i] = this[0];
    this[0] = swap;
    //進行調整，將最大）元素調整至堆頂
    this.headAdjust(0, i);
  }
}
var a1 = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('希爾排序before: ' + a1);
a1.shellSort();
console.log('希爾排序after: ' + a1);
var a2 = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('堆排序before: ' + a2);
a2.heapSort();
console.log('堆排序after: ' + a2);

希爾排序before: 3,1,5,7,2,4,9,6,10,8
初始化步長：10
步長變?yōu)椋?
對比 第4個元素:2,第0個元素:3
賦值 第4個元素2賦值為第0元素3
賦值 第0個元素2賦值為第4元素2
對比 第5個元素:4,第1個元素:1
對比 第6個元素:9,第2個元素:5
對比 第7個元素:6,第3個元素:7
賦值 第7個元素6賦值為第3元素7
賦值 第3個元素6賦值為第7元素6
對比 第8個元素:10,第4個元素:3
對比 第9個元素:8,第5個元素:4
步長變?yōu)椋?
對比 第2個元素:5,第0個元素:2
對比 第3個元素:6,第1個元素:1
對比 第4個元素:3,第2個元素:5
賦值 第4個元素3賦值為第2元素5
賦值 第2個元素3賦值為第4元素3
對比 第5個元素:4,第3個元素:6
賦值 第5個元素4賦值為第3元素6
賦值 第3個元素4賦值為第5元素4
對比 第6個元素:9,第4個元素:5
對比 第7個元素:7,第5個元素:6
對比 第8個元素:10,第6個元素:9
對比 第9個元素:8,第7個元素:7
步長變?yōu)椋?
對比 第1個元素:1,第0個元素:2
賦值 第1個元素1賦值為第0元素2
賦值 第0個元素1賦值為第1元素1
對比 第2個元素:3,第1個元素:2
對比 第3個元素:4,第2個元素:3
對比 第4個元素:5,第3個元素:4
對比 第5個元素:6,第4個元素:5
對比 第6個元素:9,第5個元素:6
對比 第7個元素:7,第6個元素:9
賦值 第7個元素7賦值為第6元素9
賦值 第6個元素7賦值為第7元素7
對比 第8個元素:10,第7個元素:9
對比 第9個元素:8,第8個元素:10
賦值 第9個元素8賦值為第8元素10
賦值 第8個元素10賦值為第7元素9
賦值 第7個元素8賦值為第9元素8
希爾排序after: 1,2,3,4,5,6,7,8,9,10
堆排序before: 3,1,5,7,2,4,9,6,10,8
堆排序after: 1,2,3,4,5,6,7,8,9,10
[Finished in 0.1s]

快速排序

function quickSort(arr){
    //如果數(shù)組<=1,則直接返回
    if(arr.length<=1){
        return arr;
    }
    var pivotIndex=Math.floor(arr.length/2);
    //找基準躬存，并把基準從原數(shù)組刪除
    var pivot=arr.splice(pivotIndex,1)[0];
    //定義左右數(shù)組
    var left=[];
    var right=[];
    //比基準小的放在left张惹，比基準大的放在right
    for(var i=0;i<arr.length;i++){
        if(arr[i]<=pivot){
            left.push(arr[i]);
        }
        else{
        right.push(arr[i]);
        }
    }
    //遞歸
    return quickSort(left).concat([pivot],quickSort(right));
}
var a1 = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('排序before: ' + a1);
a1 = quickSort(a1);
console.log('排序after: ' + a1);

排序before: 3,1,5,7,2,4,9,6,10,8
排序after: 1,2,3,4,5,6,7,8,9,10

歸并排序

function merge(left,right) {
    var result = [];
    while(left.length>0&&right.length>0){
        if(left[0]<right[0]){
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    return result.concat(left).concat(right);
}
function mergeSort(arr){
    if(arr.length==1){
        return arr;
    }
    var mid = Math.floor(arr.length/2);
    var left = arr.slice(0,mid);
    var right = arr.slice(mid);
    return merge(mergeSort(left),mergeSort(right))
}
var a1 = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('排序before: ' + a1);
a1 = mergeSort(a1);
console.log('排序after: ' + a1);

排序before: 3,1,5,7,2,4,9,6,10,8
排序after: 1,2,3,4,5,6,7,8,9,10
[Finished in 0.1s]