🐈 📉 🍯 估计的分配计数-最常用的是重新分类 🤛 🎄 🔗

彼此之间或多或少的不同种类的数量保证超过一百种。其中有一些算法的子组，它们彼此之间的差异极小，这与某些一般的主要思想相吻合。实际上，在不同的年份中，不同的人重新提出了相同的分类，只是在基本信息上并不相同。

这样的算法思想比其他思想更常见。

每个元素大约在应放置数组的位置输入。事实证明，数组几乎是有序的 。对其应用按插入排序（对于处理几乎有序的数组最有效）或使用相同算法递归处理局部无序区域。

本文是在EDISON的支持下撰写的，EDISON为各种任务开发了广泛的解决方案：从在线尝试在多品牌商店的衣服上试穿的程序，到内河与海上船只之间的LED传输系统。

我们喜欢算法理论！ ;-)

要评估大约要放置该元素的位置，需要找出它与数组的平均元素有多少不同。为此，您需要知道最小和最大元素的值，以及数组的大小。

排序后的数组应该具有真正的随机数据。此方法的所有发明者都得出相同的公式：

k是数组中元素A （ i ）应该位于的近似位置
min ， max-数组A中最小和最大元素的值
大小 -数组A中的元素数

这是一个大致的想法。让我们看看该算法一次又一次地诞生。

排序所罗门王::所罗门排序

此方法（及其漂亮的名称）由 V2008n 的用户于大约5年前提出。一切都有时间，“扔石头的时间和收集石头的时间”（传道书中所罗门王的话）-在算法中，这正是发生的情况。首先，借助公式，我们将元素分散在数组中的所需位置。由于公式给出的不是精确的位置，而是近似的位置，因此，值彼此接近的几个元素会同时声明某些位置。这些局部元素组按插入顺序排序，然后按最终顺序组装。

插值排序

再次引用同一位作者的话：“阳光下没有新事物。” 维基百科描述了通过插值进行的排序，可疑地使人联想到所罗门排序。每个“石头堆”都是一个小的附加动态数组，具有相似重要性的元素位于其中。主要区别在于，在“散布石头”之后，这些局部未排序的元素组不是通过插入进行排序，而是通过插值对自己进行排序（递归或循环）。

有序数组是离散数据集，可以将其视为某个未知函数的已知值的有限集。实际上，从计算数学的角度来看，近似分布是插值。

JavaScript插值排序-环回

Array.prototype.interpolationSort = function() { var divideSize = new Array(); var end = this.length; divideSize[0] = end; while(divideSize.length > 0) {divide(this);} function divide(A) { var size = divideSize.pop(); var start = end - size; var min = A[start]; var max = A[start]; var temp = 0; 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 { var p = 0; var bucket = new Array(size); for(var i = 0; i < size; i++) {bucket[i] = new Array();} for(var i = start; i < end; i++) { p = Math.floor(((A[i] - min) / (max - min)) * (size - 1)); bucket[p].push(A[i]); } for(var i = 0; i < size; i++) { if(bucket[i].length > 0) { for(var j = 0; j < bucket[i].length; j++) {A[start++] = bucket[i][j];} divideSize.push(bucket[i].length); } } } } };

JavaScript插值排序-递归版本

 Array.prototype.bucketSort = function() { 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();} //Recursion for(var j = 0; j < bucket[i].length; j++) {this[start++] = bucket[i][j];} } } };

直方图排序::直方图排序

这是通过插值进行排序的优化，它可以计算属于本地未排序组的元素的数量。此计数使您可以将未排序的项目直接插入到结果数组中（而不是将它们分组到单独的小数组中）。

JavaScript条形排序

 Array.prototype.histogramSort = function() { 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);} 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];} } } };

插值标签排序

为了进一步优化开销，在此建议不要记住未排序组中具有相似重要性的元素的数量，而应仅使用True / False标志标记这些组的开始。 True表示该子组已经排序，而False表示尚未排序。

