首页 > 编程语言 >桶排序算法及优化（java）

桶排序算法及优化（java）

时间：2024-08-21 11:52:11浏览次数：9  
标签：java int buckets List value 算法 array 排序

目录

1.1 引言

1.2 桶排序的历史

1.3 桶排序的基本原理

1.3.1 工作流程

1.3.2 关键步骤

1.4 桶排序的Java实现

1.4.1 简单实现

1.4.2 优化实现

1.4.3 代码解释

1.5 桶排序的时间复杂度

1.5.1 分析

1.5.2 证明

1.6 桶排序的稳定性

1.7 著名案例

1.7.1 应用场景

1.7.2 具体案例

1.8 桶排序的优化方案

1.8.1 选择合适的桶数量

1.8.2 桶内排序算法的选择

1.8.3 处理数据分布不均的情况

1.8.4 Java示例代码

1.8.5 代码解释

1.9 总结

1.1 引言

桶排序是一种非比较型整数排序算法，它通过将元素分布到有限数量的“桶”中，然后对每个桶内的元素进行排序（通常使用其他排序算法），最后按顺序合并各个桶来完成排序。本文将详细介绍桶排序的历史背景、工作原理，并通过具体案例来阐述其应用。此外，还将探讨桶排序的不同优化方案，并给出相应的Java代码示例。

1.2 桶排序的历史

桶排序的思想可以追溯到20世纪初期，它最初是为了处理大规模数据集而提出的。随着计算机科学的发展，桶排序逐渐成为一种常用的排序算法，尤其是在需要快速处理大量相似范围内的数据时。

桶排序之所以重要，是因为它可以在特定条件下达到线性时间复杂度 O(n)，这对于某些特定的数据分布非常有效。特别是当输入数据分布在一定范围内时，桶排序可以提供非常高的排序效率。

1.3 桶排序的基本原理

先来看个示例，老师安排同学们考试结束后，接到教学主任的通知需要马上把同学们的分数统计并做好排序，但是他来到教室，发现教室后面只有5个垃圾桶，老师冥思苦想，要用这几个垃圾桶怎么把同学们的分数给排名出来呢？

  • 首先还是给垃圾桶标号，这个还是不能少的。
  • 约定，1号垃圾桶放分数是1-20的同学的成绩单，2号垃圾桶放分数是20-40的同学的成绩单，3号垃圾桶放分数是40-60的同学的成绩单，4号垃圾桶放分数是60-80的同学的成绩单，5号垃圾桶放分数是80-100的同学的成绩单。
  • 当向同一个垃圾桶放入新数据的时候，先判断桶中最高分成绩和新放入成绩的大小，如果比原来最高分还高，则把新插入成绩放在原来成绩的后面。
  • 否则，把放入的新的成绩单与原来的成绩单从后往前依次比较，如果存在的成绩大于新放入的成绩，则存在的成绩往后挪一个位置，循环比较已存放的所有成绩单，如第一个桶已经有了63，再插入51，67后，桶中的排序为(51,63,67)一般通过链表来存放桶中数据。
  • 阿布老师依次从1~5号桶捡起自己仍进来的成绩单，（然后依次输出所有（非空）桶里面的数据）最后完成排序。

1.3.1 工作流程

桶排序的基本步骤如下：

  1. 初始化：根据输入数据的范围和特性，创建适当数量的空桶。
  2. 分配：遍历输入数组，将每个元素放入对应的桶中。
  3. 排序：对每个桶内的元素进行排序（可以使用任何排序算法，如插入排序）。
  4. 合并：按顺序合并各个桶中的元素，得到最终排序结果。

1.3.2 关键步骤

  • 桶的选择：根据数据的分布选择合适的桶数量。
  • 桶内排序：选择适当的排序算法对每个桶内的数据进行排序。
  • 合并桶：按顺序合并各个桶中的数据。

1.4 桶排序的Java实现

1.4.1 简单实现

