当前位置：首页 > news >正文

经典非比较排序—计数排序的Java实现方式

news 2025/7/27 14:20:38

目录

1.具体思路：

2.代码实现：

3.代码分析

4.示例测试：

测试源码：

测试结果：

计数排序，又被称为鸽巢原理，属于桶排序的一种，其本质是通过哈希映射思想，设定计数数组输入以及输出，实现非比较排序。

1.具体思路：

首先遍历待排序数组获取数组的最大值以及最小值，以此获取极差（两最值之差），根据极差大小设定计数数组，然后继续遍历待排序数组，根据映射关系在计数数组中计数，最后同时遍历计数数组与待排序数组，根据计数数组的计数内容将数据取出输出至待排序的原数组中。

2.代码实现：

该代码中计数数组的映射关系为：计数数组下标为i处的存储空间为大小为i+min（待排序数组中的最小值）的值进行计数，读者也可使用其他合理的映射关系。

public class CountSort {public static void countSort(int[]array){//遍历数组求最大值与最小值，以此获得极差创建计数数组//默认最大值与最小值均为起始元素int max=array[0];int min=array[0];//遍历数组获取最大值与最小值for(int i=1;i<array.length;i++){if(array[i]>max){max=array[i];}if(array[i]<min){min=array[i];}}//根据极差大小创建计数数组int[]count=new int[max-min+1];//遍历数组，根据映射关系开始计数for(int i=0;i< array.length;i++){//根据映射关系算出该元素在计数数组中的下标int index=array[i]-min;//对应位置计数加1count[index]++;}//计数完毕，开始遍历计数数组，输出到原数组中//设定原数组下标int index=0;for(int i=0;i< count.length;i++){//值相同的元素可能有多个，即计数数组中可能存在计数不为1的元素，需要多次取出while(count[i]>0){//根据映射关系取出元素int elem=i+min;//输出至原数组中array[index]=elem;//原数组下标移动index++;//计数数组对应计数减1count[i]--;}}}
}

3.代码分析

（1）时间复杂度：O(max(n,极差))（即n与待排序数组极差中的较大值）;

（2）空间复杂度：O(极差）;

（3）稳定性：稳定。

4.示例测试：

测试源码：


public class Test {public static void main(String[] args) {int[]array={2,4,1,3,6,8,5,7};System.out.println("排序前数组"+Arrays.toString(array));CountSort.countSort(array);System.out.println("排序后数组"+Arrays.toString(array));}
}