栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【桶排序】十大排序算法之桶排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【桶排序】十大排序算法之桶排序

【桶排序】十大排序算法之桶排序,是属于【稳定】的排序算法。

目录

一、桶排序基本思想

二、桶排序代码实现

2.1、序列长度分桶

2.2、简单分桶

2.3、规约化分桶


一、桶排序基本思想
  • 桶排序,是属于【非比较类】排序(其实我感觉也可以认为是半比较类排序,因为再对每个桶里面的元素排序时候,就可能采用比较类排序方式)。
  • 桶排序,是属于【稳定】的排序算法。
  • 桶排序的思想其实非常简单的:将数据均分为【k】个桶,然后将对于元素放入相应的桶里面,接着在单独对每一个桶里面的元素进行排序操作,所有桶排序完成之后,按照桶的顺序将所有元素输出,最终得到的序列就是排序完成的。
  • 桶排序,其实很少会使用,但是这种思想需要理解,因为由桶排序的思想,衍生出了两个其他的排序方式:【计数排序】和【基数排序】。
  • 桶排序,时间复杂度:【O(n+k)】,空间复杂度:【O(n+k)】。
    • 桶排序的时间复杂度、空间复杂度不是绝对的,而是要根据采取哪种数据结构来判断。
    • 桶排序有个特点,就是要想保证【时间复杂度】最好,就没有办法保证【空间复杂度】最好;相反地,要想保证【空间复杂度】最好,就没办法保证【时间复杂度】最好。

桶排序的使用场景

桶排序,针对那种海量数据,也就是数据量特别大的情况下,并且这些数据都满足某个特殊条件,那么这个时候,就可以考虑采用桶排序。

引用百度百科一个案例:

  • 一年的全国高考考生人数为500 万,分数使用标准分,最低100 ,最高900 ,没有小数,要求对这500 万元素的数组进行排序。
  • 这种情况其他就可以使桶排序,为什么呢???
  • 因为数据量虽然有500万条,但是这些数据最终都是只会分布在【100到900】之间,也就是每个考生的分数只会在【100到900】之间,那么我们就可以按照【100到900】进行分桶,然后将500万条数据分别放入桶里面,即可排序完成。

什么是稳定的排序???

稳定排序:

  • 如果排序数组中,存在相同的元素,假设存在两个元素【3】。
  • 为了标识两个元素【3】的先后顺序,我们假设给它命名为:【3(1)】、【3(2)】。
  • 其中括号里面的表示元素3出现的先后顺序。
  • 如果结果排序之后,两个元素还是保持相同的顺序,即:【3(1)、3(2)】,那么我们就称这个排序是稳定的,否则就是不稳定的排序。

桶排序的基本思想

桶排序,最关键的就是将数据分桶,然后对每个桶里面的数据进行单独的排序操作,所有的桶排序完成之后,按照桶的顺序,依次从桶中取处所有的数据,此时形成的序列就是有序的序列。

桶排序基本思路:

  1. 待排序数组【arr】,求出数组中最大值【max】、最小值【mid】。
  2. 计算差值【diff = max - min】,设置分桶数量【bucketNum】(具体分多少个桶,视情况而定,如何保证分桶合理???)。
  3. 通过1,2两个步骤,可以计算出每个桶中的数据区间:【diff / bucketNum】。
  4. 初始化桶的数据结构,可以利用二维数组,可以利用链表等等。
  5. 遍历待排序数组【arr】,将其中每个数据元素按照某个映射规则,找到其对应哪个桶,然后放入这个桶里面即可。
  6. 遍历结束后,按照桶的顺序,依次取出桶里面的数据元素,那么此时形成的序列,就是排序完成的。

桶排序为什么属于稳定的排序???

看了上面桶排序的基本思想,可以知道桶排序在【分桶】操作过程后,我们需要单独对每个桶进行一次排序,那么这个排序我们就可以选择一个稳定的排序算法来实现,也就可以保证桶排序的最终排序是稳定的。

可以从这个网站查看桶排序的过程【数据结构和算法动态可视化 (Chinese) - VisuAlgo】。

二、桶排序代码实现

2.1、序列长度分桶

