java 桶排序

灰太狼 2022-11-21 09:44 114阅读 0赞

--------------------

### java 桶排序 ###

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**桶排序**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMTYyNQ_size_16_color_FFFFFF_t_70][]

**算法描述：bucketSize表示每个桶可存放不同大小数据的个数**（相同大小数据可重复存放）、**bucketCount表示桶的数量**

**将数据存放入对应的桶中，然后对桶中的数据进行排序**，**排序可继续使用桶排序，也可其他排序方法**

**空间复杂度：o(n)**

**时间复杂度：o(n)**

**算法稳定性：桶排序是稳定的排序算法**

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**示例**

public class MyTest10 {
    
        public static int[] generate(int length){
            int[] a=new int[length];
    
            Random random=new Random();
            for (int i=0;i<length;i++){
                a[i]=random.nextInt(1000);
            }
    
            return a;
        }
    
        public static void bucketSort(int[] a,int pos,int bucketSize){
            if (pos<=1){
                return;
            }
    
            int min=a[0],max=a[0];
            for (int i=0;i<pos;i++){
                if (min>a[i]){
                    min=a[i];
                }
    
                if (max<a[i]){
                    max=a[i];
                }
            }
    
            if (min==max){
                return;
            }
    
            int bucketCount=(max-min)/bucketSize+1;
            int[][] bucket=new int[bucketCount][pos];
            int[] index=new int[bucketCount];
    
            for (int i=0;i<pos;i++){
                int num=(a[i]-min)/bucketSize;
                bucket[num][index[num]++]=a[i];
            }
    
            int index2=0;
            boolean flag=true;
            for (int i=0;i<bucketCount;i++){
                if (bucketSize==1){
                    flag=false;
    
                    for (int j=0;j<index[i];j++){
                        a[index2++]=bucket[i][j];
                    }
                }else {
                    if (index[i]>1){
                        bucketSort(bucket[i],index[i],--bucketSize);
                    }
                }
            }
    
            if (flag){
                for (int i=0;i<bucketCount;i++){
                    for (int j=0;j<index[i];j++){
                        a[index2++]=bucket[i][j];
                    }
                }
            }
        }
    
        public static void main(String[] args){
            int[] a=generate(10);
            System.out.println("数组排序前为：");
            Arrays.stream(a).forEach(i -> System.out.print(i+" "));
    
            bucketSort(a,a.length,5);
            System.out.println("\n\n数组排序后为：");
            Arrays.stream(a).forEach(i -> System.out.print(i+" "));
        }
    }

**控制台输出**

数组排序前为：
    998 579 655 148 973 811 845 486 29 520 
    
    数组排序后为：
    29 148 486 520 579 655 811 845 973 998

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMTYyNQ_size_16_color_FFFFFF_t_70]: /images/20221120/71418b9c908f4348af76419d324325a2.png