一.计数排序
算法原理
1.找出待排序的数组中最大和最小的元素
2.统计数组中每个值为i的元素出现的次数，存入数组countArray的第i项
3.对所有的计数累加（从countArray中的第一个元素开始，每一项和前一项相加）
4.反向遍历原数组：将每个元素i放在新数组的第countArray(i)项，每放一个元素就将countArray(i)减去1
实例分析
输入{3, 4, 3, 2, 1}，最大是4，数组长度是5。
建立计数数组{0, 0, 0, 0}。
遍历输入数组：
{3, 4, 3, 2, 1} -> {0, 0, 1, 0}
{3, 4, 3, 2, 1} -> {0, 0, 1, 1}
{3, 4, 3, 2, 1} -> {0, 0, 2, 1}
{3, 4, 3, 2, 1} -> {0, 1, 2, 1}
{3, 4, 3, 2, 1} -> {1, 1, 2, 1}
计数数组现在是{1, 1, 2, 1}，我们现在把它写回到输入数组里：
{0, 1, 2, 1} -> {1, 4, 3, 2, 1}
{o, o, 2, 1} -> {1, 2, 3, 2, 1}
{o, o, 1, 1} -> {1, 2, 3, 2, 1}
{o, o, o, 1} -> {1, 2, 3, 3, 1}
{o, o, o, o} -> {1, 2, 3, 3, 4}
这样就排好序了。
Java实现
/**
* 计数排序
*
* @param array
*/
public static void countSort(int[] array) {
if (array.length <= 1) {
return;
}
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < array.length; i++) {
max = Math.max(max, array[i]);
min = Math.min(min, array[i]);
}
int[] countArray = new int[max - min + 1];
for (int i = 0; i < array.length; i++) {
countArray[array[i] - min] += 1;
}
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
int[] temp = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
int value = array[i];
int position = countArray[value - min] - 1;
temp[position] = value;
countArray[value - min] -= 1;
}
for (int i = 0; i < array.length; i++) {
array[i] = temp[i];
}
}
效率分析
时间：O(n + k)，n是输入数组长度，k是最大数于最小数的差。
空间：O(n + k)，n是输入数组长度，k是最大数于最小数的差。
适用范围
适用于序列取值比较集中的情况，例如适用于对某个公司的员工的年龄进行排序
二.计数排序的优化
算法实现思路
利用数据挖掘对序列进行简单的数据归约，根据归约后映射的值把序列分治为比较均匀的序列，再使用计数排序对子序列进行排序，从而在保证时间效率的情况下减少了空间的分配。
实例分析
输入{10, 32, 14, 34, 56, 10000028, 10000034, 10000037, 10000089, 10000023}，最小值是10，最大值是10000089，数组的长度是10，最大值、最小值的差为10000079，下面进行计算：
10：（10 - 10）/ 10000079 * 10 = 0；
32：（32 - 10）/ 10000079 * 10 = 0；
.
.
.
10000089：（10000089 - 10）/ 10000079 * 10 = 10；
10000023：（10000023 - 10）/ 10000079 * 10 = 9；
进而根据计算结果把序列划分为三个子序列如下：
0=[10, 32, 14, 34, 56]；
9=[10000028, 10000034, 10000037, 10000023],；
10=[10000089]
再分别进行计数排序得到：
0=[10, 14, 32, 34, 56]；
9=[10000023, 10000028, 10000034, 10000037]；
10=[10000089]
最后把序列进行合并可得到有序的序列{10, 14, 32, 34, 56, 10000023, 10000028, 10000034, 10000037, 10000089}.
Java实现
/**
* 优化空间的计数排序
*
* @param array
*/
public static void reduced(int[] array) {
if (array.length <= 1) {
return;
}
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < array.length; i++) {
max = Math.max(array[i], max);
min = Math.min(array[i], min);
}
int difference = max - min;
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < array.length; i++) {
set.add(Integer.valueOf((int) ((float)(array[i] - min) / difference * array.length)));
}
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
for (Integer key : set) {
map.put(key, new ArrayList<>());
}
for (int i = 0; i < array.length; i++) {
map.get(Integer.valueOf((int)((float)(array[i] - min) / difference * array.length))).add(Integer.valueOf(array[i]));
}
Iterator<Map.Entry<Integer, ArrayList<Integer>>> it = map.entrySet().iterator();
int start = 0, end = -1, index = 0;
while (it.hasNext()) {
start = end + 1;
Map.Entry<Integer, ArrayList<Integer>> entry = it.next();
for (Integer integer : entry.getValue()) {
end++;
array[index++] = integer;
}
countSortOne(array, start, end);
}
}
/**
* 一趟计数排序
*
* @param array
*/
public static void countSortOne(int[] array, int start, int end) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = start; i <= end; i++) {
max = Math.max(max, array[i]);
min = Math.min(min, array[i]);
}
int[] countArray = new int[max - min + 1];
for (int i = start; i <= end; i++) {
countArray[array[i] - min] += 1;
}
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
int[] temp = new int[end - start + 1];
for (int i = end; i >= start; i--) {
int value = array[i];
int position = countArray[value - min] - 1;
temp[position] = value;
countArray[value - min] -= 1;
}
for (int i = start, j = 0; i <= end; i++, j++) {
array[i] = temp[j];
}
}
效率分析
时间：O(n + k)，n是输入数组长度，k是最大数于最小数的差。
空间：小于O(n + k)，n是输入数组长度，k是最大数于最小数的差。
适用范围
当序列最小、最大值比较分散的时候，并且还在某一个区间集聚现象的时候可以采用可以采用此种排序。
网友评论