前面介绍完了桶排序的思想了,这里编写代码实现桶排序。

  • 桶排序,如何分桶是关键,分多少个桶,以及如何确定分多少个桶???
  • 这些都是需要考虑的问题,不同的分桶方式,可能会影响算法的效率,最直接的分桶就是直接通过【序列长度】作为桶的数量【bucketNum】,然后通过【max - min】除以【bucketNum】将数据放入不同的桶里面。
  • 这种方式的缺点,如果数据有【n】个,那就需要分【n】个桶,显然空间复杂度太高了。
public class BucketSort {
    
    public static void bucketSort(int[] nums) {
        // 1、求最大值和最小值
        int max = nums[0], min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        // 计算差值: 最大值 - 最小值
        int diff = max - min;

        // 2、初始化桶: 按照序列长度分桶
        int bucketNum = nums.length;
        // 创建桶: 链表方式
        List> bucket = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            bucket.add(new ArrayList<>()); // 初始化桶
        }

        // 3、遍历数组,将每个数据分桶存放
        for (int i = 0; i < nums.length; i++) {
            // 计算当前元素应该放入哪个桶里面
            // diff / (bucketNum - 1): 表示每个桶保存多少数据的范围
            // nums[i] - min: 因为第一个桶从[min,mid+k]开始,所以后面的元素都要减去min开始计算区间,相等于将min看作原点0
            int index = (nums[i] - min) / (diff / (bucketNum - 1));
            // 当前元素放入 index 桶里面
            bucket.get(index).add(nums[i]);
        }

        // 4、对每个桶中元素单独进行排序操作
        for (int i = 0; i < bucket.size(); i++) {
            // 每个桶进行一次冒泡排序
            bubbleSort(bucket.get(i));
        }

