基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶排序”(bucket sort)。为了说明这一算法,我们先以基数排序的一个特例鸽巢排序(Pigeonhole sort)来进行讲解。
鸽巢排序
1、数组中没有重复的元素,且每个元素都>=0
先考虑一种最简单的情况,对一个数组array:{11, 13, 56, 23, 63, 98 ,87}进行排序,注意这个数组中没有重复的元素,且都是>=0,那么:
第一步:遍历这个数组,找出其中最大数字(maxNum)
第二步:创建一个辅助数组bucketArray,大小是maxNum+1,辅助元素中的每一个元素称之为一个"桶"
第三步:遍历待排序的数组array,将每一个元素分配(distribution)到辅助数组bucketArray中,分配的方式很简单,bucketArray[array[i]]=array[i],即直接将这个位置上的数字array[i]作bucketArray数组的下标,并给其赋值为array[i],即数组的下标和数组元素的值是相同的
第四步:可以看到,经过第三步排序之后,辅助数组bucketArray中的元素已经有序的了,现在只需要迭代辅助数组,将不是null的元素依次拷贝到待排序数组中,即完成了排序
代码实现如下:
public class PigeonholeSort { /** * 第一种情况:所有元素都>=0 */ public static void sort(int[] arr){ //第一步,确定数组中最大的元素 int max=arr[0]; for (int i : arr) { if(i>max){ max=i; } } //第二步:创建辅助数组,大小为max+1,注意这里是Integer,所以默认每个元素的值都是null Integer[] bucketArray=new Integer[max+1]; //第三步:将数组中的分配到bucket数组中 for (int i = 0; i < array.length; i++) { bucketArray[array[i]-minNum]=array[i]; } //第四步:迭代辅助数组,将不是null的元素依次拷贝到待排序数组中 int index=-1; for (int i = 0; i < bucketArray.length; i++) { if(bucketArray[i]!=null){ array[++index]=bucketArray[i]; } } } public static void main(String[] args) { int[] arr={11, 13, 56, 23, 63, 98 ,87}; System.out.println("排序前:"+ Arrays.toString(arr)); sort(arr); System.out.println("排序后:"+ Arrays.toString(arr)); } }
运行程序,输出
排序前:[11, 13, 56, 23, 63, 98, 87] 排序后:[11, 13, 23, 56, 63, 87, 98] |
2、数组中没有重复的元素,数据元素有正有负
在上面的案例中,我们假设所有的元素都是>=0,因此可以直接按照数组下标进行分配,那么如果现在存在负数呢?此时我们要按照如下方案进行修改:
第一步应该找出最大数字maxNum和最小数字minNum
第二步:辅助数组bucketArray的长度不再是待排序数组array的最大元素maxNum+1,而是maxNum-minNum+1
第三步:在分配元素到临时数组时,下标应该按照如下方案计算:bucketArray[array[i]-minNum]=array[i]
第四步:不变
修改后的代码如下所示:
public class PigeonholeSort { public static void sort(int[] array){ //第一步,确定数组中最大的元素和最小元素 int maxNum=array[0]; int minNum=array[0]; for (int i : array) { if(i>maxNum){ maxNum=i; } if(i<minNum){ minNum=i; } } //第二步:创建辅助数组,大小为max-min+1,注意这里是Integer,所以默认每个元素的值都是null int bucketArrayLength = maxNum - minNum + 1; Integer[] bucketArray=new Integer[bucketArrayLength]; //第三步:将数组中的分配到bucket数组中 for (int i = 0; i < array.length; i++) { bucketArray[array[i]-minNum]=array[i]; } //第四步:迭代辅助数组,将不是null的元素依次拷贝到待排序数组中 int index=-1; for (int i = 0; i < bucketArray.length; i++) { if(bucketArray[i]!=null){ array[++index]=bucketArray[i]; } } } public static void main(String[] args) { int[] arr={11, 13, 56, -23, 63, 98 ,87};//注意这个数组中存在一个负数 System.out.println("排序前:"+ Arrays.toString(arr)); sort(arr); System.out.println("排序后:"+ Arrays.toString(arr)); } }
运行程序,输出
排序前:[11, 13, 56, -23, 63, 98, 87] 排序后:[-23, 11, 13, 56, 63, 87, 98] |
3、数组中存在重复的元素,数据元素有正有负
当数组中存在重复的元素时,例如所有元素都相同{5,5,5,5,4},那么按照上面的计算辅助数组大小就会有错,此时按照如下方式计算辅助数组长度:
MAX((maxNum-minNum+1),array.length) |
此外,在给辅助数据分配元素的时候,可能存在相同元素的值,已经占用了一个位置,因此考虑顺延到下一个位置
修改后的代码如下所示:
public class PigeonholeSort { public static void sort(int[] array){ //第一步,确定数组中最大的元素和最小元素 int maxNum=array[0]; int minNum=array[0]; for (int i : array) { if(i>maxNum){ maxNum=i; } if(i<minNum){ minNum=i; } } //第二步:创建辅助数组,大小为max-min+1,注意这里是Integer,所以默认每个元素的值都是null int bucketArrayLength = Math.max(maxNum - minNum + 1,array.length); Integer[] bucketArray=new Integer[bucketArrayLength]; //第三步:将数组中的分配到bucket数组中 for (int i = 0; i < array.length; i++) { int distributionIndex = array[i] - minNum; while (true){ if(bucketArray[distributionIndex]==null){ bucketArray[distributionIndex]=array[i]; break; }else{ distributionIndex++; } } } //第四步:迭代辅助数组,将不是null的元素依次拷贝到待排序数组中 int index=-1; for (int i = 0; i < bucketArray.length; i++) { if(bucketArray[i]!=null){ array[++index]=bucketArray[i]; } } } public static void main(String[] args) { int[] arr={11, 13, 56,56, -23, 63, 56 ,87};//注意这个数组中存在一个负数,且有重复元素 System.out.println("排序前:"+ Arrays.toString(arr)); sort(arr); System.out.println("排序后:"+ Arrays.toString(arr)); } }
运行程序输出
排序前:[11, 13, 56, 56, -23, 63, 56, 87] 排序后:[-23, 11, 13, 56, 56, 56, 63, 87] |
总结
鸽巢排序的时间复杂度为(O(n)),执行速度快于任何一种排序,但其却需要很大的辅助空间,而且其适用于很少的数值范围内的排序。当待排序数组中出现很多不相等的元素是,鸽巢排序的效率会降低。鸽巢排序的辅助数组的大小取决与待排序数组的数值范围,辅助空间的大小为待排序数组中的最大值与最小值之差加1。比如有序列{11, 13, 56, 23, 63, 23, 98 ,87},则复制数组需要98-11+1=88个空间。
我们一般很少使用鸽巢排序, 因为它很少可以在灵活性, 简便性, 尤是速度上超过其他排序算法. 事实上, 桶排序较鸽巢排序更加的实用。