排序--09---计数排序

计数排序Counting Sort定义:计数排序 的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序计数排序要求输入的数据必须是有确定范围的整数。计数排序(Counting sort) 是一种稳定的排序算法。计数排序使用一个额外的数组C其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。原理:步骤1找出待排序的数组中最大和最小的元素步骤2统计数组中每个值为i的元素出现的次数存入数组C的第i项步骤3对所有的计数累加从C中的第一个元素开始每一项和前一项相加步骤4反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1。代码实现 1importjava.util.Arrays;publicclassCountingSort{publicstaticvoidmain(String[]args){intarr[]{53,3,542,748,3,-14,214};System.out.println(基数排序后 Arrays.toString(arr));Sort(arr);System.out.println(基数排序后 Arrays.toString(arr));}publicstaticint[]Sort(int[]array){if(array.length0){returnarray;}intminarray[0];intmaxarray[0];//先找出数组中的最大值与最小值for(inti1;iarray.length;i){if(array[i]max)maxarray[i];if(array[i]min)minarray[i];}intbias0-min;//创建一个长度为max-min1长度的数组来进行计数int[]bucketnewint[max-min1];Arrays.fill(bucket,0);for(inti0;iarray.length;i){//计算每个数据出现的次数bucket[array[i]bias];}intindex0,i0;//遍历长度为max-min1长度的数组来,来反向填充目标数组while(indexarray.length){if(bucket[i]!0){array[index]i-bias;bucket[i]--;index;}elsei;}// //遍历长度为max-min1长度的数组来,来反向填充目标数组// int index 0;// for (int i 0; i bucket.length ; i) {// while (bucket[i] !0){// array[index] i - bias;// bucket[i]--;// index;// }// }returnarray;}}代码实现 2先找出数组中的最大值与最小值创建一个长度为max-min1长度的数组来进行计数统计元素个数,并标记位置统计数组做变形后面的元素等于前面元素的和倒序遍历原始数组从统计数组中找到正确位置importjava.util.Arrays;publicclassBucketSort{publicstaticint[]bucketSort(int[]data){System.out.println(开始排序);if(data.length0){returndata;}// 1.先找出数组中的最大值与最小值intmaxInteger.MIN_VALUE;intminInteger.MAX_VALUE;for(inti0;idata.length;i){maxMath.max(max,data[i]);minMath.min(min,data[i]);}intarrayLengthdata.length;//2.创建一个长度为max-min1长度的数组来进行计数int[]bucketsnewint[max-min1];//3.统计元素个数,并标记位置for(inti0;iarrayLength;i){buckets[data[i]-min];}System.out.println(Arrays.toString(buckets));//4.统计数组做变形后面的元素等于前面元素的和for(inti1;imax-min1;i){buckets[i]buckets[i]buckets[i-1];}System.out.println(Arrays.toString(buckets));//5.倒序遍历原始数组从统计数组中找到正确位置int[]tempnewint[arrayLength];System.arraycopy(data,0,temp,0,arrayLength);for(intkarrayLength-1;k0;k--){data[--buckets[temp[k]-min]]temp[k];}returndata;}publicstaticvoidmain(String[]args){int[]data{3,5,-1,8,5,7,9,-3,1,3};System.out.println(排序之前\njava.util.Arrays.toString(data));bucketSort(data);System.out.println(排序之后\njava.util.Arrays.toString(data));}}算法分析:计数排序是稳定的 ,这个大家应该能很明显的看出来,因为计数排序本身并不是基于比较的算法.当输入的元素是n 个0到k之间的整数时它的运行时间是 O(n k)。计数排序不是比较排序排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围等于待排序数组的最大值与最小值的差加上1因为一旦序列中MAX与MIN的差距过大,那么需要的内存空间就会非常大.这使得计数排序对于数据范围很大的数组需要大量时间和内存。时间复杂度:最佳情况T(n) O(nk)最差情况T(n) O(nk)平均情况T(n) O(nk) 稳定