查看“︁插值排序”︁的源代码

{{copyedit|time=2019-06-13T00:58:13+00:00}}
'''插值排序'''（{{lang-en|Interpolation sort}}）或稱為直方圖排序（{{lang-en|Histogram sort}}）<ref>{{Cite web |url = https://xlinux.nist.gov/dads/HTML/interpolationSort.html |title = interpolation sort |author = NIST Algorithm |language = en |quote = Definition: See histogram sort. |access-date = 2019-06-14 |archive-date = 2019-06-09 |archive-url = https://web.archive.org/web/20190609030408/https://xlinux.nist.gov/dads/HTML/interpolationSort.html |dead-url = no }}</ref>是一種使用[[插值]]公式分散資料[[分而治之]]的[[排序演算法]]。插值排序也是[[桶排序]]演算法的一種變型。
<ref>{{Cite web |url = https://en.wikipedia.org/wiki/Bucket_sort#Histogram_sort |title = Histogram sort |author = en.wikipedia |language = en |quote = "Another variant of bucket sort known as histogram sort or counting sort adds an initial pass that counts the number of elements that will fall into each bucket using a count array. Using this information, the array values can be arranged into a sequence of buckets in-place by a sequence of exchanges, leaving no space overhead for bucket storage." |access-date = 2019-06-14 |archive-date = 2021-02-22 |archive-url = https://web.archive.org/web/20210222114142/https://en.wikipedia.org/wiki/Bucket_sort#Histogram_sort |dead-url = no }}</ref>

==插值排序遞歸算法==
插值排序也是一種桶排序，排序演算法與桶排序相同，插值公式是把被排序的數字化為介於零到壹的數值，再乘以桶子的數量，得出被排序數字對應的桶子號碼，以此號碼分桶來實現桶排序。一個通用的插值公式是：

插值 = 取整數(((設算數 - 最小數) / (最大數 - 最小數)) * (桶子數量 - 1))

===插值排序遞歸算法流程===
{{Infobox Algorithm
|name=插值排序遞歸算法
|class=[[排序算法]]
|image=
|data=[[数组]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math> 
|average-time=<math>O(n+k)</math>
|space=<math>O(n^2)</math>
|optimal= <math>O(n)</math>
}} 
# 尋訪序列，找出最大值與最小值，如果相等排序完成。
# 設置一個定量的陣列當作空桶子。
# 尋訪序列，把項目一個一個放到插值對應的桶子去。
# 對每個不是空的桶子再次進行桶排序。
# 從不是空的桶子裡把項目再放回原來的序列中。

===插值排序遞歸算法實作===
JavaScript code:
<syntaxhighlight lang="javascript">
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];}
    }
  }
};  
</syntaxhighlight>

