计数排序实现

原创
2014/03/03 01:02
阅读数 381

计数排序实现:

计数排序属于稳定排序,时间复杂度为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;
}

展开阅读全文
加载中

作者的其它热门文章

打赏
0
3 收藏
分享
打赏
0 评论
3 收藏
0
分享
返回顶部
顶部