龙空技术网

java实现基数排序

一个IT男的笔记 82

前言:

当前大家对“基数排序例题”大约比较着重,各位老铁们都需要学习一些“基数排序例题”的相关资讯。那么小编同时在网摘上收集了一些关于“基数排序例题””的相关文章,希望兄弟们能喜欢,看官们一起来学习一下吧!

简介

基数排序属于“分配式排序”,又称“桶子法”,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为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));        }    }}
图片说明

帮助理解

标签: #基数排序例题