cs61b homework10

part1：countingsort的算法感觉还是蛮绕的，贼烧脑，注意是对16进制的每一位进行排序，取得相应位数值算法可以写成(keys[i]%(whichDigit+1))/whichDigit;

code：

 1 public static int[] countingSort(int[] keys, int whichDigit) {
 2         if(whichDigit>7||whichDigit<0)
 3             return null;
 4         int sort[]=new int[keys.length];
 5         double num=Math.pow((double)16, (double)(whichDigit+1));
 6         double num3=Math.pow((double)16, (double)(whichDigit));
 7         int num2=(int)num;
 8         int num4=(int)num3;
 9         for(int i=0;i<keys.length;i++){
10             sort[i]=(keys[i]%num2)/num4;
11         }
12         int count[]=new int[16];
13         for(int i=0;i<sort.length;i++){
14         count[sort[i]]++;    
15         }
16         int total=0;
17         for(int i=0;i<count.length;i++){
18             int c=count[i];
19             count[i]=total;
20             total+=c;
21         }
22         int y[]=new int[keys.length];
23         for(int i=0;i<keys.length;i++){
24             y[count[sort[i]]]=keys[i];
25             count[sort[i]]++;
26         }
27         return y;
28         
29         
30       }

part2：radixsort在coutingsort基础上叠加7次，到int的取值范围即可。

code：

1 public static int[] radixSort(int[] keys) {
2           int[]radixsort=new int[keys.length];
3           for(int i=0;i<keys.length;i++)
4               radixsort[i]=keys[i];
5         for(int i=0;i<8;i++){
6             radixsort=countingSort(radixsort,i);
7         }
8         return radixsort;
9       }

运行结果：

keys are [ 60013879 11111119 2c735010 2c732010 7fffffff 4001387c 10111119 529a7385 1e635010 28905879 11119 0 7c725010 1e630010 111111e5 61feed0c 3bba7387 52953fdb 40013879 ]
keys are [ 0 11119 7fffffff 10111119 11111119 111111e5 1e630010 1e635010 28905879 2c732010 2c735010 3bba7387 40013879 4001387c 52953fdb 529a7385 60013879 61feed0c 7c725010 ]