插值排序

插值排序递归算法

插值排序也是一种桶排序，排序算法与桶排序相同，插值公式是把被排序的数字化为介于零到壹的数值，再乘以桶子的数量，得出被排序数字对应的桶子号码，以此号码分桶来实现桶排序。一个通用的插值公式是：
插值 = 取整数(((设算数- 最小数) / (最大数- 最小数)) * (桶子数量- 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