        // 5、按照桶的顺序,依次输出桶中元素
        int index = 0;
        for (int i = 0; i < bucket.size(); i++) {
            List temp = bucket.get(i);
            for (int j = 0; j < temp.size(); j++) {
                nums[index++] = temp.get(j);
            }
        }
    }
    
    public static void bubbleSort(List nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (nums.get(j) > nums.get(j + 1)) {
                    // 交换元素
                    int temp = nums.get(j);
                    nums.set(j, nums.get(j + 1));
                    nums.set(j + 1, temp);
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {4, 21, 9, 38, 74, 21, 18, 44, 120, 99};
        System.out.println(Arrays.toString(nums));
        bucketSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

2.2、简单分桶

第二种分桶方式:

  • 按照【max - min】差值除以【10】再【加1】作为最终分桶的数量【bucketNum】。
  • 公式:【bucketNum = (max - min) / 10 + 1;】
  • 这种方式,相比较于2.1的方式,在某些情况下,可以很大程度上减少桶的数量。
  • 例如:
    • 100个待排序元素,并且假设最大值等于99,最小值等于2;
    • 按照2.1的方式,直接分【100】个桶;
    • 按照2.2的方式,【bucketNUm  =(99-2)/ 10 + 1】直接分【10】个桶,减少了【10】倍。
  • 当然了,这种分桶也不是绝对的,因为如果元素有100个,但是里面最大值等于10000,最小值是1,那么计算出来的分桶数量就是【1001】,显然还不如直接按照2.1方式进行分桶。
public class BucketSort {
    
    // 简单分桶
    public static void bucketSort(int[] nums) {
        // 1、求最大值和最小值
        int max = nums[0], min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        // 计算差值: 最大值 - 最小值
        int diff = max - min;

        // 2、初始化桶: 按照简单分桶方式
        int bucketNum = (max - min) / 10 + 1;
        // 创建桶: 链表方式
        List> bucket = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            bucket.add(new ArrayList<>()); // 初始化桶
        }

        // 3、遍历数组,将每个数据分桶存放
        for (int i = 0; i < nums.length; i++) {
            // 计算当前元素应该放入哪个桶里面
            // diff / (bucketNum - 1): 表示每个桶保存多少数据的范围
            // nums[i] - min: 因为第一个桶从[min,min + d]开始,所以后面的元素都要减去min开始计算区间,相等于将min看作原点0
            int index = (nums[i] - min) / (diff / (bucketNum - 1));
            // 当前元素放入 index 桶里面
            bucket.get(index).add(nums[i]);
        }

        // 4、对每个桶中元素单独进行排序操作
        for (int i = 0; i < bucket.size(); i++) {
            // 每个桶进行一次冒泡排序
            bubbleSort(bucket.get(i));
        }

        // 5、按照桶的顺序,依次输出桶中元素
        int index = 0;
        for (int i = 0; i < bucket.size(); i++) {
            List temp = bucket.get(i);
            for (int j = 0; j < temp.size(); j++) {
                nums[index++] = temp.get(j);
            }
        }
    }
    
    public static void bubbleSort(List nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (nums.get(j) > nums.get(j + 1)) {
                    // 交换元素
                    int temp = nums.get(j);
                    nums.set(j, nums.get(j + 1));
                    nums.set(j + 1, temp);
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {4, 21, 9, 38, 74, 21, 18, 44, 120, 99};
        System.out.println(Arrays.toString(nums));
        bucketSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

2.3、规约化分桶

前面两个分桶的方式,都不太合理,因为有些桶从始至终都没有存放元素,显然还浪费了内存空间,有没有什么方式可以将那些没有元素的桶给去掉,只保留那些存放元素的桶呢???

  • 根据这个思路,我们可以看到,2.1和2.2两种分桶方式都是一开始就确定多少个桶,有没有什么方式可以不事先确定桶呢,而是在扁你数组的过程中,动态的确定当前数据应该放入哪个桶里面。
  • 如果当前数据没有对应的桶,则创建一个桶,保存当前数据。
  • 我们可以采用【哈希表】来实现,哈希表的【key】作为桶,【value】保存每个数据元素。

如何确定当前数据元素应该放入哪个桶里面???

给出计算数据所属于的桶公式:

  • index = (nums[i] - min) / (max - min) * len;
    • index:表示属于哪个桶。
    • max:表示最大值。
    • min:表示最小值。
    • len:表示数组长度,元素个数。
    • nums[i]:表示当前元素值。
  • 采用这种方式,可以确保,每个数据元素都一定在某个桶里面,并且不会存在空桶。
public class BucketSort {
	
    public static void bucketSort(int[] nums) {
        // 1、求最大值和最小值
        int max = nums[0], min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        // 计算差值: 最大值 - 最小值
        int diff = max - min;

        // 2、初始化桶: 按照规约化分桶
        Map> bucket = new HashMap<>();

        // 3、遍历数组,将每个数据分桶存放
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            // 计算当前元素应该放入哪个桶里面
            int index = (nums[i] - min) / (max - min) * len;
            // 判断是否已经存在当前 index 桶
            if (bucket.containsKey(index)) {
                // 存在桶,则元素直接放入桶里面
                bucket.get(index).add(nums[i]);
            } else {
                // 不存在桶,则创建新桶保存元素
                List temp = new ArrayList<>();
                temp.add(nums[i]);
                bucket.put(index, temp);
            }
        }

        // 4、对每个桶中元素单独进行排序操作
        List keyList = new ArrayList<>(bucket.keySet());
        Collections.sort(keyList);
        // 对 key 进行排序, 从最小的桶开始排序, 然后取出元素
        int index = 0; // 数组下标
        List bucketList = null;
        for (int key : keyList) {
            bucketList = bucket.get(key);
            // 对每个桶进行冒泡排序
            bubbleSort(bucketList);
            // 5、按照桶的顺序,依次输出桶中元素
            for (int i = 0; i < bucketList.size(); i++) {
                nums[index++] = bucketList.get(i);
            }
        }
    }
    
    public static void bubbleSort(List nums) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (nums.get(j) > nums.get(j + 1)) {
                    // 交换元素
                    int temp = nums.get(j);
                    nums.set(j, nums.get(j + 1));
                    nums.set(j + 1, temp);
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {4, 21, 9, 38, 74, 21, 18, 44, 120, 99};
        System.out.println(Arrays.toString(nums));
        bucketSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

桶排序,这里其实我个人还有点不太理解的地方是:

  1. 问题一:规约化分桶的时候,采用【index = (nums[i] - min) / (max - min) * len;】找到哪个桶,具体含义是什么意思???为什么通过这种方式,就可以获取到某个数据对应哪个桶里面???

以上程序运行结果:

综上,就是桶排序相关思想,以及代码实现。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970970.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号