首页 > 代码库 > LSDRadixSort

LSDRadixSort

code 1:

 1         // 最低位 2     public static void LSDBucketRadixSort(int[] array, int radix) { 3         int len = array.length; 4         int max = array[0]; 5         for (int v : array)  6             if(max<v) 7                 max=v; 8         //最大值的位数 9         int d = String.valueOf(max).length();10         int[] tmp;11         //12         int[] buckets = new int[radix];13         for (int i = 0, rate = 1; i < d; i++) {14             Arrays.fill(buckets, 0);15             tmp = array.clone();16             for (int v : tmp) 17                 buckets[v / rate % radix]++;18             for (int j = 1; j < radix; j++)19                 buckets[j] += buckets[j - 1];20             for (int k = len - 1; k >= 0; k--) 21                 array[--buckets[tmp[k] / rate % radix]] = tmp[k];22             rate *= radix;23         }24     }    

else code:

 1         public static void LSDBubbleRadixSort(int[] array, int radix) { 2         int len = array.length; 3         int max = array[0]; 4         for (int v : array)  5             if (max < v) 6                 max = v; 7          8         int d = String.valueOf(max).length(); 9         for (int i = 0, rate = 1; i < d; i++) {10             for (int j = 0; j < len - 1; j++) {11                 for (int k = 0; k < len - j - 1; k++) {12                     int key1 = (array[k] / rate) % radix;13                     int key2 = (array[k + 1] / rate) % radix;14                     if (key1 > key2)15                         swap(array, k, k + 1);16                 }17             }18             rate *= radix;19         }20     }21 22     private static void swap(int[] array, int k, int j) {23         int tmp = array[k];24         array[k] = array[j];25         array[j] = tmp;26     }27 28     // 最低位29     public static void LSDInsertRadixSort(int[] array, int radix) {30         int len = array.length;31         int max = array[0];32         for (int i = 1; i < len; i++) {33             if (max < array[i])34                 max = array[i];35         }36         int d = String.valueOf(max).length();37         for (int i = 0, rate = 1; i < d; i++) {38             for (int j = 1; j < len; j++) {39                 int tmp = array[j];40                 int k = j;41                 int key1 = (array[k] / rate) % radix;42                 while (k > 0 && key1 < (array[k - 1] / rate) % radix) {43                     array[k] = array[k - 1];44                     k--;45                 }46                 array[k] = tmp;47             }48             rate *= radix;49         }50     }51 52     // 最低位53     @SuppressWarnings({ "unchecked", "rawtypes" })54     public static void LSDLinkedListRadixSort(int[] array, int radix) {55         int len = array.length;56         int max = array[0];57         for (int i = 1; i < len; i++) {58             if (max < array[i])59                 max = array[i];60         }61         int d = String.valueOf(max).length();62         LinkedList[] lists = new LinkedList[radix];63         for (int j = 0; j < radix; j++)64             lists[j] = new LinkedList();65         for (int i = 0, rate = 1; i < d; i++) {66             for (int j = 0; j < radix; j++)67                 lists[j].clear();68             for (int j = 0; j < len; j++) {69                 int key = (array[j] / rate) % radix;70                 lists[key].add(array[j]);71             }72             for (int j = 0, m = 0; j < radix; j++) {73                 while (!lists[j].isEmpty())74                     array[m++] = (int) lists[j].pop();75             }76             rate *= radix;77         }78     }

 

LSDRadixSort