首页 > 其他分享 >s004-桶排序

s004-桶排序

时间:2022-10-30 10:45:53浏览次数:55  
标签:count index int 45 s004 数组 排序

s004-桶排序

概念

之前写的博客中讲述的排序算法,例如选择排序,冒泡排序,插入排序,快排,归并和堆排序都是基于比较的算法
而桶排序不是基于比较的算法,而是基于数据状态的算法
桶排序(Bucket sort)或者箱排序是一个排序算法,工作的原理是将数组分到有限的桶里。每个桶再个别排序(有可能再使用别的排序算法或者是以递归的方式继续使用桶排序进行排序)

计数排序

概念
计数排序:如果数组中数的范围控制在一定范围内,比如人的年龄数组,其值一定在0-200之间
那么我们可以准备一个长度为201的备用数组,初始值为0,遍历数组,将备用数组index值为年龄数组当前值的值++,即统计年龄数组的词频,最终按照备用数组中数据的词频,还原原数组,完成排序,复杂度是$O(N)$
计数排序的时间复杂度虽然低,但是可用范围比较窄,因为一般的排序都是在实数范围内的排序,范围比较大,使用计数排序得不偿失

基数排序

概念
基数排序:举例说明吧
例如[12,45,23,123,35]
由于数组中的数都是10进制的数,因此准备长度为10的桶
第一次按照个位数的值排序
index为2的桶 12
index为3的桶 23,123
index为5的桶 45,35
出桶,同一个桶先进先出[12,23,123,45,35]

第二次按照十位数的值排序
index为1的桶 12
index为2的桶 23,123
index为3的桶 35
index为5的桶 45
出桶,同一个桶先进先出[12,23,123,35,45]

第三次按照十位数的值排序
index为0的桶 12,23,35,45
index为1的桶 123
出桶[12,23,35,45,123]
排序完毕

基数排序升级版
举例说明
例如[12,45,23,123,35]
由于数组中的数都是10进制的数,因此准备长度为10的count数组[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
第一次按照个位数的值排序
count[0,0,1,2,0,2,0,0,0,0]个位数为2的值有1个,为3的有两个,为5的有两个
count累加[0,0,1,3,3,5,5,5,5,5]个位数为小于等于2的有1个,小于等于3的有3个,小于等于5的有5个
将[12,45,23,123,35]按照从右往左的顺序填入与该数组相同大小的备用数组中
对于35,个位数是5,小于等于5的数有5个,所以填入index为4的地方,小于等于5的数数量--,count累加[0,0,1,3,3,4,5,5,5,5]
对于123,个位数是3,小于等于3的数有3个,所以填入index为2的地方,小于等于3的数数量--,count累加[0,0,1,2,3,4,5,5,5,5]
对于23,个位数是3,小于等于3的数有2个,所以填入index为1的地方,小于等于3的数数量--,count累加[0,0,1,1,3,4,5,5,5,5]
对于45,个位数是5,小于等于5的数有4个,所以填入index为3的地方,小于等于3的数数量--,count累加[0,0,1,2,3,3,5,5,5,5]
对于12,个位数是2,小于等于2的数有1个,所以填入index为0的地方,小于等于2的数数量--,count累加[0,0,0,2,3,4,5,5,5,5]
备用数组[12,23,123,45,35]

第二次按照十位数的值排序
count[0,1,2,1,1,0,0,0,0,0]十位数为1的值有1个,为2的有两个,为3的有1个,为4的有1个
count累加[0,1,3,4,5,5,5,5,5,5]十位数为小于等于1的有1个,小于等于2的有3个,小于等于4的有4个,小于等于5的有5个
将[12,23,123,45,35]按照从右往左的顺序填入与该数组相同大小的备用数组中
对于35,十位数是3,小于等于3的数有4个,所以填入index为3的地方,小于等于3的数数量--,count累加[0,1,3,3,5,5,5,5,5,5]
对于45,十位数是4,小于等于4的数有4个,所以填入index为4的地方,小于等于4的数数量--,count累加[0,1,3,3,4,5,5,5,5,5]
对于123,十位数是2,小于等于2的数有3个,所以填入index为2的地方,小于等于2的数数量--,count累加[0,1,2,3,4,5,5,5,5,5]
对于23,十位数是2,小于等于2的数有2个,所以填入index为1的地方,小于等于2的数数量--,count累加[0,1,1,3,4,5,5,5,5,5]
对于12,十位数是1,小于等于1的数有1个,所以填入index为0的地方,小于等于1的数数量--,count累加[0,0,2,3,4,5,5,5,5,5]
备用数组[12,23,123,35,45]

第三次按照百位数的值排序
count[4,1,0,0,0,0,0,0,0,0]百位数为0的值有4个,为1的有1个
count累加[4,5,5,45,5,5,5,5,5,5]百位数为小于等于0的有4个,小于等于1的有5个
将[12,23,123,35,45]按照从右往左的顺序填入与该数组相同大小的备用数组中
不详细叙述啦,最终
备用数组[12,23,35,45,123]

实现

package com.kuang.example01;

/**
 * 功能描述
 *
 * @since 2022-10-29
 */
public class RadixSort {
    /**
     *
     * @param arr 待排序数组
     * @param l 数组待排序的左下标
     * @param r 数组待排序的右下标
     * @param digit 最大数的十进制位数,如100,digit为3,10000,digit为5
     */
    public void radixSort(int[] arr, int l, int r, int digit){
        // 基数设置为10,即待排序的数是几进制
        final int radix = 10;
        // 准备一个辅助空间
        int[] help = new int[r-l+1];
        for (int i = 1; i <= digit; i++) {
            int[] count = new int[10];
            for (int j = l; j <=r ; j++) {
                int value =  getDigit(arr[j],i);
                count[value]++;
            }
            for (int j = 1; j < count.length; j++) {
                count[j]+=count[j-1];
            }

            for (int j = r; j >=l ; j--) {
                int value =  getDigit(arr[j],i);
                help[count[value]-1] = arr[j];
                count[value]--;
            }

            for (int j = l; j < r-l+1; j++) {
                arr[j]=help[j];
            }
        }
    }

    public static int maxBits(int[] arr){
        int result=0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max,arr[i]);
        }

        while(max!=0){
            max /=10;
            result++;
        }
        return result;
    }

    public static int getDigit(int value, int d){
        return (value/((int)Math.pow(10,d-1)) %10);
    }

    public static void main(String[] args) {
        int[] arr ={10,45,36,87,123,456,34};
        int digit = maxBits(arr);
        RadixSort sort = new RadixSort();
        sort.radixSort(arr,0,6, digit);
        System.out.println(arr);

    }
}

