算法导论云：“计数排序假设n个输入元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。当k=O(n)时，排序的运行时间是O(n)”。
百度云：“计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。”
下面用java来实现：
1 import java.util.Arrays; 2 3 public class CountSort { 4 public static void main(String[] args) { 5 String str = "ededcbcaba"; 6 char[] chs = str.toCharArray(); 7 sort(chs); 8 } 9 10 private static void sort(char[] chs) { 11 int[] c = new int[26]; 12 char[] b = new char[chs.length]; 13 for (int i = 0; i < chs.length; i++) { 14 c[chs[i] - 'a']++; 15 } 16 System.out.println(Arrays.toString(c)); 17 for (int i = 1; i < c.length; i++) { 18 c[i] = c[i - 1] + c[i]; 19 } 20 System.out.println(Arrays.toString(c)); 21 for (int i = 0; i < chs.length; i++) { 22 char tmp = b[c[chs[i] - 'a'] - 1]; 23 // 注：此判断是为了防止有重复的值，如果发现这个下标上已经有值了，那么就赋到前一个下标上去。 24 if (tmp != 0) { 25 b[c[chs[i] - 'a'] - 2] = chs[i]; 26 } else { 27 b[c[chs[i] - 'a'] - 1] = chs[i]; 28 } 29 } 30 System.out.println(Arrays.toString(b)); 31 } 32 }
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/19413.html