==插值排序演算法==
{{Infobox Algorithm
|name=插值排序
|class=[[排序算法]]
|image=
|data=[[数组]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math> 
|average-time=<math>O(n+k)</math>
|space=<math>O(n*3)</math>
|optimal= <math>O(n)</math>
}} 
插值排序遞迴方式運用一個記錄桶子長度的陣列對應原數列，透過操作維護長度陣列可以避免[[遞歸]]演算法因[[記憶體]][[堆疊]]而使[[空間複雜度]]變成 <math>O(n ^ 2)</math>，藉由長度陣列的分段記錄可以使用次[[函式]]動態的宣告與刪除陣列的記憶體空間，使得遞歸程序得以控制所需空間複雜度在 <math>O(3n)</math>，包含一個動態分配記憶體的二維陣列與一個記錄長度的陣列。但是平均[[時間複雜度]]仍可維持為 <math>O(n + k)</math>的高效[[排序]]方法。
<ref name="#1">{{Cite web 
|url = https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F 
|title = 桶排序 
|author = zh.wikipedia 
|language = 中文 
|quote = 平均時間複雜度<math>O(n+k)</math> 
|access-date = 2019-06-26 
|archive-date = 2020-12-05 
|archive-url = https://web.archive.org/web/20201205222609/https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F 
|dead-url = no 
}}</ref>

動態分配記憶體的[[陣列]]也可以由[[鏈表]]、[[堆棧]]、[[佇列]]、[[关联数组]]、[[樹狀結構]]等實作，例如 [[Javascript]] 的陣列物件即適用。[[資料結構]]的不同關係著資料存取的速度進而影響到排序所需的時間。當被排序陣列內的數值是均勻分散近似[[等差級數]]時，插值排序的[[線性時間]]為 <math>O(n)</math>。
<ref>{{Cite web |url = https://en.wikipedia.org/wiki/Bucket_sort#Average-case_analysis |title = Bucket sort Average-case analysis |author = en.wikipedia |publisher = Wikipedia |language = en |quote = Note that if k is chosen to be <math>k = n</math> , then bucket sort runs in <math>O(n)</math> average time, given a uniformly distributed input. |access-date = 2019-06-14 |archive-date = 2021-02-22 |archive-url = https://web.archive.org/web/20210222114142/https://en.wikipedia.org/wiki/Bucket_sort#Average-case_analysis |dead-url = no }}</ref>

===插值排序流程===
#設置一個桶子長度陣列記錄未完成排序桶子的長度。初始化放入(push)原始陣列的長度。
#[主排序]：如果桶子長度陣列清空排序完成。如果未清空執行[分桶函數]。
#[分桶函數]：從桶子長度陣列末端取出(pop)一個桶子長度執行分桶。如果最大值等於最小值該序列排序完成停止分桶。
#設置一個二維陣列當作空桶子。依照插值分桶。
#分桶後從不是空的桶子裡把項目逐一放回原始陣列。 並在桶子長度陣列加入(push)桶子的長度。
#返回[主排序]。

===插值排序實作===
JavaScript code:
<syntaxhighlight lang="javascript">
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);
        }
      }
    }
  }
};
</syntaxhighlight>

==變種==
===插值標簽排序===
{{Infobox Algorithm
|name=插值標簽排序
|class=[[排序算法]]
|image=
|data=[[数组]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math> 
|average-time=<math>O(n+k)</math>
|space=<math>O(2n + (n)bits)</math>
|optimal= <math>O(n)</math>
}} 
'''插值標簽排序'''(Interpolation Tag Sort)是插值排序(Interpolation Sort)的變型，應用桶排序分而治之的方法,以數學插值公式將數組資料以陣列方式分散到有限數量的桶子裡,桶子再[[遞歸]]原處理程序直到完成排序。

插值標簽排序是插值排序的遞歸排序方法,為避免遞歸造成堆疊溢出使得記憶體崩潰, 而利用一個[[布林]][[資料型別]]的標簽陣列操做遞迴次[[函式]]以釋放記憶體。所需額外記憶體的[[空間複雜度]]約等於 <math>2n+(n)bits</math>，包含一個動態分配記憶體的二維[[陣列]]與一個布林資料型別的標簽陣列。除此之外[[關聯數組]]、[[鏈表]]、[[堆棧]]、[[佇列]]、[[樹狀結構]]等皆可實作成桶排序的桶子。誠如 [[Javascript]] 的陣列物件即適用於此排序方法, 資料結構的不同關係著資料存取的速度進而影響到排序所需的時間。當要被排序的陣列內的數值是均勻分布的時候使用線性時間 <math> \Theta(n) </math>。桶[[排序演算法]]並不是比較排序不受 <math>O(n log n)</math> 下限的限制。插值標簽排序是[[桶排序]]的變型平均執行複雜度同為 <math>O(n + k)</math>。
<ref name="#1"/>

====插值標簽排序演算法====
#設置一個與原始陣列等量的標簽陣列，並初始化為假值。
#[主排序]判斷原始陣列所有桶子是否都已排序完成，未完成執行[分桶函數]。
#[分桶函數]找出桶子內最大最小值，如果最大值等於最小值排序完成停止分桶。
#設置一個二維陣列當作空桶子。依照插值分桶。
#分桶後從不是空的桶子裡把項目逐一放回原始陣列。並在標簽陣列將桶子的起始位置標記為真值。
#返回[主排序]。

====插值標簽排序實作====
JavaScript code:
<syntaxhighlight lang="javascript">
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
};
</syntaxhighlight>

===原地插值排序===
{{Infobox Algorithm
|name=原地插值排序
|class=[[排序算法]]
|image=
|data=[[数组]]
|time=<math>O(n)</math> 
|best-time=<math>O(n)</math>
|average-time=<math>O(n)</math>
|space=<math>O(1)</math>
}} 

