【数据结构】-java实现基数排序算法（八）

【数据结构】-java实现基数排序算法（八）

基数排序算法的思想、动态演示、C++、python实现可以参考​​基数排序详解​​ 基数排序的思想：按照其余数来进行排序。桶中放的就是其余数。

基数排序算法分析

其中，d代表数组元素最高为位数，n代表元素个数。

使用了一个临时的数组。所以空间复杂度：O（n）。

在基数排序过程中，装桶的过程也是按照其先后顺序来的。所以基数排序是稳定的算法。

java代码实现

下面的代码有个致命的bug，就是不能对0进行排序，即对0、4、3、2、1排序会出错，可以在初始化bucket[][]时，赋给一个不会取到的数。我本来是想改的，但是如果你能发现这个bug，那么说明你对这个算法已经很熟悉了。

public static int[] radixSort(int[] theArray,int radix) { int count = getMax(theArray); //循环次数为最大的位数，每次循环都将出现一个新的theArray数组 for(int j=0; jmax){ max = theArray[i]; } } //获取最大的数的位数 int count = 0; while(max > 0){ max = max / 10; count++; } return count; }

总结

循环的次数为数组中最大的的位数。桶中放入的是余数，注意初始化bucket。每次循环都将bucket中的数，依次放回theArray数组中。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。