首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。