下面是一个简单的桶排序Java代码示例：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BucketSortSimple {

    public static void bucketSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int max = getMax(array);
        List<List<Integer>> buckets = createBuckets(max, array.length);
        distributeElements(array, buckets);
        sortAndMerge(buckets, array);
    }

    private static int getMax(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        return max;
    }

    private static List<List<Integer>> createBuckets(int max, int bucketCount) {
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        return buckets;
    }

    private static void distributeElements(int[] array, List<List<Integer>> buckets) {
        for (int element : array) {
            int index = element / (buckets.size() - 1);
            buckets.get(index).add(element);
        }
    }

    private static void sortAndMerge(List<List<Integer>> buckets, int[] array) {
        int index = 0;
        for (List<Integer> bucket : buckets) {
            Integer[] bucketArray = bucket.toArray(new Integer[0]);
            Arrays.sort(bucketArray);
            for (Integer value : bucketArray) {
                array[index++] = value;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("原始数组:");
        printArray(array);

        bucketSort(array);

        System.out.println("排序后的数组:");
        printArray(array);
    }

    private static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

1.4.2 优化实现

接下来是一个优化后的桶排序Java代码示例，其中考虑了更多的细节，如桶的数量选择、桶内排序算法的选择等：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BucketSortOptimized {

    public static void bucketSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int value : array) {
            if (value < min) min = value;
            if (value > max) max = value;
        }

        int range = max - min + 1;
        int bucketCount = (int) Math.sqrt(array.length); // 选择桶的数量
        List<List<Integer>> buckets = createBuckets(bucketCount);

        // 分配元素到桶中
        for (int value : array) {
            int index = (value - min) * bucketCount / range;
            buckets.get(index).add(value);
        }

        // 排序并合并桶
        sortAndMerge(buckets, array, min);

    }

    private static List<List<Integer>> createBuckets(int bucketCount) {
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        return buckets;
    }

    private static void sortAndMerge(List<List<Integer>> buckets, int[] array, int min) {
        int index = 0;
        for (List<Integer> bucket : buckets) {
            Integer[] bucketArray = bucket.toArray(new Integer[0]);
            Arrays.sort(bucketArray);
            for (Integer value : bucketArray) {
                array[index++] = value;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("原始数组:");
        printArray(array);

        bucketSort(array);

        System.out.println("排序后的数组:");
        printArray(array);
    }

    private static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

1.4.3 代码解释

  • 初始化：找到数组中的最小值和最大值，以确定数据的范围。
  • 桶的选择：根据数组的大小选择合适的桶数量。
  • 分配：将每个元素分配到对应的桶中。
  • 排序：使用内置的 Arrays.sort() 方法对每个桶内的元素进行排序。
  • 合并：按顺序合并各个桶中的元素。

1.5 桶排序的时间复杂度

桶排序的时间复杂度取决于桶的数量、桶内排序算法的时间复杂度以及输入数据的分布情况。

平均时间复杂度：O(n + k)
最佳时间复杂度：O(n + k)
最差时间复杂度：O(n ^ 2)
空间复杂度：O(n * k)
稳定性：稳定

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。 

1.6 桶排序的稳定性

桶排序是稳定的排序算法，只要桶内排序也是稳定的，桶排序就能保持输入数据的相对顺序不变。

1.7 著名案例

1.7.1 应用场景

桶排序在处理大规模数据集时特别有用，尤其是当数据分布较为均匀时。下面通过一个具体的案例来说明桶排序的应用。

1.7.2 具体案例

案例描述：假设我们有一个包含100000个整数的数组，这些整数的范围在1到1000之间。我们需要快速地对这些整数进行排序。

解决方案：使用桶排序可以有效地解决这个问题。

  1. 初始化：创建1000个空桶。
  2. 分配：遍历数组，将每个整数分配到对应的桶中。
  3. 排序：对每个桶内的元素使用计数排序。
  4. 合并：按顺序合并各个桶中的元素。

具体步骤：

  1. 初始化：创建1000个空桶。
  2. 分配：遍历数组，将每个整数分配到对应的桶中。
  3. 排序：对每个桶内的元素使用计数排序。
  4. 合并：按顺序合并各个桶中的元素。

效果：由于数据分布较为均匀，桶排序可以快速完成排序任务，且时间复杂度接近 O(n)。

1.8 桶排序的优化方案

1.8.1 选择合适的桶数量

选择合适的桶数量对于桶排序的性能至关重要。一个常见的做法是使用根号n作为桶的数量，其中 n 是数组的长度。

1.8.2 桶内排序算法的选择

对于桶内的排序，可以选择更高效的排序算法，如计数排序或基数排序，以减少排序的时间复杂度。

1.8.3 处理数据分布不均的情况

当数据分布不均时，可以通过预处理步骤来改善数据分布，如对数据进行归一化处理。

1.8.4 Java示例代码

下面是一个考虑了更多优化因素的桶排序Java代码示例：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BucketSortAdvanced {

    public static void bucketSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int value : array) {
            if (value < min) min = value;
            if (value > max) max = value;
        }

        int range = max - min + 1;
        int bucketCount = (int) Math.sqrt(array.length); // 选择桶的数量
        List<List<Integer>> buckets = createBuckets(bucketCount);

        // 分配元素到桶中
        for (int value : array) {
            int index = (value - min) * bucketCount / range;
            buckets.get(index).add(value);
        }

        // 排序并合并桶
        sortAndMerge(buckets, array, min);

    }

    private static List<List<Integer>> createBuckets(int bucketCount) {
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        return buckets;
    }

    private static void sortAndMerge(List<List<Integer>> buckets, int[] array, int min) {
        int index = 0;
        for (List<Integer> bucket : buckets) {
            Integer[] bucketArray = bucket.toArray(new Integer[0]);
            countSort(bucketArray); // 使用计数排序
            for (Integer value : bucketArray) {
                array[index++] = value;
            }
        }
    }

    private static void countSort(Integer[] array) {
        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        for (int value : array) {
            if (value < minVal) minVal = value;
            if (value > maxVal) maxVal = value;
        }

        int range = maxVal - minVal + 1;
        int[] count = new int[range];

        for (int value : array) {
            count[value - minVal]++;
        }

        int index = 0;
        for (int i = 0; i < range; i++) {
            while (count[i] > 0) {
                array[index++] = i + minVal;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("原始数组:");
        printArray(array);

        bucketSort(array);

        System.out.println("排序后的数组:");
        printArray(array);
    }

    private static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

1.8.5 代码解释

  • 初始化：找到数组中的最小值和最大值，以确定数据的范围。
  • 桶的选择：根据数组的大小选择合适的桶数量。
  • 分配：将每个元素分配到对应的桶中。
  • 排序：使用计数排序对每个桶内的元素进行排序。
  • 合并：按顺序合并各个桶中的元素。

1.9 总结

桶排序是计数排序的变种，它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。把计数排序中相邻的m个”小桶”放到一个”大桶”中，在分完桶后，对每个桶进行排序（一般用快排），然后合并成最后的结果。

算法思想和散列中的开散列法差不多，当冲突时放入同一个桶中；可应用于数据量分布比较均匀，或比较侧重于区间数量时。

桶排序最关键的建桶，如果桶设计得不好的话桶排序是几乎没有作用的。通常情况下，上下界有两种取法，第一种是取一个10^n或者是2^n的数，方便实现。另一种是取数列的最大值和最小值然后均分作桶。

标签：java,int,buckets,List,value,算法,array,排序
From： https://blog.csdn.net/weixin_43841461/article/details/141365406

相关文章

  • 【CSP：202312-1】仓库规划（Java）
    题目链接202312-1仓库规划题目描述求解思路暴力求解：由于数据量较小，对每个仓库进行遍历求解即可。需要注意只有一个仓库的特殊情况。（n=1......
  • 【CSP：202312-2】因子化简（Java）
    题目链接202312-2因子化简题目描述求解思路哈希表：利用哈希表记录下每个因数出现的次数。从222开始遍历，找出......
  • [Lgxの归纳] 动态规划算法
    参考文章：dp题方法总汇-YeahPotato组合问题选讲-command_block前言2023NOI大纲中，写明了动态规划入门算法为四级难度，属于CSP-J的考察范围。在联合省选2024中，D1T3/D2T1/D2T2，以及NOI2024中，D1T2/D2T2都以不同的形式考察了动态规划算法。甚至在IOI含金量最高......
  • KNN(K近邻)算法之——KD-Tree构建及查找原理
    0前言本文主要讲解KNN算法中用于快速检索最近元素的KD树的构建及查找原理。为了达到最佳阅读效果，请读者按照本文顺序阅读，文章使用了大量图片帮助读者理解。1背景1.1为什么要使用KD-Tree?k近邻法(KNN)最简单的实现方法是线性扫描。这时要计算输入实例与每一个训练实例的......
  • 1Java加强----异常
    1.异常体系1.1异常入门1.1运行时异常publicstaticvoidshow(){//int[]arr={1,2,3};//System.out.println(arr[3]);//.ArrayIndexOutOfBoundsException数组越界异常//Stringstr=null;System.out.println(str.length());//Nul......
  • 2Java加强-----泛型
    1.认识泛型publicclassGenericDemo1{publicstaticvoidmain(String[]args){//目标：认识泛型，搞清楚使用泛型的好处。ArrayListlist=newArrayList();list.add("java");list.add("php");list.add(23);l......
  • 「代码随想录算法训练营」第四十三天 | 图论 part1
    797.所有可能的路径题目链接：https://leetcode.cn/problems/all-paths-from-source-to-target/description/文章讲解：https://programmercarl.com/kamacoder/0098.所有可达路径.html题目难度：中等题目状态：看题解思路一：DFSvoiddfs(vector<vector<int>>&graph,intx,intn......
  • [JAVA]创建多线程的三种方式与区别
    继承Thread类创建线程实现Runnable接口创建线程Callable接口创建线程要学习创建线程，我们要通过代码来演示，这里我们可以通过实现以下参赛者跑步的场景来展开。模拟以下场景                              模拟10......
  • Java SuppressWarnings 注解抑制警告参数记录
    在Java代码中可以通过合理使用@SuppressWarnings注解可以抑制一些不合适的警告，这里记录一下用过的忽略类型参数作用all抑制“可替换为Lambda表达式”的警告Convert2Lambda抑制“可替换为Lambda表达式”的警告unused抑制“方法/字段/属性等从未使用”的警告c......
  • 莫队算法
    前言莫队是由莫涛提出的一种离线算法，是分块与双指针的结合，一般可以在\(O(n\sqrtn)\)或者\(O(n\sqrtm)\)的复杂度解决一些种类问题。普通莫队SP3267DQUERY-D-query给你一个长度为\(n\)的数列\(A\)，\(m\)次询问，每次询问区间\([l,r]\)内的不同数字的个数。如果......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99