十大排序——10.基数排序

本文主要是介绍十大排序——10.基数排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

下面我们来看一下基数排序

1.介绍

2.代码实现

3.总结与思考

1.介绍

基数排序（Radix sort）是一种非比较型整数排序算法

基本思想：

它的原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法描述

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；

2.代码实现

下面看一下代码实现：

package Sorts;import java.util.Arrays;//基数排序
public class RadixSort {public static void main(String[] args) {int [] arr = new int[]{193,255,12,6,78,50,31,564};radixSort(arr);;System.out.println(Arrays.toString(arr));}public static void radixSort(int[] array) {if (array == null || array.length <= 1) {return;}int length = array.length;// 每位数字范围0~9，基为10int radix = 10;int[] aux = new int[length];int[] count = new int[radix + 1];// 以关键字来排序的轮数，由位数最多的数字决定，其余位数少的数字在比较高位时，自动用0进行比较// 将数字转换成字符串，字符串的长度就是数字的位数，字符串最长的那个数字也拥有最多的位数int x = Arrays.stream(array).map(s -> String.valueOf(s).length()).max().getAsInt();// 共需要d轮计数排序, 从d = 0开始，说明是从个位开始比较，符合从右到左的顺序for (int d = 0; d < x; d++) {// 1. 计算频率，在需要的数组长度上额外加1for (int i = 0; i < length; i++) {// 使用加1后的索引，有重复的该位置就自增count[digitAt(array[i], d) + 1]++;}// 2. 频率 -> 元素的开始索引for (int i = 0; i < radix; i++) {count[i + 1] += count[i];}// 3. 元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据for (int i = 0; i < length; i++) {// 填充一个数据后，自增，以便相同的数据可以填到下一个空位aux[count[digitAt(array[i], d)]++] = array[i];}// 4. 数据回写for (int i = 0; i < length; i++) {array[i] = aux[i];}// 重置count[]，以便下一轮统计使用for (int i = 0; i < count.length; i++) {count[i] = 0;}}}//Description: 根据d，获取某个值的个位、十位、百位等，d = 0取出个位，d = 1取出十位，以此类推。对于不存在的高位，用0补private static int digitAt(int value, int d) {return (value / (int) Math.pow(10, d)) % 10;}
}