原地插值排序是插值排序的[[原地算法]]（in-place algorithm）。原地插值排序通過插值計算交換元素完成排序；但是要排序的數組必需是算術級數，例如連續整數。原地插值排序對不重複的等差數列排序，序列從頭開始計算元素的插值，插值指向元素排序好的位置，兩者相互調換位置，遞增而行至序列結尾排序完成。計算時間複雜度為：<math>O(n)</math>，最壞空間複雜度：<math>O(1)</math>。
 
====原地插值排序實作====
JavaScript code:
<syntaxhighlight lang="javascript">
Array.prototype.in_placeInterpolationSort = function()
{//Date:2019/11/15 Arithmetic progression only//
  var n = this.length;
  var min = this[0];
  var max = this[0];
  for (var i = 1; i < n; i++){
    if ( this[i] < min ){min = this[i];}
    else{if (this[i] > max){max = this[i];}}
  } 
  var position = n;
  var temp = 0;
  for (var i = 0; i < n; i++){
    position = Math.floor(((this[i] - min) / (max - min)) * (n - 1));
    while (i != position ){ 
      temp = this[position];
      this[position] = this[i]; 
      this[i] = temp;
      position = Math.floor(((this[i] - min) / (max - min)) * (n - 1));
    } 
  } 
};
</syntaxhighlight>