JavaScript标记的插值排序

 Array.prototype.InterpolaionTagSort = function() { var end = this.length; if(end > 1) { var start = 0 ; var Tag = new Array(end); //Algorithm step-1 for(var i = 0; i < end; i++) {Tag[i] = false;} Divide(this); } //Algorithm step-2 while(end > 1) { while(Tag[--start] == false){} //Find the next bucket's start Divide(this); } function Divide(A) { 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 = start; } else { //Algorithm step-3 Start to be the next bucket's end var interpolation = 0; var size = end - start; var Bucket = new Array(size);//Algorithm step-4 for(var i = 0; i < size; i++) {Bucket[i] = new Array();} for(var i = start; i < end; i++) { interpolation = Math.floor(((A[i] - min) / (max - min)) * (size - 1)); Bucket[interpolation].push(A[i]); } for(var i = 0; i < size; i++) { if(Bucket[i].length > 0) {//Algorithm step-5 Tag[start] = true; for(var j = 0; j < Bucket[i].length; j++) {A[start++] = Bucket[i][j];} } } } }//Algorithm step-6 };

插值标签排序（就地）

如果数组中元素的值没有重复且不均匀分布（粗略地说-如果排序后的数据像算术级数一样），那么您可以一次性进行排序，就地排序，而无需将元素移动到中间数组中。

在JavaScript中按插值排序并使用标签（就地）

 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; } } };

Flash Sort :: Flashsort

曾几何时，我写过有关排序的文章，它是诺伊伯特（Neubert）生物物理学教授于1998年发明的。

教授建议将元素分布到几个单独的类中（类成员资格由元素的大小确定）。考虑到这一点，公式如下所示：

该公式表示的是m-分配数组元素的类数，而不是Size（数组大小）。该公式不会计算元素应该抛出的数组中的键，而是元素所属的类号。

这种排序还不错，因为这样可以节省更多内存。元素的重新分布就位。仅类的本地化是分开存储的（好吧，如果从不同的角度看，则属于特定类的元素数是分开存储的）。

好吧，其余都是同一首歌。

