基数排序 | 指尖的舞客

基数排序 | 指尖的舞客

基数排序号称可以在O(n)的时间复杂度完成排序，其实所言非虚，只是真正的时间复杂度应该是O(kN)，k指待排序列最大值的位数，同时不能遗漏的是基数排序需要O(N)的空间充当"桶"的角色。根据基数排序的排序的原理，可知它比较适合于正整数的排序，而对于负数或者浮点数，字符串等排序，需要将待排序列做一定得变换。这里主要是记录下如何使用基数排序来实现对正整数的排序，以此来阐述基数排序的原理。 根据按位比较的方向，可以将基数排序的实现分为两种，MSD（Most significant digital，从高到低）和LSD（Least significant digital，从低到高）。 首先写一个获取指定位的辅助函数 private static final int radix = 10; private static int getDigit(int num, int d){ int[] rd = new int[]{1,1,10,100,1000}; return (num / rd[d])%10; } 先实现MSD算法，也就是从高到低位的比较顺序。 public static void msdRadixSort(int[] nums, int start, int end, int d){ if(nums == null || nums.length < 2) return; int len = end - start + 1; int[] bucket = new int[len]; int[] count = new int[radix+1]; int i = 0; int j = 0; for(i=start; i<=end; i++){ count[getDigit(nums[i], d)]++; } for(i=1; i<=radix; i++){ count[i] += count[i-1]; } for(i = end; i>=start; i--){ j = getDigit(nums[i], d); bucket[count[j] - 1] = nums[i]; count[j]--; } for(i=start, j=0; i<=end; i++,j++) nums[i] = bucket[j]; for(i=0; i

Read full article from 基数排序 | 指尖的舞客