简单来说,就是通过额外开辟一个数组或者类似的集合空间,将原数组待排序元素进行整理放到这个新开辟的数组中,最后,再将这个数组排序好的元素重新填充到原数组中,可以看出来,这个计数排序是需要额外消耗空间的。
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数(局限性)。
基数排序时间复杂度。计数排序算法步骤大概有三个步骤:
下面用代码来实现一下这个过程,大家可以参照代码注释一块儿理解,
public class CountSort {public static void main(String[] args) {int[] arr = {11,48,15,7};System.out.println(Arrays.toString(countSort(arr)));}public static int[] countSort(int[] arr){//最大最小值初始化int min=arr[0],max=arr[0];//寻找最大最小值for(int i=0;i<arr.length;i++){if(arr[i] > max){max = arr[i];}if(arr[i] < min){ min = arr[i];}}//定义一个额外的数组,相当于是一个空桶,可以存放的下标长度是从 min 到max的长度大小int[] bucket = new int[max-min+1];//初始化桶填充,这里全部为0Arrays.fill(bucket, 0);//{11,48,15,7} ,保证原数组的元素在bucket中都能占据一个位置,for(int i=0;i<arr.length;i++){bucket[arr[i]-min]++;}//数组内容回填int index=0,i=0;while(index < arr.length){if(bucket[i] != 0){arr[index] = i + min;bucket[i]--;index++;}else{i++;}}return arr;}}
运行一下这段程序,可以看到已经排好序,
java排序方法,当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量内存。N表示原始数组元素个数,k表示桶的个数,也就是数组c的长度
综合来看:
1、最佳情况:T(n) = O(n+k)
2、最差情况:T(n) = O(n+k))
3、平均情况:T(n) = O(n+k)
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态