特性

在线性时间内排序

Java实现

package mairuis.algorithm.sort; /** * 计数排序 * * @author Mairuis * @date 2019/5/25 */ public class CountingSort extends Sort { public static int[] countingSort(int[] a) { int[] c = new int[a.length]; //用无限循环模拟goto，实现超容就扩充数组然后从头开始 for (; ; ) { for (int anA : a) { if (c.length <= anA) { c = new int[c.length << 2]; break; } c[anA] += 1; } break; } for (int i = 1; i < c.length; i += 1) { c[i] += c[i - 1]; } int[] b = new int[a.length]; for (int anA : a) { b[c[anA] -1] = anA; c[anA] -= 1; } return b; } public static int[] sort(int[] data) { return countingSort(data); } public static void main(String[] args) { int[] data = generalIntegers(10); printArray(data); for (int i : sort(data)) { System.out.println(i); } } }