首页 > 代码库 > 基数排序
基数排序
基数排序(Radix Sort)是在桶排序的基础上发展而来的，两种排序都是分配排序的高级实现。
分配排序(Distributive Sort)的基本思想：排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。
基数排序代码：
import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Main { //static int[] array = {7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2,-3}; static int[] array = {7, 8, 9, 6, 1, 4, 3, 2, 5, 0,32,7,159,2,83,123,321,36}; public static void main(String[] args) throws InterruptedException { System.out.println(Arrays.toString(array)); radixSort(array); System.out.println(Arrays.toString(array)); } public static void radixSort(int[] array){ int max = array[0]; for(int i=0;i<array.length;i++){ //找到数组中的最大值 if(array[i]>max){ max = array[i]; } } int keysNum = 0; //关键字的个数，我们使用个位、十位、百位...当做关键字，所以关键字的个数就是最大值的位数 while(max>0){ max /= 10; keysNum++; } List<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>(); for(int i=0;i<10;i++){ //每位可能的数字为0~9，所以设置10个桶 buckets.add(new ArrayList<Integer>()); //桶由ArrayList<Integer>构成 } for(int i=0;i<keysNum;i++){ //由最次关键字开始，依次按照关键字进行分配 for(int j=0;j<array.length;j++){ //扫描所有数组元素，将元素分配到对应的桶中 //取出该元素对应第i+1位上的数字，比如258，现在要取出十位上的数字，258%100=58,58/10=5 int key =array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i); buckets.get(key).add(array[j]); //将该元素放入关键字为key的桶中 } //buckets内有10子bucket,根据第i+1位上的数字分别存储在不同的bucket内 //分配完之后，将桶中的元素依次复制回数组 int counter = 0; //元素计数器 for(int j=0;j<10;j++){ ArrayList<Integer> bucket =buckets.get(j); //关键字为j的桶 while(bucket.size()>0){ array[counter++] = bucket.remove(0); //将桶中的第一个元素复制到数组，并移除 } } System.out.print("第"+(i+1)+"轮排序："); display(array); } } public static void display(int[] array){ for(int i=0;i<array.length;i++){ System.out.print(array[i]+"\t"); } System.out.println(); }}
[7, 8, 9, 6, 1, 4, 3, 2, 5, 0, 32, 7, 159, 2, 83, 123, 321, 36]第1轮排序：0 1 321 2 32 2 3 83 123 4 5 6 36 7 7 8 9 159 第2轮排序：0 1 2 2 3 4 5 6 7 7 8 9 321 123 32 36 159 83 第3轮排序：0 1 2 2 3 4 5 6 7 7 8 9 32 36 83 123 159 321 [0, 1, 2, 2, 3, 4, 5, 6, 7, 7, 8, 9, 32, 36, 83, 123, 159, 321]
数组中不可以有负数。
第一步判断关键字的个数，这里的关键字就是个，十，百，获取最大值，就可以知道关键字的个数
第二步创建List数组buckets，有10个元素，每一个都是一个ArrayList类型的bucket
第三步根据关键字进行遍历，先根据数组array中元素的个位数的值，分别存储到buckets中对应的bucket
第四步将buckets中的值全部赋值给array,清空buckets中的每一个bucket，并根据关键字中的百进行下一步
第三步，第四步不停循环，直到关键字全部循环结束
最后即可发现数组array已经排好序。
复制的次数和数据项的个数与关键字长度成正比，关键字的长度越长，效率越低。
http://blog.csdn.net/u012152619/article/details/47702673
基数排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。