排序不基于比较。核心思想是桶排序。时间复杂度为O(N)。常见的不基于比较的排序有计数排序和基数排序。1、计数排序适用于对取值范围比较小且为整数的元素进行排序。（例子：年龄）1.核心思想：(1)先准备有限个数（如200）的整数辅助数组，将原数组逐个遍历，得到i值，然后将i值加1辅助数组的i位置(2)遍历辅助数组，如果数组位置i的值为k，则输出ki，得到的数组进行排序2.详细参考代码：/***@authorJavaand算法学习：星期一*/publicstaticvoidcountSort(int[]arr){if(arr==null||arr.length<2){return;}//统计数据intmax=Integer.MIN_VALUE;for(intv:arr){max=Math.max(max,v);}int[]bucket=newint[max+1];for(intv:arr){bucket[v]++;}//排序inti=0;for(intj=0;j0){arr[i++]=j;}}}从第一步可以看出，如果排序后的值跨度比较大，必须准备一个很大的辅助数组，但是数组大部分都是空的，所以是一个巨大的空间浪费。由此我们也可以看出计数和排序的局限性。2.基数排序适用于十进制正整数。1、核心思想：（1）遍历整个数组，得到最大小数位数，同时对不满足最大位数的数高位加0（2）准备十个桶,编号从0-9,每个桶的大小遍历数组为原数组大小(3),以个位数为准,若个位数的值为i,则将其放入第i-第桶；数出（先进先出）。此时的数按照个位数排序(4)遍历数组，以十位为准，如果十位的值为i，则放入第i个桶；一开始，一个一个倒出数字（先进先出）。这时候就把数字按照十位排序……直到遍历最高位，排序最后一个数字。实际写代码的时候，不是准备十个桶，而是准备一个长度为10的数组，这样可以大大节省空间。2.详细参考代码：/***@authorJava与算法学习：Monday*/publicstaticvoidradixSort(int[]arr){if(arr==null||arr.length<2){return;}sort(arr,0,arr.length-1,maxBit(arr));}/***找出数组中小数位数的最大值*/publicstaticintmaxBit(int[]arr){intmax=整数.MIN_VALUE；for(intvalue:arr){max=Math.max(max,value);}intres=0;while(max!=0){res++;最大值/=10；}returnres;}privatestaticint[voidsort(]arr,intl,intr,intdigit){intradix=10;//辅助数组int[]help=newint[r-l+1];//多次进入和退出桶数for(intd=1;d<=digit;d++){//prefixandarray:count[i]当前位（d位）有多少个数[0-i]int[]count=newint[radix];//统计此时数组d位置上的数字出现了多少次，for(inti=l;i<=r;i++){//获取d位置上的值，范围为[0,9]intv=getDigit(arr[i],d);计数[v]++；}}//此时count[i]表示当前位（d位）有多少个数是[0-i]for(inti=1;i=l;i--){//得到d位上的值intv=getDigit(arr[i],d);帮助[--计数[v]]=arr[i];}}//复制回原来的数组for(inti=0;i
