草庐IT

桶排序的简单理解

程序员翔仔 2023-03-28 原文

详细描述

桶排序的工作原理是，将序列中的元素分配到有限的桶里，每个桶再分别进行排序（使用别的排序算法或者递归使用桶排序），最终合并成结果序列。

桶排序详细的执行步骤如下：

  1. 找出序列中最小的元素和最大的元素，并计算得到差值范围和映射范围，确定桶的数量；
  2. 遍历整个序列，将每一个元素移动到对应的桶中；
  3. 对每一个桶中的元素进行排序，直到所有的桶中元素都有序；
  4. 合并每一个桶中的元素成为有序序列。

算法图解

问题解疑

桶排序的关键是什么？

桶排序过程中存在两个关键环节：元素到桶的映射规则、排序算法选择。

对于映射规则，如果规则设计过于模糊、宽泛，可能所有元素都映射到同一个桶，导致桶排序往比较类排序算法演变；如果规则设计过于严苛，可能每一个桶只分配到一个元素，导致桶排序往计数排序方式演变。

对于桶中元素的排序，可以继续使用桶排序或者其他排序算法，最终桶排序的复杂度和稳定性，都根据排序算法的选择有所不同。

桶排序的适用于什么场景？

最好时间复杂度的场景是：序列中的元素值范围越小越好，比如对范围只有 10 的序列做排序，申请 10 个桶就能实现遍历一次序列完成排序。

最好空间复杂度的场景是：序列中的元素值均匀分布，最终分配到每一个桶的元素数量都相差不大，这样可以避免数据倾斜的问题。

代码实现

排序接口

package cn.fatedeity.algorithm.sort;

/**
 * 排序接口
 */
public interface Sort {
    int[] sort(int[] numbers);
}

排序抽象类

package cn.fatedeity.algorithm.sort;

/**
 * 排序抽象类
 */
public abstract class AbstractSort implements Sort {
    protected void swap(int[] numbers, int src, int target) {
        int temp = numbers[src];
        numbers[src] = numbers[target];
        numbers[target] = temp;
    }
}

桶排序类

package cn.fatedeity.algorithm.sort;

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

/**
 * 桶排序类
 */
public class BucketSort extends AbstractSort {
    private void swap(List<Integer> numbers, int src, int target) {
        int temp = numbers.get(src);
        numbers.set(src, numbers.get(target));
        numbers.set(target, temp);
    }

    private void insertSort(List<Integer> numbers) {
        for (int i = 1; i < numbers.size(); i++) {
            for (int j = i; j > 0; j--) {
                if (numbers.get(j - 1) <= numbers.get(j)) {
                    break;
                }
                this.swap(numbers, j, j - 1);
            }
        }
    }

    @Override
    public int[] sort(int[] numbers) {
        if (numbers.length <= 1) {
            return numbers;
        }

        int min = numbers[0], max = numbers[0];
        for (int number : numbers) {
            if (number < min) {
                min = number;
            } else if (number > max) {
                max = number;
            }
        }

        // 以 10 为步长
        int bucketNum = (max - min) / 10 + 1;
        List<List<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new ArrayList<>());
        }

        // 将元素分配到桶中
        for (int number : numbers) {
            int index = (number - min) / 10;
            List<Integer> bucket = bucketList.get(index);
            bucket.add(number);
        }

        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            List<Integer> bucket = bucketList.get(i);
            this.insertSort(bucket);
            for (int number : bucket) {
                numbers[index++] = number;
            }
        }
        return numbers;
    }
}
桶排序排序numbersintnumber算法与数据结构

