计数排序 Counting sort
“In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. “ From Wikipedia
完整排序算法代码：https://github.com/huangliu0909/Sort-Algorithms
计数排序，有别于比较排序，不需要进行数据之间的比较、交换。适用于不同数值总数较小的序列。
首先，找到数组的最大值max和最小值min，构造一个count数组，大小为max-min+1，初始化为0.
对于原始array中的每个数a-min作为count数组的index进行计数。
调整count数组使得每个数值为这个index在result中出现的最后一个位置。
对原始array从右向左进行遍历，对每个元素a找到count数组中对应的位置填入result数组，并且将count数组中的该数值减一，因为上一个位置已经被填入了，下次被填入需要向前挪一位。
计数排序时间复杂度为$O(n)$。计数排序通常被使用为基数排序(Radix Sort)的一个步骤。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import java.util.Arrays;
public class Counting_Sort {
public static void main(String[] args) {
int[] array = new int[] {1, 0, 1, 2, 3, 6, 3, 2, 9, 8, 7, 1, 5, 2, 3};
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int a : array) if(a > max) max = a; //find max value
for(int a : array) if(a < min) min = a; //find min value
int size = max - min + 1; //the num of distinct values
int[] count = new int[size];
for(int i = 0; i < size; i ++) count[i] = 0; //initialize
for(int a : array) count[a - min] ++; //counting
for(int i = 1; i < size; i ++) count[i] += count[i - 1]; //find last index
int[] result = new int[array.length];
for(int i = array.length - 1; i >= 0; i --) {
int a = array[i];
result[count[a] - 1] = a;
count[a]--;
}
System.out.println(Arrays.toString(result));
//[0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 5, 6, 7, 8, 9]
}
}
基数排序 Radix Sort
通过数组的最大值确定位数pos的范围(max/pos != 0)，从个位(pos=1)开始根据每一位((a/pos)%10)进行计数排序，每一轮计数排序结束，pos*=10。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28import java.util.Arrays;
public class Radix_Sort {
public static void main(String[] args) {
int[] array = new int[] {123, 2, 34, 678, 345, 890, 234, 789, 23, 49, 843, 56, 234};
int max = Integer.MIN_VALUE;
for(int a : array) if(a > max) max = a; //find max value
for(int pos = 1; max/pos != 0; pos*=10) {
count_sort(array, pos);
}
System.out.println(Arrays.toString(array));
//[2, 23, 34, 49, 56, 123, 234, 234, 345, 678, 789, 843, 890]
}
public static void count_sort(int[] array, int pos) {
int[] count = new int[10];
for(int i = 0; i < 10; i ++) count[i] = 0; //initialize
for(int a : array) count[(a/pos)%10] ++; //counting
for(int i = 1; i < 10; i ++) count[i] += count[i - 1]; //find last index
int[] result = new int[array.length];
for(int i = array.length - 1; i >= 0; i --) {
int a = array[i];
result[count[(a/pos)%10] - 1] = a;
count[(a/pos)%10]--;
}
for (int i = 0; i < array.length; i++) array[i] = result[i];
}
}