当前位置:网站首页 > 更多 > 涨姿势 > 正文

[每日一学] 计数排序——蓝桥杯培训

作者:CC下载站 日期:2020-04-29 00:00:00 浏览:75 分类:涨姿势

B站视频演示地址:https://www.bilibili.com/video/BV1GW411H7Cs/

概念:计数排序是一个非基于比较的排序算法,而是利用数组下标来确定元素的正确位置。用辅助数组对数组中出现的数字技术,元素转下标,下标转元素。

假设元素均大于等于0,一次扫描原数组,将元素值K记录在辅助数组的K位上。


1,基础版计数排序

假定20个随机整数的值如下:

9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9,7,9

创建一个辅助数组(长度为最大值+1)

先遍历这个无序的随机数列,每一个整数按照其值对号入座,对应数组下标的元素进行加1操作。

比如第一个整数是9,那么数组下标为9的元素加1:

第二个整数是3,那么数组下标为3的元素加1:

继续遍历数列并修改数组。。。。。。

最终,数列遍历完毕时,数组的状态如下:

遍历数组,输出数组元素的下标值,元素的值是几,就输出几次:

0,1,1,2,3,3,3,4,4,5,5,6,7,7,8,9,9,9,9,10

publicstaticvoidcountSort1(int[]arr){
		intmax=arr[0];
		for(inti:arr){
			if(i>max){
				max=i;
			}
		}
		int[]countarr=newint[max+1];
		for(intj:countarr){
			countarr[j]++;
		}
		intcurrent=0;
		for(inti=0;i<countarr.length;i++){
			while(countarr[i]>0){
				arr[current]=i;
				countarr[i]--;
				current++;
			}
		}
	}

2,改进版:

	publicstaticvoidcountSort(int[]arr){
		//找到arr的最大值和最小值
		intmin=arr[0];
		intmax=arr[0];
		for(inti:arr){
			if(i<min){
				min=i;
			}
			if(i>max){
				max=i;
			}
		}
		//创建计数数组
		int[]countArr=newint[max-min+1];
		for(intj:countArr){
			countArr[j-min]++;
		}
		//定义指针
		intcurrent=0;
		//回填
		for(inti=0;i<countArr.length;i++){
			while(countArr[i]>0){
				arr[current]=i+min;
				current++;

			}
		}
	}

3,最终版

publicstaticint[]countArr3(int[]arr){
		intmin=arr[0];
		intmax=arr[0];
		for(inti:arr){
			if(i<min){
				min=i;
			}
			if(i>max){
				max=i;
			}
		}
		//创建计数数组
		int[]countArr=newint[max-min+1];
		for(intj:countArr){
			countArr[j-min]++;
		}
		//对计数数组的元素进行累加,累加的规则将前一个元素的值+当前元素的值
		for(inti=1;i<countArr.length;i++){
			countArr[i]+=countArr[i-1];
		}
		//创建一个数组,存储最终的有序数列
		int[]sortedArr=newint[arr.length];
		//回填
		for(inti=arr.length-1;i>=0;i--){
			sortedArr[countArr[arr[i]-min]-1]=arr[i];
			countArr[arr[i]-min]--;
		}

		returnsortedArr;
	}

以上皆为笔记

您需要 登录账户 后才能发表评论

取消回复欢迎 发表评论:

关灯