插值排序

插值排序遞歸算法

插值排序也是一種桶排序，排序演算法與桶排序相同，插值公式是把被排序的數字化為介於零到壹的數值，再乘以桶子的數量，得出被排序數字對應的桶子號碼，以此號碼分桶來實現桶排序。一個通用的插值公式是：
插值 = 取整數(((設算數 - 最小數) / (最大數 - 最小數)) * (桶子數量 - 1))

插值排序遞歸算法實作

JavaScript code:
Array.prototype.bucketSort = function(){//--edit date:2019/08/31 Taiwan--//
  var start = 0;
  var size = this.length;
  var min = this[0];
  var max = this[0]; 
  for (var i = 1; i < size; i++){
    if (this[i] < min){min = this[i];}
    else{ if(this[i] > max){max = this[i];} }
  }
  if (min != max){
    var bucket = new Array(size);
    for (var i = 0; i < size; i++){bucket[i] = new Array();}
    var interpolation = 0;
    for (var i = 0; i < size; i++){
      interpolation = Math.floor(((this[i] - min) / (max - min)) * (size - 1));
      bucket[interpolation].push(this[i]);
    }
    for (var i = 0; i < size; i++){
      if (bucket[i].length > 1){bucket[i].bucketSort();}//遞歸
      for(var j = 0; j < bucket[i].length; j++){this[start++] = bucket[i][j];}
    }
  }};

插值排序實作

JavaScript code:
Array.prototype.interpolationSort = function(){ //edit date:2019/07/31
  var bucketSize = new Array();
  var end = this.length;
  bucketSize[0] = end;
  while(bucketSize.length > 0){DivideToBucket(this);}

  function DivideToBucket(needSortArray){
    var size = bucketSize.pop();
    var start = end - size;
    var minimum = needSortArray[start];
    var maximum = needSortArray[start];
    for(i = start + 1; i < end; i++){
      if(needSortArray[i] < minimum){minimum = needSortArray[i];}
      else{if(needSortArray[i] > maximum){maximum = needSortArray[i];}}
    }
    if(minimum == maximum){end = end - size;}
    else{
      var interpolation = 0;
      var bucket = new Array(size);
      for( i = 0; i < size; i++){bucket[i] = new Array();}
      for(i = start; i < end; i++){
        interpolation = Math.floor(((needSortArray[i] - minimum) / (maximum - minimum)) * (size - 1));
        bucket[interpolation].push(needSortArray[i]);
      }
      for(i = 0; i < size; i++){
        if(bucket[i].length > 0){
          for(j = 0; j < bucket[i].length; j++){needSortArray[start++] = bucket[i][j];}
          bucketSize.push(bucket[i].length);
        }
      }
    }
  }};

插值標簽排序實作

