前言:
当前大家对“基数排序例题”大约比较着重,各位老铁们都需要学习一些“基数排序例题”的相关资讯。那么小编同时在网摘上收集了一些关于“基数排序例题””的相关文章,希望兄弟们能喜欢,看官们一起来学习一下吧!简介
基数排序属于“分配式排序”,又称“桶子法”,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为对数,在某些时候,基数排序法的效率高于其它的稳定性排序法。
中文名基数排序外文名Radix sort别 名“桶子法”
举例说明
1。假设原来有一串数值:73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
2。接下来将这些桶子中的数值重新串接起来,成为以下的数列:
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配,这次是根据十位数来分配:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
3。接下来将这些桶子中的数值重新串接起来,成为以下的数列:
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。
代码实现
package com.zyp.sort;import java.util.Arrays;/** * 基数排序 * @author zyp * @create 2022/2/21 */public class RadixSort { public static void main(String[] args) { //待排序数组 int[] array = new int[]{73, 22, 93, 43, 55, 14, 28, 65, 39, 81}; /** * 先找到数据中的最大值 */ int max = array[0]; for (int i = 1; i < array.length; i++) { if (max < array[i]) { max = array[i]; } } /** * 声明一个长度为10的二维数组 * 这10个二维数组代表下标为0-9的桶。用于储存个位、十位、百位对应的数组 */ int[][] blackArray = new int[10][array.length]; //声明一个数组,用于记录二维数组中的数据的个数 int[] count = new int[10]; //用于获取待排序中元素的个位、十位、百位、千位...的辅助变量 int n = 1; //最大值有多少位就要进行多少次 for (int i = 0; i < (max + "").length(); i++) { //将数组中的数据放入二维数组中(先从个位开始) for (int j = 0; j < array.length; j++) { int index = array[j] / n % 10; blackArray[index][count[index]] = array[j]; count[index]++; } int arrayIndex = 0; //将二维数组中的数据按照顺序放回到数组中 for(int k = 0;k < blackArray.length;k++){ if(count[k] != 0) { for (int x = 0; x < count[k]; x++) { array[arrayIndex] = blackArray[k][x]; arrayIndex++; } count[k] = 0; } } n = n * 10; System.out.println("第"+(i+1)+"轮之后的结果:"+Arrays.toString(array)); } }}图片说明
标签: #基数排序例题