计数排序的思路
计数排序的基本思路：
- 确定取值范围： 遍历整个待排序的数组，确定数组中元素的取值范围，找到最小值和最大值。
- 创建计数数组： 创建一个计数数组，其长度为取值范围的大小，用于统计原始数组中每个元素出现的次数。
- 统计元素个数： 遍历原始数组，将每个元素出现的次数记录到计数数组中，计数数组的索引对应于元素的值。
- 累加计数数组： 对计数数组进行累加操作，每个位置的值等于其前面所有位置值之和。这一步的目的是确定每个元素在排序后的数组中的位置。
- 构建有序数组： 创建一个与原始数组等长的临时数组，遍历原始数组，根据累加计数数组确定每个元素在有序数组中的位置，同时更新计数数组中对应元素的计数。
- 得到排序结果： 此时，临时数组就是排序完成的结果。
public class Sort {//5.计数排序public static int[] countingSort(int... array){int max=array[0],i,j;for(i=1;i<array.length;i++){if(array[i]>max){max=array[i];}}//新建max+1的整数数组int[] tempArray = new int[max+1];for (i = 0; i < array.length; i++) {tempArray[array[i]]++;}for (i = 0,j=0; i < tempArray.length; i++) {for (int k = 0; k < tempArray[i]; k++) {array[j++]=i;}}return array;}public static void main(String[] args) {int[] a={52,1,0,49,70,62,81,17};System.out.println(Arrays.toString(countingSort(a)));}
}
结果展示
)