标签:count,index,int,45,s004,数组,排序
From: https://www.cnblogs.com/Oh-mydream/p/16840647.html

相关文章

  • Shell脚本之数组排序
    数组排序(使用tr、sort、for)操作步骤;使用tr命令将数组内每个元素之间的空格替换为换行符;之后使用sort命令按从小到大重新排序;最后使用for循环遍历排序后的元素值。......
  • js-基础排序实现(冒泡排序,快速排序,选择排序,插入排序,希尔排序,归并排序,堆排序)
    冒泡排序:两个指针循环,遇到不合适就交换,直到将符合要求的浮到边界functionbubbleSort(list){ for(leti=0;i<list.length;i++){ for(letj=0;j<list.length-i-1;j++)......
  • 冒泡排序
    <!DOCTYPEhtml><html>   <head>      <metacharset="utf-8">      <title></title>   </head>   <body>      <scripttype="text/......
  • 冒泡排序
    packageclass01;importjava.util.Arrays;/***冒泡排序*概述:每相邻的2个数比较,较大的数向后交换。排到最后一个位置时,它就是整个数组的最大值,第一轮结束。*......
  • 插入排序
    packageclass01;importjava.util.Arrays;/***插入排序*概述:先将i指向第二个数(索引为1),将j指向i-1位置,如果j大于等于0,并且arr[j]>arr[j+1],将将arr[j]和arr[j+......
  • 选择排序
    packageclass01;importjava.util.Arrays;/***选择排序*概述:n个数,n次循环(10个数就是10次循环),每次循环找出本轮的最小值,和本轮的第一个位置的数,交换。周而复......
  • 选择排序
    #include<stdio.h>#include<string.h>intmain(){inttemp=0;intflag;inta;intt;intarr[10]={};for(inti=0;i<10;i++){ scanf("%d",&a); arr[temp......
  • 【HEOI2016_TJOI2016】排序(线段树分裂&合并)
    线段树分裂&合并入门题。对于每个单调段用一个权值线段树维护。一次操作相当于先对\(l,r\)所在的单调段的权值线段树分裂,然后再合并若干棵的权值线段树。线段树分裂和......
  • 【AGC010E】Rearranging(博弈,图论,拓扑排序)
    考场上想了很久才想到做法,然后考完后又想了很久,加上看了一下一些大佬的博客和Atcoder的官方题解,才完整地证明了整个做法的正确性。综合了一下,在这里详细阐述:首先发现如......
  • 快速排序
    快速排序的思想是这样的,如果要对数组区间[p,r]的数据进行排序,我们先选择其中任意一个数据作为pivot(分支点),一般为区间最后一个元素。然后遍历数组,将小于pivot的数据......