基数排序
2019-04-20 本文已影响0人
趁年轻多奋斗
百度:
基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。
理解:
把一个待排序的数组按照从个位、十位......进行分类,再按每次分类从0-9(个位、十位......)进行排序,依次进行,直到数组中最大数的位数排序完。
步骤:
- 先找出数组中最大数,求出位数,即需要分配的次数。
- 定义一个二维的临时数组,第一维用来存放0-9的正在分配的类别,长度为10,第二维用来从数组中提取出来的数,因为在分配前是不知道0-9各自有多少数,所以定义第二维的长度为数组的长度。
- 定义一个长度为10的数组,用来存放每次分配到二维数组时,每个维度的长度,作为下次同样类别存放的下标。
- 根据求出的分配次数进行for循环遍历,此时需要在定义一个变量n,初始为1,用来根据每次遍历分别类乘于10(比如第一次为1,、1%10得到个位数,依次类推)。
- 将得到的位数作为二维数组的第一维下标,第二维下标为上面的长度为10数组对应位数的值,用来存放当前判断的数字。
- 定义一个变量 index,用来记录取得到的数字要存放的位置,存放后的数组将覆盖原来要分配的数组。
- 使用两个for循环,用来取出二维数组里记录的数组。
- 当分配完一个类别后,要将记录数组长度的数组用到的下标归为0,用于下次的使用。
演示:
image.pngJvav代码:
package com.company;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = new int[]{5, 45, 87, 32, 9, 7, 159, 324, 4, 107, 69,58};
Main.base(arr);
System.out.println(Arrays.toString(arr));
}
private static void base(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
//计算最大数字是几位数
int count = (max + "").length();
//用来临时存放数据的数组
int[][] temp = new int[10][arr.length];
//用于记录在temp中相应的数组中存放数字的数量
int[] counts = new int[10];
//根据最长长度的数决定比较次数
for (int j = 0, n = 1; j < count; j++,n *= 10) {
//把每个数字分别计算余数
for (int d = 0;d<arr.length;d++){
//计算余数
int yu = arr[d]/n%10;
//把当前遍历的数字存放在指定位置的数组中
temp[yu][counts[yu]] = arr[d];
//记录数字
counts[yu]++;
}
//记录取出元素要放在原数组的位置
int index = 0;
//把数组从二维数组取出来
for (int k = 0;k<counts.length;k++){
//判断记录的数组是否有记录
if (counts[k]!=0){
//若有 则以记录该数组下标对应值为当前位数的数量
for (int l =0;l<counts[k];l++){
//取出元素
arr[index]=temp[k][l];
//移动下标
index++;
}
//遍历完,清空,下个位数记录需要
counts[k]=0;
}
}
}
}
}