今天凌晨两点跟着左程云算法课28复习了基数排序。

        基数排序和其他排序最大的不同就是，基数排序不是基于比较的排序。他有点桶排序的思想在里面。并且我们在进行基数排序的时候，要求数组里面没有负数。

        基数排序就是依次根据数字的个十百千位排序。先开始设置offset=1，那么nums[i]每次比较位数就是（nums[i]/offset）%10,每次offset要*BASE（BASE表示数组的进制数，一般为10）。然后根据数字的某一位进行cnt计数。计数完成后，将cnt处理成前缀累加的形式，前缀累加的cnt形式可以理解为cnt[i]为【提取的一位数字】<=i 的个数，这样方便我们后续倒序处理定位help数组中的位置。然后进行倒序处理，提取一位数字，然后放到cnt[i]-1的位置，然后cnt[i]-1。这就是按照数据其中一位(个、十、百、千...)进行一次排序的过程。这个进位由offset控制。

基数排序的核心代码：

	// 基数排序核心代码// arr内要保证没有负数// n是arr的长度// bits是arr中最大值在BASE进制下有几位public static void radixSort(int[] arr, int n, int bits) {// 理解的时候可以假设BASE = 10for (int offset = 1; bits > 0; offset *= BASE, bits--) {Arrays.fill(cnts, 0);for (int i = 0; i < n; i++) {// 数字提取某一位的技巧cnts[(arr[i] / offset) % BASE]++;}// 处理成前缀次数累加的形式for (int i = 1; i < BASE; i++) {cnts[i] = cnts[i] + cnts[i - 1];}for (int i = n - 1; i >= 0; i--) {// 前缀数量分区的技巧// 数字提取某一位的技巧help[--cnts[(arr[i] / offset) % BASE]] = arr[i];}for (int i = 0; i < n; i++) {arr[i] = help[i];}}}

在应用基数排序时，一般数组中会有负数的情况。这种情况也比较好处理，遍历寻找数组中的最小值minNum，然后数组中每个数字都减去minNum，进行一个转换。排序完成后最后再加上minNum，复原成原来的数字。

主函数部分（注意找最大值要找转换后的最大值，可能bits值会不一样）：

class Solution {public static int BASE=10;public static int MAXN=50001;public static int[] cnt=new int[BASE];public static int[] help=new int[MAXN];public int[] sortArray(int[] nums) {int n=nums.length;if(n>1){int numMin=nums[0];for(int i=1;i<n;i++){numMin=Math.min(nums[i],numMin);}int numMax=Integer.MIN_VALUE;for(int i=0;i<n;i++){nums[i]=nums[i]-numMin;numMax=numMax>nums[i]?numMax:nums[i];}int bits=getBits(numMax);radixSort(nums,n,bits);for(int i=0;i<n;i++){nums[i]=nums[i]+numMin;}}return nums;}public int getBits(int n){int ans=0;while(n>0){ans++;n=n/10;}return ans;}public void radixSort(int[] nums,int n,int bits){for(int offset=1;bits>0;offset*=BASE,bits--){Arrays.fill(cnt,0);for(int i=0;i<n;i++){cnt[(nums[i]/offset)%10]++;}for(int i=1;i<BASE;i++){cnt[i]=cnt[i-1]+cnt[i];}for(int i=n-1;i>=0;i--){help[cnt[(nums[i]/offset)%10]-1]=nums[i];cnt[(nums[i]/offset)%10]--;}for(int i=0;i<n;i++){nums[i]=help[i];}}}
}