算法说明

若领图排序是分布排序的一种。

个人理解，若领图排序算是桶排序+计数排序的变异版，桶排序计数排序理解了，那么若领图排序理解起来就会比较容易。区别其实就是存储中间值的方式做了调整……

话说，这个代码我写的很烂很吃力，而且写好几个小时才写好，再次证明我的资质真的很差哟。。。

好了，结合代码大概说一下流程，其实主要是希望将来我自己再看到后能很快的回忆出思路。。。

1、找出待排数组的最大值（20-25行代码）。

2、根据最大值，建立计数数组，并对待排数组每个值进行计数（28-31行代码）（这个计数的过程其实就是分桶的过程，桶的大小根据你数字的实际情况去分， 我的桶就是去除小数部分的整数为一桶~）。

3、建立位置数组，记录根据计数数组，得出待排数组每个数字最终排序后的开始索引位置（例如1.1f，最终排序后会出现在索引1处，所以arrayPosition[1]=2。 大家将值代入一下就知道了，与计数排序合并计数器其实是一个道理）（35-44行代码）。

4、根据位置数组进行排序。 注意子数组使用的是插入排序来写入到arrayResult中的（所谓子数组，就是，例如位置1时，里边的子数组就是1.2f,1.1f,1.8f）（49-77行代码）

5、结束。。。

 

代码

使用的是java

package hark.sort.distributionsort;import java.util.Arrays;/* * 若领图排序 */public class ProxmapSort {	public static void main(String[] args) {		float[] arrayData = { 6.7f, 5.9f, 8.4f, 1.2f, 7.3f, 3.7f, 11.5f, 1.1f,				4.8f, 0.4f, 10.5f, 6.1f, 1.8f };		float[] arrayResult = ProxmapSortMethod(arrayData);		for (float integer : arrayResult) {			System.out.print(integer);			System.out.print(" ");		}	}	public static float[] ProxmapSortMethod(float[] arrayData) {		float maxNum = 0;		for (int i = 0; i < arrayData.length; i++) {			if (arrayData[i] > maxNum) {				maxNum = arrayData[i];			}		}		// 计数数组，记录数字出现的次数		int[] arrayHitCount = new int[(int) maxNum + 1];		for (int i = 0; i < arrayData.length; i++) {			arrayHitCount[(int) arrayData[i]]++;		}		//System.out.println(Arrays.toString(arrayHitCount));		// 位置数组， 记录当前索引下的数字的起始位置		int[] arrayPosition = new int[(int) maxNum + 1];		int index = 0;		for (int i = 0; i < arrayHitCount.length; i++) {			if (arrayHitCount[i] > 0) {				arrayPosition[i] = index;				index = arrayHitCount[i] + index;			} else {				arrayPosition[i] = -1;			}		}		//System.out.println(Arrays.toString(arrayPosition));		// 根据位置数组，将排序好的数据存储至结果数组。		// 注：位置中的子数组使用的是插入排序		float[] arrayResult = new float[arrayData.length];		int pos;		float value, temp = 0;		for (int i = 0; i < arrayData.length; i++) {			value = arrayData[i];			pos = arrayPosition[(int) value];			if (pos >= 0) {				if (arrayResult[pos] > 0f) {					while (pos < arrayData.length) {						if (arrayResult[pos] == 0) // 如果arrayResult中值为0，则直接写入						{							arrayResult[pos] = value;							break;						} else if (arrayResult[pos] > value) // 如果arrayResult大于要比较的值，则进行，并且往后移动						{							temp = arrayResult[pos];							arrayResult[pos] = value;							value = temp;							pos++;						} else {							pos++;						}					}				} else {					arrayResult[pos] = value;				}			}		}		return arrayResult;	}}

　　

 

 

 

 

参考