排序算法笔记:计数排序 CountingSort in java
博客专区 > CheN_exe 的博客 > 博客详情
排序算法笔记:计数排序 CountingSort in java
CheN_exe 发表于4年前
排序算法笔记:计数排序 CountingSort in java
  • 发表于 4年前
  • 阅读 23
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

/**
 * 计数排序
 * 简述:
 * 		创建一个临时数组temp[max],max>=max(array).先统计array[i]的个数于temp[array[i]]上,再通过temp[]确定每一个数字的位置(算出有m个比n小的,则n就在m+1上),最后将数据串与result上.
 * 时间复杂度:
 * 		当k=O(n)时,为O(n)
 * 空间复杂度:
 * 		O(n)
 * 优点:
 * 		时间复杂度几乎为最低
 * 缺点:
 * 		对数组内容要求较多:1.全为自然数;2.若数字太大,则需要过多额外空间.
 * 可改进:
 * 		通过把100当做1的方式,可以实现两位小数的排序,不过太浪费空间
 * @author CheN
 *
 */
public class CountingSort {
	public static int[] asc( int[] array ){
		return sort(array);
	}
	
	private static int[] sort( int[] array ){
		int max = 0;//max为某个整数,该整数大于array中最大的整数
		for( int i = 0 ; i < array.length ; i++ ){
			if( max < array[i]){
				max = array[i];
			}
		}
		int[] result = new int[array.length] , temp = new int[max];
//		for( int i = 0 ; i < k ; i++ ){
//			temp[i] = 0;
//		}
		// 计数
		for( int i = 0 ; i < array.length ; i++ ){
			temp[array[i]] = temp[array[i]]+1;
		}
		// 统计比第i位小的数字个数的总和,即统计数组中每一位之前的值之和。
		for( int i = 1 ; i < max ; i++ ){
			temp[i] = temp[i]+temp[i-1];
		}
		// 将临时数组中的不为零的位,分别按照它的值的数量,填入result数组中,从而完成排序
		for( int i = array.length - 1 ; i >= 0 ; i-- ){
			result[temp[array[i]]-1] = array[i];
			temp[array[i]] = temp[array[i]]-1;
		}
		return result;
	}
}


若有错误或不妥之处,敬请谅解并指点。

共有 人打赏支持
粉丝 3
博文 31
码字总数 16641
×
CheN_exe
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: