
_START_ARTICLE_
插值排序
_START_SECTION_
插值排序递归算法
_START_PARAGRAPH_
插值排序也是一种桶排序，排序算法与桶排序相同，插值公式是把被排序的数字化为介于零到壹的数值，再乘以桶子的数量，得出被排序数字对应的桶子号码，以此号码分桶来实现桶排序。一个通用的插值公式是：_NEWLINE_插值 = 取整数(((设算数- 最小数) / (最大数- 最小数)) * (桶子数量- 1))
_START_SECTION_
插值排序递归算法实作
_START_PARAGRAPH_
JavaScript code:_NEWLINE_Array.prototype.bucketSort = function(){//--edit date:2019/08/31 Taiwan--//_NEWLINE_  var start = 0;_NEWLINE_  var size = this.length;_NEWLINE_  var min = this[0];_NEWLINE_  var max = this[0]; _NEWLINE_  for (var i = 1; i < size; i++){_NEWLINE_    if (this[i] < min){min = this[i];}_NEWLINE_    else{ if(this[i] > max){max = this[i];} }_NEWLINE_  }_NEWLINE_  if (min != max){_NEWLINE_    var bucket = new Array(size);_NEWLINE_    for (var i = 0; i < size; i++){bucket[i] = new Array();}_NEWLINE_    var interpolation = 0;_NEWLINE_    for (var i = 0; i < size; i++){_NEWLINE_      interpolation = Math.floor(((this[i] - min) / (max - min)) * (size - 1));_NEWLINE_      bucket[interpolation].push(this[i]);_NEWLINE_    }_NEWLINE_    for (var i = 0; i < size; i++){_NEWLINE_      if (bucket[i].length > 1){bucket[i].bucketSort();}//遞歸_NEWLINE_      for(var j = 0; j < bucket[i].length; j++){this[start++] = bucket[i][j];}_NEWLINE_    }_NEWLINE_  }};
_START_SECTION_
插值排序实作
_START_PARAGRAPH_
JavaScript code:_NEWLINE_Array.prototype.interpolationSort = function(){ //edit date:2019/07/31_NEWLINE_  var bucketSize = new Array();_NEWLINE_  var end = this.length;_NEWLINE_  bucketSize[0] = end;_NEWLINE_  while(bucketSize.length > 0){DivideToBucket(this);}_NEWLINE__NEWLINE_  function DivideToBucket(needSortArray){_NEWLINE_    var size = bucketSize.pop();_NEWLINE_    var start = end - size;_NEWLINE_    var minimum = needSortArray[start];_NEWLINE_    var maximum = needSortArray[start];_NEWLINE_    for(i = start + 1; i < end; i++){_NEWLINE_      if(needSortArray[i] < minimum){minimum = needSortArray[i];}_NEWLINE_      else{if(needSortArray[i] > maximum){maximum = needSortArray[i];}}_NEWLINE_    }_NEWLINE_    if(minimum == maximum){end = end - size;}_NEWLINE_    else{_NEWLINE_      var interpolation = 0;_NEWLINE_      var bucket = new Array(size);_NEWLINE_      for( i = 0; i < size; i++){bucket[i] = new Array();}_NEWLINE_      for(i = start; i < end; i++){_NEWLINE_        interpolation = Math.floor(((needSortArray[i] - minimum) / (maximum - minimum)) * (size - 1));_NEWLINE_        bucket[interpolation].push(needSortArray[i]);_NEWLINE_      }_NEWLINE_      for(i = 0; i < size; i++){_NEWLINE_        if(bucket[i].length > 0){_NEWLINE_          for(j = 0; j < bucket[i].length; j++){needSortArray[start++] = bucket[i][j];}_NEWLINE_          bucketSize.push(bucket[i].length);_NEWLINE_        }_NEWLINE_      }_NEWLINE_    }_NEWLINE_  }};
_START_SECTION_
插值标签排序实作
_START_PARAGRAPH_
JavaScript code:_NEWLINE_Array.prototype.InterpolaionTagSort = function(){//Whale Chen 同意：「維基百科:CC BY-SA 3.0協議文本」編輯日：2019/08/04//_NEWLINE_  var start = 1 ;_NEWLINE_  var end = this .length;_NEWLINE_  var Tag = new Array ( end ); //Algorithm step-1_NEWLINE_  for ( i = 0 ; i < end; i ++ ){ Tag[ i ] = false ; }_NEWLINE_  Tag[0] = true;_NEWLINE_  while ( end > 0 ){ //Algorithm step-2_NEWLINE_    while ( Tag[ --start ] == false ){ }_NEWLINE_    DivideToBucket( this ); }_NEWLINE_    _NEWLINE_  function DivideToBucket( A ){_NEWLINE_    var minimum = A[ start ];_NEWLINE_    var maximum = A[ start ];_NEWLINE_    for ( i = start + 1 ; i < end; i ++ ){_NEWLINE_      if ( A[ i ] < minimum ){ minimum = A[ i ]; }_NEWLINE_      else { if ( A [ i ] > maximum ){ maximum = A[ i ]; } }_NEWLINE_    }_NEWLINE_    if ( minimum == maximum ){ end = start; }//Algorithm step-3_NEWLINE_    else { _NEWLINE_      var interpolation = 0 ;_NEWLINE_      var size = end - start;_NEWLINE_      var Bucket = new Array ( size );//Algorithm step-4_NEWLINE_      for ( i = 0 ; i < size; i ++ ){ Bucket[ i ] = new Array ( ); }_NEWLINE_      for ( i = start; i < end; i ++ ){ _NEWLINE_        interpolation = Math .floor ( ( ( A[ i ] - minimum ) / ( maximum - minimum ) ) * ( size - 1 ) );_NEWLINE_        Bucket[ interpolation ].push( A[ i ] );_NEWLINE_      }_NEWLINE_      for ( i = 0 ; i < size; i ++ ){_NEWLINE_        if ( Bucket[ i ].length > 0 ){ //Algorithm step-5_NEWLINE_          Tag[ start ] = true ; _NEWLINE_          for (j = 0 ; j < Bucket[ i ].length; j ++){ A[ start ++ ] = Bucket[ i ][ j ];}_NEWLINE_        }_NEWLINE_      }_NEWLINE_    }_NEWLINE_  }//Algorithm step-6};
_START_SECTION_
原地插值标签排序实作
_START_PARAGRAPH_
JavaScript code:_NEWLINE_Array.prototype.InPlaceTagSort = function(){ //從插值標簽排序想出原地插值標簽排序的靈感源自兩個偈頌的差別：_NEWLINE_  //神秀偈頌：身是菩提樹，心如明鏡臺；時時勤拂拭，勿使惹塵埃！_NEWLINE_  //惠能偈頌：菩提本無樹，明鏡亦非臺；本來無一物，何處惹塵埃？_NEWLINE_  var n = this.length;_NEWLINE_  var Tag = new Array( n );_NEWLINE_  for ( i = 0; i < n; i++ ){ Tag[ i ] = false; }_NEWLINE_  var min = this[ 0 ];_NEWLINE_  var max = this[ 0 ];_NEWLINE_  for ( i = 1; i < n; i++ ){ if ( this[ i ] < min ){ min = this[ i ]; }_NEWLINE_  else{ if (this[ i ] > max){ max = this[ i ]; } } } _NEWLINE_  var p = 0;_NEWLINE_  var temp = 0;_NEWLINE_  for ( i = 0; i < n; i++ ){_NEWLINE_    while ( Tag[ i ] == false ){ _NEWLINE_      p = Math.floor((( this[ i ] - min ) / ( max - min )) * ( n - 1 ));_NEWLINE_      temp = this[ i ];_NEWLINE_      this[ i ] = this[ p ]; _NEWLINE_      this[ p ] = temp;_NEWLINE_      Tag[ p ] = true; _NEWLINE_    } _NEWLINE_  } _NEWLINE_};needSortArray.InPlaceTagSort();
_START_SECTION_
插值排序混合其他排序方法与递归算法
_START_PARAGRAPH_
插值排序是一种桶排序，桶排序可以混合其他排序方法完成排序，若是由桶排序与插入排序混合，亦是相当高效的排序方法。但是当数列出现一个乖离很大的数值，例如数列最大值大于次大值的N倍时，数列分桶处理后分布情形是除了最大值以外其余元素都落入同一个桶子，紧接着第二个排序方法使用插入排序，可能会使得执行复杂度陷入，如此便失去了使用桶排序分而治之的意义与执行效能。_NEWLINE_插值排序是使用桶排序递归的方式，执行递归以后仍然使用桶排序分散数列，这样可以避免上述情形。如欲使得递归的插值排序执行复杂度陷入，则必需在整个数列呈现阶乘放大的情况，相对上数列要出现这种特殊分布情形的几率很少。
_START_SECTION_
插值排序混合插入排序实作
_START_PARAGRAPH_
JavaScript code:_NEWLINE_Array.prototype.interpolationInsertSort = function(){ //--Edit Date:2019/09/02 Taiwan--//_NEWLINE_  var start = 0;_NEWLINE_  var size = this.length;_NEWLINE_  var min = this[0];_NEWLINE_  var max = this[0]; _NEWLINE_  for (var i = 1; i < size; i++){_NEWLINE_    if (this[i] < min){min = this[i];}_NEWLINE_    else{ if(this[i] > max){max = this[i];} }_NEWLINE_  }_NEWLINE_  if (min != max){_NEWLINE_    var bucket = new Array(size);_NEWLINE_    for (var i = 0; i < size; i++){bucket[i] = new Array();}_NEWLINE_    var buckets = size - 1;_NEWLINE_    var range = max - min;_NEWLINE_    var interpolation = 0;_NEWLINE_    var insetIndex = 0;_NEWLINE_    var k = 0;_NEWLINE_    for (var i = 0; i < size; i++){_NEWLINE_      interpolation = Math.floor(((this[i] - min) / range) * buckets);_NEWLINE_      bucket[interpolation].push(this[i]);_NEWLINE_      insetIndex = 0;//項目放到對應桶子後，直接執行插入排序。_NEWLINE_      while(this[i] > bucket[interpolation][insetIndex]){insetIndex++;}_NEWLINE_      k = bucket[interpolation].length-1;_NEWLINE_      while(k > insetIndex){bucket[interpolation][k] = bucket[interpolation][k-1]; k--;}_NEWLINE_      bucket[interpolation][insetIndex] = this[i];_NEWLINE_    }_NEWLINE_    for(var i = 0; i < size; i++){_NEWLINE_      for(var j = 0; j < bucket[i].length; j++){this[start++] = bucket[i][j];}_NEWLINE_    }_NEWLINE_  }};
_START_SECTION_
额外参考
_START_PARAGRAPH_
[1] interpolationSort.html_NEWLINE_[2] histogramSort.html_NEWLINE_[3] The FlashSort Algorithm_NEWLINE_[4] Mathematical Analysis of Algorithms_NEWLINE_[5] http://www.drdobbs.com/database/the-flashsort1-algorithm/184410496