基本排序_基数排序_Java实现数据结构与算法

转载请注明出处：http://blog.csdn.net/ljmingcom304/article/details/50372591
本文出自：【梁敬明的博客】
1.基数排序基数排序又称作桶排序，从序列的最低位开始，把当前位数对应的数字按0~9将元素进行归类，遍历到元素中不为0的最高位为止，直到最终完成排序。

文章图片

存在一个序列【19】【82】【137】【22】【5】【431】【23】【20】【11】【109】，将其按照从小到大的顺序进行排列。
第一次分类，选取元素的个位数，按0~9将元素进行归类。
第二次分类，选取元素的十位数，按0~9将元素进行归类。
第三次分类，选取元素的百位数，按0~9将元素进行归类。
2.示例代码对一个长度为N的序列从小到大进行排序，序列中元素的不为0的最高位为第i位，从第1位开始，将0~9存放到二维数组的第一维，再将序列中当前位的元素与第一维对应，存放到二维数组的第二维，按该存放方式到元素的最高位为止。

public class RadixSort {public static void main(String[] args) { int[] array = { 19, 82, 137, 22, 5, 431, 23, 20, 11, 109 }; RadixSort.sort(array); System.out.println("排序后数组：" + Arrays.toString(array)); }public static void sort(int[] a) { int digit = 0; // 数组的最大位数 for (int i : a) { // 获取数组中数的最大位数 digit = Math.max(digit, String.valueOf(i).length()); } int k = 0; // 用户记录排序数组的索引 int m = 1; // 当前的位数，个位用1表示，十位用2表示，以此类推 int n = 1; // 用来表示当前位数的整数倍 int type = 10; // 将余数从0-9分为10种类型 int[][] temp = new int[type][a.length]; // 第一维用来存储余数，第二维用来存储余数对应的数组值 int[] order = new int[type]; // 用户第二维数组值得索引计数 while (m <= digit) { // 遍历数组中的每个元素，以当前位数依据余数进行归类 for (int i = 0; i < a.length; i++) { int r = (a[i] / n) % 10; // 当前数值在当前位数的余数 temp[r][order[r]] = a[i]; // 第一次为temp[r][0],第二次为temp[r][1]...... order[r]++; } // 遍历二维数组的第一维 for (int i = 0; i < type; i++) { if (order[i] != 0) {// 当order[i]==0时，说明order[r]++没有执行，temp[r][]中没有存储数组值 // 遍历二维数组的第二维 for (int j = 0; j < order[i]; j++) {// order[i]表示当前i余数的类型存储的数组值的个数 a[k] = temp[i][j]; k++; } } order[i] = 0; } k = 0; // 排序数组索引初始化 m++; // 当前位数个数的索引 n *= 10; // 当前位数向前推 } }}

3.算法分析 【基本排序_基数排序_Java实现】时间复杂度：
待排序列有n个元素，所有元素的最大位数为d（如最大位数为百分位，则d=3），r为当前位数的取值范围（如0~9），基数排序的时间复杂度为O(d(n+r))。
算法稳定性：
在基数排序中，当前位数相同的数值不会交换位置，所以基数排序是稳定的排序算法。