×
文章路径: Java > 算法 > 排序

计数排序CountingSort

发表于3年前(Dec 24, 2014 10:18:15 AM)  阅读 671  评论 0

分类: Java 算法 排序

标签: countingsort 计数排序

计数排序假设n个输入元素中的每一个都是介于0到k之间的整数,此处k为某个整数。

计数排序算法的基本思想是对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数。一旦有了这个信息,就可以将x直接存放到最终的输出序列的正确位置上。例如,如果输入序列中只有17个元素的值小于x的值,则x可以直接存放在输出序列的第18个位置上。当然,如果有多个元素具有相同的值时,我们不能将这些元素放在输出序列的同一个位置上,因此,上述方案还要作适当的修改。

 

package sort;

/**
 * 计数排序
 * @author lihui
 *
 */
public class CountingSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		int[] a = {2, 5, 3, 0, 2, 3, 0, 3};
		int[] a = {2, 4, 4, 1, 0};
		int[] b = countingSort(a, 5);
		for(int i=0;i<b.length;i++) {
			System.out.print(b[i]+"\t");
		}
	}

	/**
	 * 计数排序不是原地排序,需用一个新数组来保存结果
	 * 计数排序假定所有元素都是0到k之间的整数
	 * @param a 待排序数组
	 * @param b 排序后的数值
	 * @param k 最大数
	 */
	public static int[] countingSort(int[] a, int k) {
		int[] b = new int[a.length];
		//建立辅助数组c[i]表示i在数组中的个数
		int[] c = new int[k+1];
		for(int i=0;i<a.length;i++) {
			c[a[i]] = c[a[i]] + 1;
		}
		//c[i]表示a中有多少元素是<=i
		for(int i=1;i<=k;i++) {
			c[i] = c[i] + c[i-1];
		}
		//将a中的元素循环取出来,放入对应位置,每放一个c[i]中对应的数值减1
		for(int i=0;i<a.length;i++) {
			b1]-1] = a[i];
			c[a[i]]--;
		}
		return b;
	}
	
}

计数排序的时间复杂度为O(n),当然是有条件的。计数排序不是原地排序。

 

发表评论