9.计数排序
计数排序是一个非基于比较的排序算法,它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法,而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序,堆排序)
最坏、最好、平均时间复杂度:N+K ; 空间复杂度为:N+K
K不能省略,因为K为范围,受范围影响很大,当O(k)>O(n*log(n))时,受益低。
相关资料:https://blog.csdn.net/qq_42111463/article/details/84146915
static int[] countSort(int[] a) { int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int i = 0; i < a.length; i++) { max = a[i] > max ? a[i] : max; min = a[i] < min ? a[i] : min; } int[] help = new int[max - min + 1]; for (int i = 0; i < a.length; i++) { help[a[i] - min]++;//最小的数放在下标为0的位置 } ////////////////////////////////////////////////////////// //基本数据类型做法,直接输出到原数组排序;空间复杂度为K // int j = 0; // for (int i = 0; i < help.length; i++) { // while (help[i]-- > 0) {//当计数数组不为0时, // a[j++] = i + min;//将下标对应的数(i+min)依次填入原数组中 // } // } ////////////////////////////////////////////////////////// //对象如何保证稳定性 排名数组和新数组排序,空间复杂度:N+K //1.将统计数组变形为排名数组 int sum = 0;//当前排名 for (int i = 0; i < help.length; i++)//统计数组做变形,后面的元素等于前面元素的和,排名 { sum += help[i]; help[i] = sum; } //////////////////计数数组变形为排名数组优化 // for (int i = 1; i < help.length; i++)//统计数组做变形,后面的元素等于前面元素的排名加上自身的计数个数 // { // help[i] += help[i-1]; // } //////////////////取数排序过程分析 //此时将计数数组变成了排名数组, //再逆序输出原数组,将原数组的每一个数根据排名数组的下标去找排名,放在新数组中; //同时把排名数组对应位置的名次-1 int[] sortArr = new int[a.length]; for (int j = a.length - 1; j >= 0; j--) { sortArr[help[(a[j]-min)]-1]=a[j];//a[j]是原数组的数, a[j]-min是在排名数组中对应的下标, // help[a[j]-min]是对应的排名,help[a[j]-min]-1是在新建存放稳定数组中的存放位置 help[(a[j]-min)]--;//同时将该下标的排名-1 } ////////////////取数排序可以简化为一条语句 // for(int i=a.length-1;i>=0;i--){ // b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素 // } return sortArr;//将排好序的稳定数组返回 } }
//优化版 public static int[] countSort(int[]a){ int b[] = new int[a.length]; int max = a[0],min = a[0]; for(int i:a){ max = a[i] > max ? a[i] : max; min = a[i] < min ? a[i] : min; } }//这里k的大小是要排序的数组中,元素大小的极值差+1 int c[]=new int[max-min+1];//初始化计数数组 for(int i=0;i<a.length;++i){ c[a[i]-min]+=1;//优化过的地方,减小了数组c的大小 } for(int i=1;i<c.length;++i){//计数变排名数组 c[i]=c[i]+c[i-1]; } for(int i=a.length-1;i>=0;--i){//稳定取数 b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素 } return b; } }