基数排序也被称为桶排序,是一种使用空间换时间的做法。它的大致思想为:
图解(待完成)
不足:
一些细节:
基数排序的时间复杂度位NxK,K代表着桶的个数。
有人会好奇,0-9对应的这10个桶在进行操作的时候,比如说个位遍历结束后,准备遍历十位时,不需要对10个桶进行清空吗?回答是不需要对桶整个进行清空,但要对保存着每个桶的bucketElementCounts
数组进行清空,具体做法为,在取出元素的时候,每取出一个桶的,就把这个bucketElementCounts
数组存储的索引进行清空,以便下一次对十位进行排序。
package sort; import java.util.Arrays; /** * 基数排序(桶排序) */ public class RadixSort { public static void main(String[] args) { // 原始数组 int[] arr = { 53, 3, 542, 748, 14, 214}; System.out.println("原始数组:"+ Arrays.toString(arr)); // 定义桶为一个二维数组 10:位数 arr.length:桶内一维数组大小 int[][] bucket = new int[10][arr.length]; // 定义一个记录桶内一维数组元素个数的工具 int[] bucketElementCounts = new int[10]; // 1.桶排序的循环次数与最大数的位数相关,找到最大的数字,确定位数 // 1.1假设arr[0]最大 int max = arr[0]; for (int i = 1; i < arr.length - 1; i++) { if (arr[i] > max){ max = arr[i]; } } // 1.2得到了最大数字是几位数 int maxLength = (max + "").length(); // 2.进行循环,使用i控制循环次数(取模),使用n控制步长 for (int i = 0,n = 1;i <maxLength; i++, n *= 10){ // 2.1 对每个arr中的元素取余数 for (int j = 0; j< arr.length;j++){ int single = arr[j] / n % 10; // 2.2依据位数,放入对应的桶中 bucket[single][bucketElementCounts[single]] = arr[j]; bucketElementCounts[single]++; // 2.2需要理解 } // 3.放入桶结束,从桶中取出元素放入arr开始 int index = 0; // arr数组的索引 //3.1 遍历桶 for (int k = 0; k < bucketElementCounts.length; k++){ // 3.2如果桶内有元素 if (bucket[k].length != 0){ // 3.3遍历桶内元素,放入arr for (int l = 0; l < bucketElementCounts[k];l++){ arr[index++] = bucket[k][l]; } } // 3.4记录桶内一维数组元素个数的工具,置0 bucketElementCounts[k] = 0; } } System.out.println("排序后数组:"+Arrays.toString(arr)); // [3, 14, 53, 214, 542, 748] } }