JavaScript code:
Array.prototype.InterpolaionTagSort = function(){//Whale Chen 同意：「維基百科:CC BY-SA 3.0協議文本」編輯日：2019/08/04//
  var start = 1 ;
  var end = this .length;
  var Tag = new Array ( end ); //Algorithm step-1
  for ( i = 0 ; i < end; i ++ ){ Tag[ i ] = false ; }
  Tag[0] = true;
  while ( end > 0 ){ //Algorithm step-2
    while ( Tag[ --start ] == false ){ }
    DivideToBucket( this ); }
    
  function DivideToBucket( A ){
    var minimum = A[ start ];
    var maximum = A[ start ];
    for ( i = start + 1 ; i < end; i ++ ){
      if ( A[ i ] < minimum ){ minimum = A[ i ]; }
      else { if ( A [ i ] > maximum ){ maximum = A[ i ]; } }
    }
    if ( minimum == maximum ){ end = start; }//Algorithm step-3
    else { 
      var interpolation = 0 ;
      var size = end - start;
      var Bucket = new Array ( size );//Algorithm step-4
      for ( i = 0 ; i < size; i ++ ){ Bucket[ i ] = new Array ( ); }
      for ( i = start; i < end; i ++ ){ 
        interpolation = Math .floor ( ( ( A[ i ] - minimum ) / ( maximum - minimum ) ) * ( size - 1 ) );
        Bucket[ interpolation ].push( A[ i ] );
      }
      for ( i = 0 ; i < size; i ++ ){
        if ( Bucket[ i ].length > 0 ){ //Algorithm step-5
          Tag[ start ] = true ; 
          for (j = 0 ; j < Bucket[ i ].length; j ++){ A[ start ++ ] = Bucket[ i ][ j ];}
        }
      }
    }
  }//Algorithm step-6};

原地插值標簽排序實作

JavaScript code:
Array.prototype.InPlaceTagSort = function(){ //從插值標簽排序想出原地插值標簽排序的靈感源自兩個偈頌的差別：
  //神秀偈頌：身是菩提樹，心如明鏡臺；時時勤拂拭，勿使惹塵埃！
  //惠能偈頌：菩提本無樹，明鏡亦非臺；本來無一物，何處惹塵埃？
  var n = this.length;
  var Tag = new Array( n );
  for ( i = 0; i < n; i++ ){ Tag[ i ] = false; }
  var min = this[ 0 ];
  var max = this[ 0 ];
  for ( i = 1; i < n; i++ ){ if ( this[ i ] < min ){ min = this[ i ]; }
  else{ if (this[ i ] > max){ max = this[ i ]; } } } 
  var p = 0;
  var temp = 0;
  for ( i = 0; i < n; i++ ){
    while ( Tag[ i ] == false ){ 
      p = Math.floor((( this[ i ] - min ) / ( max - min )) * ( n - 1 ));
      temp = this[ i ];
      this[ i ] = this[ p ]; 
      this[ p ] = temp;
      Tag[ p ] = true; 
    } 
  } 
};needSortArray.InPlaceTagSort();

插值排序混合其他排序方法與遞歸算法

插值排序是一種桶排序，桶排序可以混合其他排序方法完成排序，若是由桶排序與插入排序混合，亦是相當高效的排序方法。但是當數列出現一個乖離很大的數值，例如數列最大值大於次大值的N倍時，數列分桶處理後分布情形是除了最大值以外其餘元素都落入同一個桶子，緊接著第二個排序方法使用插入排序，可能會使得執行複雜度陷入，如此便失去了使用桶排序分而治之的意義與執行效能。
插值排序是使用桶排序遞歸的方式，執行遞歸以後仍然使用桶排序分散數列，這樣可以避免上述情形。如欲使得遞歸的插值排序執行複雜度陷入，則必需在整個數列呈現階乘放大的情況，相對上數列要出現這種特殊分布情形的機率很少。

插值排序混合插入排序實作

JavaScript code:
Array.prototype.interpolationInsertSort = function(){ //--Edit Date:2019/09/02 Taiwan--//
  var start = 0;
  var size = this.length;
  var min = this[0];
  var max = this[0]; 
  for (var i = 1; i < size; i++){
    if (this[i] < min){min = this[i];}
    else{ if(this[i] > max){max = this[i];} }
  }
  if (min != max){
    var bucket = new Array(size);
    for (var i = 0; i < size; i++){bucket[i] = new Array();}
    var buckets = size - 1;
    var range = max - min;
    var interpolation = 0;
    var insetIndex = 0;
    var k = 0;
    for (var i = 0; i < size; i++){
      interpolation = Math.floor(((this[i] - min) / range) * buckets);
      bucket[interpolation].push(this[i]);
      insetIndex = 0;//項目放到對應桶子後，直接執行插入排序。
      while(this[i] > bucket[interpolation][insetIndex]){insetIndex++;}
      k = bucket[interpolation].length-1;
      while(k > insetIndex){bucket[interpolation][k] = bucket[interpolation][k-1]; k--;}
      bucket[interpolation][insetIndex] = this[i];
    }
    for(var i = 0; i < size; i++){
      for(var j = 0; j < bucket[i].length; j++){this[start++] = bucket[i][j];}
    }
  }};

額外參考

[1] interpolationSort.html
[2] histogramSort.html
[3] The FlashSort Algorithm
[4] Mathematical Analysis of Algorithms
[5] http://www.drdobbs.com/database/the-flashsort1-algorithm/184410496