插值排序

插值排序（interpolation sort）或称为直方图排序（histogram sort）。 [1] 是一种使用插值公式分散资料分而治之的排序算法。插值排序也是桶排序算法的一种变型。 [2]

插值排序递归算法

插值排序也是一种桶排序，排序算法与桶排序相同，插值公式是把被排序的数字化为介于零到壹的数值，再乘以桶子的数量，得出被排序数字对应的桶子号码，以此号码分桶来实现桶排序。一个通用的插值公式是：

插值 = 取整数(((设算数 -­ 最小数) / (最大数 -­ 最小数)) * (桶子数量 - 1))

插值排序递归算法流程

插值排序递归算法
概况
类别排序算法
数据结构数组
复杂度
平均时间复杂度 
最坏时间复杂度 
最优时间复杂度 
空间复杂度 
最佳解 
相关变量的定义
  1. 寻访序列，找出最大值与最小值，如果相等排序完成。
  2. 设置一个定量的阵列当作空桶子。
  3. 寻访序列，把项目一个一个放到插值对应的桶子去。
  4. 对每个不是空的桶子再次进行桶排序。
  5. 从不是空的桶子里把项目再放回原来的序列中。

插值排序递归算法实作

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]

插值排序流程

  1. 设置一个桶子长度阵列记录未完成排序桶子的长度。初始化放入(push)原始阵列的长度。
  2. [主排序]：如果桶子长度阵列清空排序完成。如果未清空执行[分桶函数]。
  3. [分桶函数]：从桶子长度阵列末端取出(pop)一个桶子长度执行分桶。如果最大值等于最小值该序列排序完成停止分桶。
  4. 设置一个二维阵列当作空桶子。依照插值分桶。
  5. 分桶后从不是空的桶子里把项目逐一放回原始阵列。 并在桶子长度阵列加入(push)桶子的长度。
  6. 返回[主排序]。

插值排序实作

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]

插值标签排序算法

  1. 设置一个与原始阵列等量的标签阵列，并初始化为假值。
  2. [主排序]判断原始阵列所有桶子是否都已排序完成，未完成执行[分桶函数]。
  3. [分桶函数]找出桶子内最大最小值，如果最大值等于最小值排序完成停止分桶。
  4. 设置一个二维阵列当作空桶子。依照插值分桶。
  5. 分桶后从不是空的桶子里把项目逐一放回原始阵列。并在标签阵列将桶子的起始位置标记为真值。
  6. 返回[主排序]。

插值标签排序实作

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倍时，数列分桶处理后分布情形是除了最大值以外其余元素都落入同一个桶子，紧接着第二个排序方法使用插入排序，可能会使得执行复杂度陷入 ，如此便失去了使用桶排序分而治之的意义与执行效能。

插值排序是使用桶排序递归的方式，执行递归以后仍然使用桶排序分散数列，这样可以避免上述情形。如欲使得递归的插值排序执行复杂度陷入 ，则必需在整个数列呈现阶乘放大的情况，相对上数列要出现这种特殊分布情形的几率很少。

插值排序混合插入排序流程

插值插入排序
概况
类别排序算法
数据结构数组
复杂度
平均时间复杂度 
最坏时间复杂度 
最优时间复杂度 
空间复杂度 
最佳解 
相关变量的定义
  1. 寻访序列，找出最大值与最小值，如果相等排序完成。
  2. 设置一个定量的阵列当作空桶子。
  3. 寻访序列，并且把项目放到对应的桶子去。
  4. 在桶子内把该项目直接进行插入排序。
  5. 从不是空的桶子里把项目再放回原来的序列中。

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

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. ^ NIST Algorithm. interpolation sort. [2019-06-14]. （原始内容存档于2019-06-09） （英语）. Definition: See histogram sort. 
  2. ^ 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. ^ 3.0 3.1 zh.wikipedia. 桶排序. [2019-06-26]. （原始内容存档于2020-12-05） （中文）. 平均时间复杂度  
  4. ^ 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. 
  5. ^ NIST Algorithm. histogram sort. [2019-11-25]. （原始内容存档于2021-03-10） （英语）. 
  6. ^ en.wikipedia. Proxmap sort. [2019-06-14]. （原始内容存档于2019-07-26） （英语）. 
  7. ^ 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 （页面存档备份，存于互联网档案馆）

额外连结