用Java排序Flash

 /** * FlashSort.java - integer version * Translation of Karl-Dietrich Neubert's algorithm into Java by * Rosanne Zhang */ class FlashSort { static int n; static int m; static int[] a; static int[] l; /* constructor @param size of the array to be sorted */ public static void flashSort(int size) { n = size; generateRandomArray(); long start = System.currentTimeMillis(); partialFlashSort(); long mid = System.currentTimeMillis(); insertionSort(); long end = System.currentTimeMillis(); // print the time result System.out.println("Partial flash sort time : " + (mid - start)); System.out.println("Straight insertion sort time: " + (end - mid)); } /* Entry point */ public static void main(String[] args) { int size = 0; if (args.length == 0) { usage(); System.exit(1); } try { size = Integer.parseInt(args[0]); } catch (NumberFormatException nfe) { usage(); System.exit(1); } FlashSort.flashSort(size); } /* Print usage */ private static void usage() { System.out.println(); System.out.println("Usage: java FlashSort n "); System.out.println(" n is size of array to sort"); } /* Generate the random array */ private static void generateRandomArray() { a = new int[n]; for(int i=0; i < n; i++) { a[i] = (int)(Math.random() * 5 * n); } m = n / 20; l = new int[m]; } /* Partial flash sort */ private static void partialFlashSort() { int i = 0, j = 0, k = 0; int anmin = a[0]; int nmax = 0; for(i=1; i < n; i++) { if (a[i] < anmin) anmin=a[i]; if (a[i] > a[nmax]) nmax=i; } if(anmin == a[nmax]) return; double c1 = ((double)m - 1) / (a[nmax] - anmin); for(i=0; i < n; i++) { k= (int) (c1 * (a[i] - anmin)); l[k]++; } for(k=1; k < m; k++) { l[k] += l[k - 1]; } int hold = a[nmax]; a[nmax] = a[0]; a[0] = hold; int nmove = 0; int flash; j = 0; k = m - 1; while(nmove < n - 1) { while(j > (l[k] - 1)) { j++; k = (int) (c1 * (a[j] - anmin)); } flash = a[j]; while(!(j == l[k])) { k = (int) (c1 * (flash - anmin)); hold = a[l[k] - 1]; a[l[k] - 1] = flash; flash = hold; l[k]--; nmove++; } } } /* Straight insertion sort */ private static void insertionSort() { int i, j, hold; for(i = a.length - 3; i >= 0; i--) { if(a[i + 1] < a[i]) { hold = a[i]; j = i; while (a[j + 1] < hold) { a[j] = a[j + 1]; j++; } a[j] = hold; } } } /* For checking sorting result and the distribution */ private static void printArray(int[] ary) { for(int i=0; i < ary.length; i++) { if((i + 1) % 10 ==0) { System.out.println(ary[i]); } else { System.out.print(ary[i] + " "); } System.out.println(); } } }

近似排序:: Proxmap排序

这种排序是这里提到的最古老的排序；它是由加利福尼亚大学的Thomas Standish教授于1980年提出的。在外观上似乎有很大不同，但是如果仔细观察，一切都是一样的。

该算法以命中（hit）的概念进行操作- 命中某个值，其值与数组的某些元素接近。
为了确定数组元素是否为命中，将近似函数应用于该元素。

Standish教授对实数数组进行了排序。逼近功能是将实数四舍五入为整数。
也就是说，例如，如果数组包含元素2.8、2、2.1、2.6等。那么这些数字将大打折扣。

一般程序：

我们对每个元素应用一个近似函数，确定哪个命中对应于下一个元素。
因此，对于每个匹配，我们可以计算与此匹配相对应的元素数。
知道所有匹配项的元素数量后，我们确定数组中匹配项的位置（左侧边界）。
知道匹配的本地化后，我们确定每个元素的本地化。
确定元素的本地化之后，我们尝试将其插入数组中的位置。如果该位置已被占用，那么我们将向右移动邻居（如果元素小于它们），以便为该元素腾出空间。或在右边插入元素本身（如果它大于相邻元素）。

作为一种近似函数，您可以根据数组中数据的一般性质分配任何一个。在这种排序的现代实现中，命中率通常不是通过小数部分确定的，而是使用我们最喜欢的公式确定的。

JavaScript近似排序

 Array.prototype.ProxmapSort = function() { var start = 0; var end = this.length; var A2 = new Array(end); var MapKey = 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];} } } //Optimization 1.Save the MapKey[i]. for (var i = start; i < end; i++) { MapKey[i] = Math.floor(((this[i] - min ) / (max - min)) * (end - 1)); hitCount[MapKey[i]]++; } //Optimization 2.ProxMaps store in the hitCount. hitCount[end-1] = end - hitCount[end - 1]; for(var i = end-1; i > start; i--){ hitCount[i-1] = hitCount[i] - hitCount[i - 1]; } //insert A[i]=this[i] to A2 correct position var insertIndex = 0; var insertStart = 0; for(var i = start; i < end; i++){ insertIndex = hitCount[MapKey[i]]; insertStart = insertIndex; while(A2[insertIndex] != null) {insertIndex++;} while(insertIndex > insertStart && this[i] < A2[insertIndex - 1]) { A2[insertIndex] = A2[insertIndex - 1]; insertIndex--; } A2[insertIndex] = this[i]; } for(var i = start; i < end; i++) {this[i] = A2[i];} };

哈希排序插入排序::哈希排序

好吧，我们将以bobbyKdas habraiser六年前建议的算法结束我们的评论。这是一种混合算法，其中除了分布和插入之外，还添加了合并。

将数组递归地分成两半，直到在某些步骤中，半子数组的大小达到最小大小（作者不超过500个元素）。
在最低的递归级别上，将熟悉的算法应用于每个半子数组-使用相同的公式，子数组内部会发生近似分布，并通过插入局部未排序的部分进行排序。
在将子阵列的两半排列后，它们合并。
当通过递归级别爬到最顶部时，当原始数组由两个半部分合并时，将重复点3（排序的半部分子数组的合并）。

