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;

	}

}