桶排序

桶排序介绍

桶排序就是把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。

之后每个桶里面的数据就是有序的了，我们在进行合并汇总。

为方便理解我还准备了图片：

实现原理

为了让大家更好的对桶排序理解，下面形象生动的画出几个桶，其实过程并不复杂，大家可以看到图中分为几个桶，然后在桶里面进行排序，这样子就快了许多，然后合并就是了。

实现代码

package fg;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;

/**
 * @author 皖
 * @data 2020.5.14
 */
public class BuckeStort{
    public static int[]BuckeStort(int[] arr){
        if (arr==null||arr.length<2)return arr;

        int n=arr.length;
        int max=arr[0];
        int min=arr[0];
        //寻找数组中的最大值与最小值
        for (int i = 1; i <n; i++) {
            if (min>arr[i])
                min=arr[i];
            if (max<arr[i])
                max=arr[i];
        }
        //弄一个大小为min偏移值
        int d=max-min;
        //创建 d / 5 + 1 个桶，第 i 桶存放  5*i ~ 5*i+5-1范围的数
        int bucktNum=d/5+1;
        ArrayList<LinkedList<Integer>>bucketList=new ArrayList<>(bucktNum);
        //初始化桶
        for (int i = 0; i <bucktNum ; i++) {
            bucketList.add(new LinkedList<>());

        }
        //遍历数组，将每个元素分别插入桶中
        for (int i = 0; i <n ; i++) {
            bucketList.get((arr[i]-min)/d).add(arr[i]-min);

        }
        //对桶内元素进行排序
        for (int i = 0; i <bucktNum ; i++) {
            Collections.sort(bucketList.get(i));

        }
        //这里然后把排好序之后的数据进行合并汇总放回原来的数组里面
        int k=0;
        for (int i = 0; i <bucktNum; i++) {
            for (Integer t:bucketList.get(i)){
                arr[k++]=t+min;
            }

        }
     return arr;
    }
    public static void main (String[] args) {
        int[] arr = {5, 8, 2, 4, 6, 9, 7, 23, 1,3};

        System.out.print("排序前:  ");
        print(arr);

        BuckeStort(arr);  //此时已经成功

        System.out.print("排序后:  ");
        print(arr);
    }

    // 打印数组
    public static void print(int[] arr) {
        if (arr == null)    return;
        //遍历并且输出
        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

输出测试

排序前:  5 8 2 4 6 9 7 23 1 3 
排序后:  1 2 3 4 5 6 7 8 9 23 

性质：

1、时间复杂度：O(n+k)

2、空间复杂度：O(n+k)

3、稳定排序

4、非原地排序

结尾

我每天一更不是为了装x，其实我也有过想放弃，毕竟看看视频，玩玩儿游戏多舒服，时间过的又快，害，可是这样子下去只能是先甜后苦，最后只会得不尝试，说实话我从初中开始就有了第一步手机，当时酷跑还那么火，我曾经也通宵玩儿，所有的赛道都记熟悉了，我当时比较喜欢跑极速模式，当时可以跑十万多米（确实挺难的)，就这样子稀里糊涂的进了一个普通的高中，继续玩儿，记得中考结束之后出了一个新游戏《英雄战迹》（就是现在的王者荣耀)，当时就上瘾了，雾草这么好玩儿，这不就是手机版本的lol么，就一直玩儿，到现在累计场数都有接近五千场了，咋们来算一个时间帐，就按照五千来算，平均一局就按照20分钟来算吧，总共时间达到了1666小时，换算成天数就是69天，不吃不喝69天，害，现在想起来花一半的时间来写数据结构，也是一个大神了，学校开这个课程也就几十个学时，不过现在的我，也还是很不自觉，偶尔还是会玩儿一下，不过非常少了，基本上一些短视频软件和游戏一周时间加起来不会超过4小时吧，我也有时候会因为心情不好不想学习，但是哪有天天心情好呢，人非草木，岂无情，学习还是得坚持下去，就像我现在虽说会的也是比较基础的但是如果，不坚持下去，就永远也不会，到时候也只会和前两次一样心里只有后悔了，现在幸好还有一年多的时间，也许还可以搏一搏，起码最后不会后悔吧，也许青春永远是充满迷茫的，作为我们这个年纪，玩儿是天性，我也想着玩儿呀，害，希望看老本篇文章的各位好好总结一下，时间是永远不会倒流的，也没有后悔药，也希望以后的岁月我看到这篇文章，又能重温现在这种后浪推前浪的豪情，加油！

欢迎大家和小黄一起学习！
微信公众号：小黄爱编程