按Java中的哈希插入排序

 import java.util.Arrays; import java.util.Date; import java.util.Random; public class HashSort { //    static int SOURCELEN = 1000000; int source[] = new int[SOURCELEN]; //        int quick[] = new int[SOURCELEN]; //     static int SORTBLOCK = 500; static int k = 3; //  static int TMPLEN = (SOURCELEN < SORTBLOCK * k) ? SORTBLOCK * k : SOURCELEN; int tmp[] = new int[TMPLEN]; //    static int MIN_VAL = 10; static int MAX_VAL = 1000000; int minValue = 0; int maxValue = 0; double hashKoef = 0; //      public void randomize() { int i; Random rnd = new Random(); for(i=0; i<SOURCELEN; i++) { int rndValue = MIN_VAL + ((int)(rnd.nextDouble()*((double)MAX_VAL-MIN_VAL))); source[i] = rndValue; } } //         - public void findMinMax(int startIndex, int endIndex) { int i; minValue = source[startIndex]; maxValue = source[startIndex]; for(i=startIndex+1; i<=endIndex; i++) { if( source[i] > maxValue) { maxValue = source[i]; } if( source[i] < minValue) { minValue = source[i]; } } hashKoef = ((double)(k-1)*0.9)*((double)(endIndex-startIndex)/((double)maxValue-(double)minValue)); } // (  - )      public void stickParts(int startIndex, int mediana, int endIndex) { int i=startIndex; int j=mediana+1; int k=0; //      -    while(i<=mediana && j<=endIndex) { if(source[i]<source[j]) { tmp[k] = source[i]; i++; } else { tmp[k] = source[j]; j++; } k++; } //     -      if( i>mediana ) { while(j<=endIndex) { tmp[k] = source[j]; j++; k++; } } //     -      if(j>endIndex) { while(i<=mediana) { tmp[k] = source[i]; i++; k++; } } System.arraycopy(tmp, 0, source, startIndex, endIndex-startIndex+1); } //        //         boolean shiftRight(int index) { int endpos = index; while( tmp[endpos] != 0) { endpos++; if(endpos == TMPLEN) return false; } while(endpos != index ) { tmp[endpos] = tmp[endpos-1]; endpos--; } tmp[endpos] = 0; return true; } //-    public int hash(int value) { return (int)(((double)value - (double)minValue)*hashKoef); } //        public void insertValue(int index, int value) { int _index = index; //  ,    //            - while(tmp[_index] != 0 && tmp[_index] <= value) { _index++; } //       ,    if( tmp[_index] != 0) { shiftRight(_index);//      } tmp[_index] = value;//  -   } //        public void extract(int startIndex, int endIndex) { int j=startIndex; for(int i=0; i<(SORTBLOCK*k); i++) { if(tmp[i] != 0) { source[j] = tmp[i]; j++; } } } //   public void clearTMP() { if( tmp.length < SORTBLOCK*k) { Arrays.fill(tmp, 0); } else { Arrays.fill(tmp, 0, SORTBLOCK*k, 0); } } //  public void hashingSort(int startIndex, int endIndex) { //1.          findMinMax(startIndex, endIndex); //2.    clearTMP(); //3.       - for(int i=startIndex; i<=endIndex; i++) { insertValue(hash(source[i]), source[i]); } //4.         extract(startIndex, endIndex); } //         public void sortPart(int startIndex, int endIndex) { //    500,   - if((endIndex - startIndex) <= SORTBLOCK ) { hashingSort(startIndex, endIndex); return; } //  > 500         int mediana = startIndex + (endIndex - startIndex) / 2; sortPart(startIndex, mediana);//    sortPart(mediana+1, endIndex);//    stickParts(startIndex, mediana, endIndex);//   -   } //       public void sort() { sortPart(0, SOURCELEN-1); } public static void main(String[] args) { HashSort hs = new HashSort(); hs.randomize(); hs.sort(); } }