這篇文章帶給大家的內容是關於Java實作基數排序（RadixSort）的程式碼範例，有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。
基數排序算是桶排序和計數排序的衍生吧，因為基數排序裡面會用到這兩種其中一種。
基數排序所針對的待排序元素是要有高低位之分的，例如單字adobe，activiti，activiti就高於adobe，這個是根據ascll碼來的。
現在我們可以提出一個問題，要怎麼對字典裡面的單字進行排序呢？
例如我們現在有以下單字：
"Java", "Mongodb", "Redis", "Kafka", "javascript", "mysql", "mybatis", "kindle", "rpc", "Algorithm", "mergeSort", "quickSort", "Adobe"
我們要怎麼對它排序呢，這裡就可以用到基數排序了，基數排序的原理就是我們將一個元素按高低位分成單一個體，如Adobe我們就分成A,d,o,b,e，Algorithm我們就分成A,l,g,o,r,i,t,h,m，然後我們從右往左，依序比較即可。但這裡Adobe和Algorithm並不能直接比較，因為他們的長短不一，所以在比較之前我們應該找到最長的元素的長度，然後將其餘短的元素補全到一樣長：
Adobe0000
Algorithm
這樣才可以形成比較，從右往左,0:m,0:h,0:t,0:i,e:r,b:o,o: g,d:l,A:A，我們就可以比較出來Adobe > Algorihtm
跟著以下的圖片會更清楚原理：
package com.structure.sort;
/**
* @author zhangxingrui
* @create 2019-01-30 14:58
**/
public class RadixSort {
public static void main(String[] args) {
/*int[] numbers = {19, 36, 24, 10, 9, 29, 1, 0, 3, 60, 100, 1001, 999, 520, 123, 96};
radixSort(numbers);
for (int number : numbers) {
System.out.println(number);
}*/
String[] words = {"Java", "Mongodb", "Redis", "Kafka", "javascript", "mysql", "mybatis", "kindle", "rpc", "Algorithm", "mergeSort", "quickSort", "Adobe"};
// String[] words = {"Java", "mongodb", "Kafka"};
radixSort(words);
for (String word : words) {
System.out.println(word.replaceAll("0", ""));
}
}
/**
* @Author: xingrui
* @Description: 基数排序（单词）
* @Date: 15:53 2019/1/30
*/
private static void radixSort(String[] words){
int exp = 0;
int maxLength = getMaxLength(words);
autoComplete(words, maxLength);
for(exp = 1; exp <= maxLength; exp++){
countingSort(words, exp);
}
}
/**
* @Author: xingrui
* @Description: 计数排序（单词）
* @Date: 13:57 2019/1/30
*/
private static void countingSort(String[] words, int exp){
int n = words.length;
String[] r = new String[n];
int[] c = new int[122];
for(int i = 0; i < n; ++i){
int asc = (byte)words[i].charAt(words[i].length() - exp);
c[asc]++;
}
for(int i = 1; i < 122; ++i){
c[i] = c[i-1] + c[i];
}
for (int i = n - 1; i >= 0; --i){
int asc = (byte)words[i].charAt(words[i].length() - exp);
int index = c[asc];
r[index - 1] = words[i];
c[asc]--;
}
for(int i = 0; i < n; ++i){
words[i] = r[i];
}
}
/**
* @Author: xingrui
* @Description: 基数排序（纯数字）
* @Date: 15:00 2019/1/30
*/
private static void radixSort(int[] numbers){
int exp = 0;
int maxNumber = getMaxNumber(numbers);
for(exp = 1; maxNumber/exp > 0; exp *= 10){
countingSort(numbers, exp);
}
}
/**
* @Author: xingrui
* @Description: 计数排序（纯数字）
* @Date: 13:57 2019/1/30
*/
private static void countingSort(int[] numbers, int exp){
int n = numbers.length;
int[] r = new int[n];
int[] c = new int[10];
for(int i = 0; i < n; ++i){
c[numbers[i]/exp % 10]++;
}
for(int i = 1; i < 10; ++i){
c[i] = c[i-1] + c[i];
}
for (int i = n - 1; i >= 0; --i){
int index = c[numbers[i] / exp % 10];
r[index - 1] = numbers[i];
c[numbers[i] / exp % 10]--;
}
for(int i = 0; i < n; ++i){
numbers[i] = r[i];
}
}
/**
* @Author: xingrui
* @Description: 自动补全单词
* @Date: 16:38 2019/1/30
*/
private static void autoComplete(String[] words, int maxLength){
int i = 0;
for (String word : words) {
if(word.length() < maxLength){
int value = maxLength - word.length();
StringBuilder sb = new StringBuilder();
for(int j = 0; j < value; ++j){
sb.append("0");
}
words[i] = word + sb;
}
i++;
}
}
/**
* @Author: xingrui
* @Description: 获取字符串最大的长度
* @Date: 15:56 2019/1/30
*/
private static int getMaxLength(String[] words){
int maxLength = words[0].length();
for(int i = 1; i < words.length; ++i){
if(words[i].length() > maxLength)
maxLength = words[i].length();
}
return maxLength;
}
/**
* @Author: xingrui
* @Description: 获取最大的数字
* @Date: 15:56 2019/1/30
*/
private static int getMaxNumber(int[] numbers){
int maxNumber = numbers[0];
for(int i = 1; i < numbers.length; ++i){
if(numbers[i] > maxNumber)
maxNumber = numbers[i];
}
return maxNumber;
}
}
#
以上是Java實作基數排序（RadixSort）的程式碼範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！