有关桶排序的简单理解的更多相关文章

  1. ruby - 简单获取法拉第超时 - 2

    有没有办法在这个简单的get方法中添加超时选项？我正在使用法拉第3.3。Faraday.get(url)四处寻找，我只能先发起连接后应用超时选项，然后应用超时选项。或者有什么简单的方法？这就是我现在正在做的:conn=Faraday.newresponse=conn.getdo|req|req.urlurlreq.options.timeout=2#2secondsend 最佳答案 试试这个:conn=Faraday.newdo|conn|conn.options.timeout=20endresponse=conn.get(url

  2. ruby - 用 Ruby 编写一个简单的网络服务器 - 2

    我想在Ruby中创建一个用于开发目的的极其简单的Web服务器(不，不想使用现成的解决方案)。代码如下:#!/usr/bin/rubyrequire'socket'server=TCPServer.new('127.0.0.1',8080)whileconnection=server.acceptheaders=[]length=0whileline=connection.getsheaders想法是从命令行运行这个脚本，提供另一个脚本，它将在其标准输入上获取请求，并在其标准输出上返回完整的响应。到目前为止一切顺利，但事实证明这真的很脆弱，因为它在第二个请求上中断并出现错误:/usr/b

  3. ruby-on-rails - 简单的 Ruby on Rails 问题——如何将评论附加到用户和文章？ - 2

    我意识到这可能是一个非常基本的问题，但我现在已经花了几天时间回过头来解决这个问题，但出于某种原因，Google就是没有帮助我。(我认为部分问题在于我是一个初学者，我不知道该问什么......)我也看过O'Reilly的RubyCookbook和RailsAPI，但我仍然停留在这个问题上.我找到了一些关于多态关系的信息，但它似乎不是我需要的(尽管如果我错了请告诉我)。我正在尝试调整MichaelHartl'stutorial创建一个包含用户、文章和评论的博客应用程序(不使用脚手架)。我希望评论既属于用户又属于文章。我的主要问题是:我不知道如何将当前文章的ID放入评论Controller。

  4. ruby - 使用 Ruby 通过 Outlook 发送消息的最简单方法是什么？ - 2

    我的工作要求我为某些测试自动生成电子邮件。我一直在四处寻找，但未能找到可以快速实现的合理解决方案。它需要在outlook而不是其他邮件服务器中，因为我们有一些奇怪的身份验证规则，我们需要保存草稿而不是仅仅发送邮件的选项。显然win32ole可以做到这一点，但我找不到任何相当简单的例子。 最佳答案 假设存储了Outlook凭据并且您设置为自动登录到Outlook，WIN32OLE可以很好地完成此操作:require'win32ole'outlook=WIN32OLE.new('Outlook.Application')message=

  5. postman——集合——执行集合——测试脚本——pm对象简单示例02 - 2

    //1.验证返回状态码是否是200pm.test("Statuscodeis200",function(){pm.response.to.have.status(200);});//2.验证返回body内是否含有某个值pm.test("Bodymatchesstring",function(){pm.expect(pm.response.text()).to.include("string_you_want_to_search");});//3.验证某个返回值是否是100pm.test("Yourtestname",function(){varjsonData=pm.response.json

  6. Qt Designer的简单使用 - 2

    在前面两节的例子中，主界面窗口的尺寸和标签控件显示的矩形区域等，都是用C++代码编写的。窗口和控件的尺寸都是预估的，控件如果多起来，那就不好估计每个控件合适的位置和大小了。用C++代码编写图形界面的问题就是不直观，因此Qt项目开发了专门的可视化图形界面编辑器——QtDesigner（Qt设计师）。通过QtDesigner就可以很方便地创建图形界面文件*.ui，然后将ui文件应用到源代码里面，做到“所见即所得”，大大方便了图形界面的设计。本节就演示一下QtDesigner的简单使用，学习拖拽控件和设置控件属性，并将ui文件应用到Qt程序代码里。使用QtDesigner设计界面在开始菜单中找到「Q

  7. CAN协议的学习与理解 - 2

    最近在学习CAN，记录一下，也供大家参考交流。推荐几个我觉得很好的CAN学习，本文也是在看了他们的好文之后做的笔记首先是瑞萨的CAN入门，真的通透；秀！靠这篇我竟然2天理解了CAN协议！实战STM32F4CAN！原文链接：https://blog.csdn.net/XiaoXiaoPengBo/article/details/116206252CAN详解（小白教程）原文链接：https://blog.csdn.net/xwwwj/article/details/105372234一篇易懂的CAN通讯协议指南1一篇易懂的CAN通讯协议指南1-知乎(zhihu.com)视频推荐CAN总线个人知识总

  8. TimeSformer：抛弃CNN的Transformer视频理解框架 - 2

    Transformers开始在视频识别领域的“猪突猛进”，各种改进和魔改层出不穷。由此作者将开启VideoTransformer系列的讲解，本篇主要介绍了FBAI团队的TimeSformer，这也是第一篇使用纯Transformer结构在视频识别上的文章。如果觉得有用，就请点赞、收藏、关注！paper:https://arxiv.org/abs/2102.05095code(offical):https://github.com/facebookresearch/TimeSformeraccept:ICML2021author:FacebookAI一、前言Transformers(VIT)在图

  9. ruby - 易于初学者理解的 Ruby 库 - 2

    关闭。这个问题不符合StackOverflowguidelines.它目前不接受答案。我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题，以便用事实和引用来回答。关闭3年前。Improvethisquestion我正处于学习Ruby的阶段，我想查看一些小型库的源代码以了解它们是如何构建的。我不知道什么是小型图书馆，但希望SO能推荐一些易于理解的图书馆来学习。因此，如果有人知道一两个非常小的库，这是新手Rubyists学习的好例子，请推荐!我想使用Manveru'sInnatelib，因为它试图保持在2000LOC以下，但我还不熟悉其中经常使用的Ruby速记。也许大约100-5

  10. ruby - 使用 Ruby，计算 n x m 数组的每一列中有多少个 true 的简单方法是什么？ - 2

    给定一个nxmbool数组:[[true,true,false],[false,true,true],[false,true,true]]有什么简单的方法可以返回“该列中有多少个true？”结果应该是[1,3,2] 最佳答案 使用转置得到一个数组，其中每个子数组代表一列，然后将每一列映射到其中的true数:arr.transpose.map{|subarr|subarr.count(true)}这是一个带有inject的版本，应该在1.8.6上运行，没有任何依赖:arr.transpose.map{|subarr|subarr.in

随机推荐