Java实现基数排序（RadixSort）的代码示例

本篇文章给大家带来的内容是关于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

跟着以下的图片会更清楚原理：

从上图我们可以看出，基数排序会从右往左依次比较（即在我们的程序实现里面需要遍历很多次），而具体要遍历多少次则取决于最长的元素有多长，从右往左对每个位的元素比较可以用到桶排序或计数排序，桶排序和计数排序的时间复杂度都是O(n)，假设最大的元素长度为K，则基数排序的时间复杂度为O(k * n)，而k一般不会有多大，可以视为常量，所以基数排序的时间复杂度也是O(n)。

以下是我的Java实现：

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&q<em>本文来源[email protected]搞@^&代*@码2网</em>uot;, "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;    }}

喜欢 (0)赏

[搞代码]

分享 (0)