==類似排序方法==
===直方圖排序 Histogram sort===
直方圖排序不使用陣列物件(類似ArrayList)作桶子，而是使用一維的輔助陣列分段當作桶子。首先用插值公式敲擊桶子計算每個桶子的敲擊數量，並使用另一個陣列記錄桶子的資料數量，再把每個敲擊的數量累加，得到桶子在輔助陣列的起始位置。然後再次用插值公式把資料逐一放進桶子裏，當資料放置完畢，將輔助陣列的資料複製回原陣列，然後利用桶子的數量記錄，對每個桶子再次使用直方圖排序直到排序完成。
<ref>{{cite web |url = https://xlinux.nist.gov/dads/HTML/histogramSort.html |title = histogram sort |author = NIST Algorithm |language = en |access-date = 2019-11-25 |archive-date = 2021-03-10 |archive-url = https://web.archive.org/web/20210310090129/https://xlinux.nist.gov/dads/HTML/histogramSort.html |dead-url = no }}</ref>
<syntaxhighlight lang="javascript">
Array.prototype.histogramSort = function()
{//-- Edit date:2019/11/07 Taiwan --//
  var end = this.length;
  var sortedArray = new Array(end);
  var interpolation = new Array(end);
  var hitCount = new Array(end);
  var divideSize = new Array();
  divideSize[0] = end;
  while (divideSize.length > 0){distribute(this);} 
  //Repeat the distribute function instead of recursion
  function distribute(A){
    var size = divideSize.pop();
    var start = end - size;
    var min = A[start];
    var max = A[start];
    for (var i = start + 1; i < end; i++){
      if (A[i] < min){min = A[i];}
      else{if (A[i] > max){max = A[i];}}
    }
    if (min == max){end = end - size;}
    else{
      for (var i = start; i < end; i++){hitCount[i] = 0;}
      for (var i = start; i < end; i++){
        interpolation[i] = start + Math.floor(((A[i] - min ) / (max - min ) ) * (size - 1 ));
        hitCount[interpolation[i]]++;
      }
      for (var i = start; i < end; i++){
        if(hitCount[i] > 0){divideSize.push(hitCount[i]);}
      }
      hitCount[end-1] = end - hitCount[end-1];
      for (var i = end-1; i > start; i--){
        hitCount[i-1] = hitCount[i] - hitCount[i-1];
      }
      for (var i = start; i < end; i++){
        sortedArray[hitCount[interpolation[i]]] = A[i];
        hitCount[interpolation[i]]++;
      }
      for (var i = start; i < end; i++){A[i] = sortedArray[i];}
    }
  }
};
</syntaxhighlight>
===相鄰圖排序 ProxmapSort===
相鄰圖排序也是使用一維的輔助陣列當作桶子，桶子分段方式與直方圖排序相同，不同的是用插值公式將資料分配到輔助陣列的桶子時，隨後使用插入排序插入資料讓資料有序，當分配資料完成時排序完成，將輔助陣列的資料複製回原陣列。
<ref>{{Cite web |url = https://en.wikipedia.org/wiki/Proxmap_sort |title = Proxmap sort |author = en.wikipedia |language = en |access-date = 2019-06-14 |archive-date = 2019-07-26 |archive-url = https://web.archive.org/web/20190726205018/https://en.wikipedia.org/wiki/Proxmap_sort |dead-url = no }}</ref>
<syntaxhighlight lang="javascript">
Array.prototype.ProxmapSort = function()
{//-- Edit date:2019/11/11 Taiwan --//
  var start = 0;
  var end = this.length;
  var size = end - start;
  var sortedArray = new Array(end);
  var interpolation = new Array(end);
  var hitCount = new Array(end);
  
  for (var i = start; i < end; i++){hitCount[i] = 0;}
  var min = this[start];
  var max = this[start];
  for (var i = start+1; i < end; i++){
    if (this[i] < min){min = this[i];}
    else{if (this[i] > max){max = this[i];}}
  }
  for (var i = start; i < end; i++){
    interpolation[i] = Math.floor(((this[i] - min ) / (max - min )) * (size - 1));
    hitCount[interpolation[i]]++;
  }
  hitCount[end-1] = end - hitCount[end-1];
  for (var i = end-1; i > start; i--){
    hitCount[i-1] = hitCount[i] - hitCount[i-1];
  }
//insertion sort this[i] to correct position
  var insertIndex = 0;
  var insertStart = 0;
  for (var i = start; i < end; i++){
    insertIndex = hitCount[interpolation[i]];
    insertStart = insertIndex;
    while(sortedArray[insertIndex] != null){insertIndex++;}
    while(insertIndex > insertStart && this[i] < sortedArray[insertIndex-1]){
      sortedArray[insertIndex] = sortedArray[insertIndex-1];
      insertIndex--;
    }
    sortedArray[insertIndex] = this[i];
  }
  for (var i = start; i < end; i++){this[i] = sortedArray[i];}
};
</syntaxhighlight>
===閃電排序 FlashSort===
閃電排序不使用一維輔助陣列，而是將原始陣列視為分段的桶子，利用交換的方式將資料放入桶子。首先用插值公式計算各個點該有的資料數量，再把該數量累加得到每個點的最終位置。然後在用插值公式把資料與對應的點交換，當所有資料交換完畢，資料已經都在桶子裏，桶子是有序的所以陣列接近排序完成，當資料接近有序時使用插入排序會很快，最後使用插入排序將整個陣列完成排序。
<ref>{{Cite web |url = https://en.wikipedia.org/wiki/Flashsort |title = Flashsort |author = en.wikipedia |language = en |access-date = 2019-06-14 |archive-date = 2020-12-20 |archive-url = https://web.archive.org/web/20201220053921/https://en.wikipedia.org/wiki/Flashsort |dead-url = no }}</ref>
<syntaxhighlight lang="javascript">
Array.prototype.FlashSort = function()
{//-- Edit date:2019/11/24 Taiwan--//
  var start = 0;
  var end = this.length;
  var size = end - start;
  var hitCount = new Array(end);
  var min = this[start];
  var max = this[start];
  for (var i = start + 1; i < end; i++){
    if (this[i] < min){min = this[i];}
    else{if (this[i] > max){max = this[i];}}
  }    
  for (var i = start; i < end; i++){hitCount[i] = 0;}
  var interpolation = 0;
  for (var i = start; i < end; i++){
    interpolation = Math.floor(((this[i] - min ) / (max - min ) ) * (size - 1 ));
    hitCount[interpolation]++;
  }
  hitCount[0] = hitCount[0] - 1;
  for (var i = 1; i < end; i++){
    hitCount[i] = hitCount[i] + hitCount[i-1];
  }
  var temp = 0;
  var tag = new Array(end);
  for (var i = start; i < end; i++){tag[i] = false;}
  for (var i = start; i < end; i++){
    while(tag[i] == false){
      interpolation = Math.floor(((this[i] - min) / (max - min)) * (size - 1));
      tag[hitCount[interpolation]] = true;
      temp = this[hitCount[interpolation]];
      this[hitCount[interpolation]] = this[i];
      this[i] = temp;
      hitCount[interpolation]--;
    }
  }
  //insertionSort
  var key = 0;
  var j = 0;
  for(var i = 1; i < end; i++){
    key = this[i];
    j = i -1;
    while((j >= 0) && (key < this[j])){
      this[j+1] = this[j];
      j--;
    }
    this[j+1] = key;
  }
};
</syntaxhighlight>
===插值排序混合其他排序方法===
插值排序是一種桶排序，桶排序可以混合其他排序方法完成排序，若是由[[桶排序]]與[[插入排序]]混合，亦是相當高效的排序方法。但是當數列出現一個乖離很大的數值，例如數列最大值大於次大值的N倍時，數列分桶處理後分佈情形是除了最大值以外其餘元素都落入同一個桶子，緊接著第二個排序方法使用插入排序，可能會使得執行複雜度陷入<math>O(n^2)</math>，如此便失去了使用桶排序分而治之的意義與執行效能。

插值排序是使用桶排序[[遞歸]]的方式，執行遞歸以後仍然使用桶排序分散數列，這樣可以避免上述情形。如欲使得遞歸的插值排序執行複雜度陷入<math>O(n^2)</math>，則必需在整個數列呈現階乘放大的情況，相對上數列要出現這種特殊分佈情形的機率很少。

====插值排序混合插入排序流程====
{{Infobox Algorithm
|name=插值插入排序
|class=[[排序算法]]
|image=
|data=[[数组]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math> 
|average-time=<math>O(n+k)</math>
|space=<math>O(2n)</math>
|optimal= <math>O(n)</math>
}} 
# 尋訪序列，找出最大值與最小值，如果相等排序完成。
# 設置一個定量的陣列當作空桶子。
# 尋訪序列，並且把項目放到對應的桶子去。
# 在桶子內把該項目直接進行插入排序。
# 從不是空的桶子裡把項目再放回原來的序列中。

====插值排序混合插入排序實作====
JavaScript code:
<syntaxhighlight lang="javascript">
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];}
    }
  }
};  

</syntaxhighlight>

==參考==
{{reflist}}

==額外參考==
[1] [http://xlinux.nist.gov/dads/HTML/interpolationSort.html interpolationSort.html] {{Wayback|url=http://xlinux.nist.gov/dads/HTML/interpolationSort.html |date=20190609030408 }}

[2] [http://xlinux.nist.gov/dads/HTML/histogramSort.html histogramSort.html] {{Wayback|url=http://xlinux.nist.gov/dads/HTML/histogramSort.html |date=20210310090129 }}

[3] [http://www.neubert.net/FSOIntro.html The FlashSort Algorithm] {{Wayback|url=http://www.neubert.net/FSOIntro.html |date=20201109030701 }}

[4] [https://web.archive.org/web/20160304084930/http://oai.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=AD0726158 Mathematical Analysis of Algorithms]

[5] http://www.drdobbs.com/database/the-flashsort1-algorithm/184410496 {{Wayback|url=http://www.drdobbs.com/database/the-flashsort1-algorithm/184410496 |date=20200210080810 }}

==額外連結==
*[https://plus.google.com/u/0/116595705228888301771/posts/icXYXWiVKU8 Interpolation Sort Algorithm--Whale Chen 2012/09/16]
*[https://www.facebook.com/WhaleChen.1969/posts/2252485301532790 桶排序遞迴方式演算法 Bucket Sort recursive method ]
*[https://www.facebook.com/WhaleChen.1969/posts/2131925703588751 插值標簽排序演算法 Interpolation Tag Sort Algorithm]
*[http://users.dcc.uchile.cl/~rbaeza/handbook/algs/4/416.sort.c.html interpolation sort (Pascal version available)] {{Wayback|url=http://users.dcc.uchile.cl/~rbaeza/handbook/algs/4/416.sort.c.html |date=20170317182320 }}
*[https://www.w3schools.com/js/tryit.asp?filename=tryjs_array_sort2 w3schools JavaScript Array Sort 測試平台] {{Wayback|url=https://www.w3schools.com/js/tryit.asp?filename=tryjs_array_sort2 |date=20210321070011 }}


{{排序算法表}}

[[Category:排序算法]]