计数排序实现:
计数排序属于稳定排序,时间复杂度为O(n), 主要的思路:
找出数组中小于其中某个元素element的个数i,那么该element就应该位于数组的第i+1个位置:
比如:
A为待排序数组,C为计数数组(下标对应A的各元素值,下标值为该元素值出现的个数),B存放排序后的数组,实现代码:
/**
* 计数排序
* @param A 待排序数组
* @param B 对应A排序后的数组,
* @param k A数组中最大元素
*/
public static void countingSort(int[] A, int[] B, int k){
//用于记录A中每个元素出现的次数
int[] C = new int[k];
//统计A[i]每个元素出现的次数,并放到C中A[i]的位置
for (int i=0; i<A.length; i++){
C[A[i]] += 1;
}
//求计数和
for (int i=1; i<k; i++){
C[i] = C[i] + C[i-1];
}
//整理
for (int j = A.length - 1; j >= 0; j--) {
int a = A[j];
B[C[a] - 1] = a;
C[a] -= 1;
}
}
测试代码:
int[] A = new int[]{16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
int[] B = new int[A.length];
int k = 100; //k需要被计算,这里假设一个
countingSort(A, B, k);
一个完整的实现:
public static int[] countSort(int []a){
int b[] = new int[a.length];
int max = a[0], min = a[0];
//找出最大,最小元素
for(int i : a){
if(i > max){
max = i;
}
if(i < min){
min = i;
}
}
//这里k的大小是要排序的数组中,元素大小的极值差+1
int k = max - min + 1;
int c[] = new int[k];
for(int i = 0; i < a.length; ++i){
c[a[i]-min] += 1;
}
//求计数和
for(int i = 1; i < c.length; ++i){
c[i] = c[i] + c[i-1];
}
//根据各个元素的出现次数,开始反填
for(int i = a.length-1; i >= 0; --i){
b[--c[a[i]-min]] = a[i];
}
return b;
}