插值排序
插值排序（英語：Interpolation sort）或稱為直方圖排序（英語：Histogram sort）[1]是一種使用插值公式分散資料分而治之的排序演算法。插值排序也是桶排序演算法的一種變型。 [2]
插值排序遞歸算法
插值排序也是一種桶排序，排序演算法與桶排序相同，插值公式是把被排序的數字化為介於零到壹的數值，再乘以桶子的數量，得出被排序數字對應的桶子號碼，以此號碼分桶來實現桶排序。一個通用的插值公式是：
插值 = 取整數(((設算數 - 最小數) / (最大數 - 最小數)) * (桶子數量 - 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];}
}
}
};
插值排序演算法
| 插值排序 | |
|---|---|
| 概況 | |
| 類別 | 排序算法 |
| 資料結構 | 數組 |
| 複雜度 | |
| 平均時間複雜度 | |
| 最壞時間複雜度 | |
| 最優時間複雜度 | |
| 空間複雜度 | |
| 最佳解 | |
| 相關變量的定義 | |
插值排序遞迴方式運用一個記錄桶子長度的陣列對應原數列，透過操作維護長度陣列可以避免遞歸演算法因記憶體堆疊而使空間複雜度變成 ，藉由長度陣列的分段記錄可以使用次函式動態的宣告與刪除陣列的記憶體空間，使得遞歸程序得以控制所需空間複雜度在 ，包含一個動態分配記憶體的二維陣列與一個記錄長度的陣列。但是平均時間複雜度仍可維持為 的高效排序方法。 [3]
動態分配記憶體的陣列也可以由鏈表、堆棧、佇列、關聯數組、樹狀結構等實作，例如 Javascript 的陣列物件即適用。資料結構的不同關係着資料存取的速度進而影響到排序所需的時間。當被排序陣列內的數值是均勻分散近似等差級數時，插值排序的線性時間為 。 [4]
插值排序流程
- 設置一個桶子長度陣列記錄未完成排序桶子的長度。初始化放入(push)原始陣列的長度。
- [主排序]：如果桶子長度陣列清空排序完成。如果未清空執行[分桶函數]。
- [分桶函數]：從桶子長度陣列末端取出(pop)一個桶子長度執行分桶。如果最大值等於最小值該序列排序完成停止分桶。
- 設置一個二維陣列當作空桶子。依照插值分桶。
- 分桶後從不是空的桶子裏把項目逐一放回原始陣列。 並在桶子長度陣列加入(push)桶子的長度。
- 返回[主排序]。
插值排序實作
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);
}
}
}
}
};
變種
插值標簽排序
| 插值標簽排序 | |
|---|---|
| 概況 | |
| 類別 | 排序算法 |
| 資料結構 | 數組 |
| 複雜度 | |
| 平均時間複雜度 | |
| 最壞時間複雜度 | |
| 最優時間複雜度 | |
| 空間複雜度 | |
| 最佳解 | |
| 相關變量的定義 | |
插值標簽排序(Interpolation Tag Sort)是插值排序(Interpolation Sort)的變型，應用桶排序分而治之的方法,以數學插值公式將數組資料以陣列方式分散到有限數量的桶子裏,桶子再遞歸原處理程序直到完成排序。
插值標簽排序是插值排序的遞歸排序方法,為避免遞歸造成堆疊溢出使得記憶體崩潰, 而利用一個布林資料型別的標簽陣列操做遞迴次函式以釋放記憶體。所需額外記憶體的空間複雜度約等於 ，包含一個動態分配記憶體的二維陣列與一個布林資料型別的標簽陣列。除此之外關聯數組、鏈表、堆棧、佇列、樹狀結構等皆可實作成桶排序的桶子。誠如 Javascript 的陣列物件即適用於此排序方法, 資料結構的不同關係着資料存取的速度進而影響到排序所需的時間。當要被排序的陣列內的數值是均勻分佈的時候使用線性時間 。桶排序演算法並不是比較排序不受 下限的限制。插值標簽排序是桶排序的變型平均執行複雜度同為 。 [3]
插值標簽排序演算法
- 設置一個與原始陣列等量的標簽陣列，並初始化為假值。
- [主排序]判斷原始陣列所有桶子是否都已排序完成，未完成執行[分桶函數]。
- [分桶函數]找出桶子內最大最小值，如果最大值等於最小值排序完成停止分桶。
- 設置一個二維陣列當作空桶子。依照插值分桶。
- 分桶後從不是空的桶子裏把項目逐一放回原始陣列。並在標簽陣列將桶子的起始位置標記為真值。
- 返回[主排序]。
插值標簽排序實作
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
};
原地插值排序
| 原地插值排序 | |
|---|---|
| 概況 | |
| 類別 | 排序算法 |
| 資料結構 | 數組 |
| 複雜度 | |
| 平均時間複雜度 | |
| 最壞時間複雜度 | |
| 最優時間複雜度 | |
| 空間複雜度 | |
| 相關變量的定義 | |
原地插值排序是插值排序的原地算法（in-place algorithm）。原地插值排序通過插值計算交換元素完成排序；但是要排序的數組必需是算術級數，例如連續整數。原地插值排序對不重複的等差數列排序，序列從頭開始計算元素的插值，插值指向元素排序好的位置，兩者相互調換位置，遞增而行至序列結尾排序完成。計算時間複雜度為： ，最壞空間複雜度： 。
原地插值排序實作
JavaScript code:
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));
}
}
};
類似排序方法
直方圖排序 Histogram sort
直方圖排序不使用陣列物件(類似ArrayList)作桶子，而是使用一維的輔助陣列分段當作桶子。首先用插值公式敲擊桶子計算每個桶子的敲擊數量，並使用另一個陣列記錄桶子的資料數量，再把每個敲擊的數量累加，得到桶子在輔助陣列的起始位置。然後再次用插值公式把資料逐一放進桶子裏，當資料放置完畢，將輔助陣列的資料複製回原陣列，然後利用桶子的數量記錄，對每個桶子再次使用直方圖排序直到排序完成。 [5]
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];}
}
}
};
相鄰圖排序 ProxmapSort
相鄰圖排序也是使用一維的輔助陣列當作桶子，桶子分段方式與直方圖排序相同，不同的是用插值公式將資料分配到輔助陣列的桶子時，隨後使用插入排序插入資料讓資料有序，當分配資料完成時排序完成，將輔助陣列的資料複製回原陣列。 [6]
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];}
};
閃電排序 FlashSort
閃電排序不使用一維輔助陣列，而是將原始陣列視為分段的桶子，利用交換的方式將資料放入桶子。首先用插值公式計算各個點該有的資料數量，再把該數量累加得到每個點的最終位置。然後在用插值公式把資料與對應的點交換，當所有資料交換完畢，資料已經都在桶子裏，桶子是有序的所以陣列接近排序完成，當資料接近有序時使用插入排序會很快，最後使用插入排序將整個陣列完成排序。 [7]
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;
}
};
插值排序混合其他排序方法
插值排序是一種桶排序，桶排序可以混合其他排序方法完成排序，若是由桶排序與插入排序混合，亦是相當高效的排序方法。但是當數列出現一個乖離很大的數值，例如數列最大值大於次大值的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];}
}
}
};
參考
- ^ NIST Algorithm. interpolation sort. [2019-06-14]. （原始內容存檔於2019-06-09） （英語）.
Definition: See histogram sort.
- ^ en.wikipedia. Histogram sort. [2019-06-14]. （原始內容存檔於2021-02-22） （英語）.
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.
- ^ 3.0 3.1 zh.wikipedia. 桶排序. [2019-06-26]. （原始內容存檔於2020-12-05） （中文）.
平均時間複雜度
- ^ en.wikipedia. Bucket sort Average-case analysis. Wikipedia. [2019-06-14]. （原始內容存檔於2021-02-22） （英語）.
Note that if k is chosen to be , then bucket sort runs in average time, given a uniformly distributed input.
- ^ NIST Algorithm. histogram sort. [2019-11-25]. （原始內容存檔於2021-03-10） （英語）.
- ^ en.wikipedia. Proxmap sort. [2019-06-14]. （原始內容存檔於2019-07-26） （英語）.
- ^ en.wikipedia. Flashsort. [2019-06-14]. （原始內容存檔於2020-12-20） （英語）.
額外參考
[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 （頁面存檔備份，存於互聯網檔案館）
額外連結
- Interpolation Sort Algorithm--Whale Chen 2012/09/16
- 桶排序遞迴方式演算法 Bucket Sort recursive method
- 插值標簽排序演算法 Interpolation Tag Sort Algorithm
- interpolation sort (Pascal version available) （頁面存檔備份，存於互聯網檔案館）
- w3schools JavaScript Array Sort 測試平台 （頁面存檔備份，存於互聯網檔案館）