【数据结构】排序算法---桶排序

在这里插入图片描述

文章目录

  • 1. 定义
  • 2. 算法步骤
  • 3. 演示
    • 3.1 动态演示1
    • 3.2 动态演示2
    • 3.3 图片演示1
    • 3.4 图片演示2
  • 4. 性质
  • 5. 算法分析
  • 6. 代码实现
    • C语言
    • Python
    • Java
    • C++
    • Go
  • 结语

1. 定义

桶排序（英文：Bucket sort）是计数排序的升级版，适用于待排序数据值域较大但分布比较均匀的情况。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

2. 算法步骤

桶排序按下列步骤进行：

  1. 设置一个定量的数组当作空桶；

  2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；

  3. 对每个不是空的桶进行排序；

  4. 从不是空的桶里把排好序的数据拼接起来。

3. 演示

3.1 动态演示1

在这里插入图片描述

3.2 动态演示2

在这里插入图片描述

3.3 图片演示1

元素分布在桶中：

在这里插入图片描述

然后，元素在每个桶中排序：

在这里插入图片描述

3.4 图片演示2

在这里插入图片描述

4. 性质

稳定性：

如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法。

由于每块元素不多，一般使用插入排序。此时桶排序是一种稳定的排序算法。

空间复杂度：

桶排序算法排序过程中新建了一个桶和一个输出数组，所以算法的空间复杂度是 O ( N + M ) O(N+M) O(N+M)。

时间复杂度：

桶排序的平均时间复杂度为 O ( n + n 2 k + k ) O(n+{n^2 \over k}+k) O(n+kn2​+k)（将值域平均分成n块 + 排序 + 重新合并元素)，当k≈n时为 O ( n ) O(n) O(n)。

桶排序的最坏时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

什么时候最快：

当输入的数据可以均匀的分配到每一个桶中。

什么时候最慢：

当输入的数据被分配到了同一个桶中。

5. 算法分析

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

6. 代码实现

C语言

void RadixSort(int* arr, int n)
{
	//max为数组中最大最小值
	int max = arr[0];
	int min = arr[0];
	int base = 1;

	//找出数组中的最大值
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	//循环结束max就是数组最大最小值

	//循环将数组的元素全部变为正数
	//所有元素加上最小值的绝对值
	for (int i = 0; i < n; i++)
	{
		arr[i] += abs(min);
	}

	//临时存放数组元素的空间
	int* tmp = (int*)malloc(sizeof(int)*n);

	//循环次数为最大数的位数
	while (max / base > 0)
	{
		//定义十个桶，桶里面装的不是数据本身，而是每一轮排序对应（十、白、千...）位的个数
		//统计每个桶里面装几个数
		int bucket[10] = { 0 };
		for (int i = 0; i < n; i++)
		{
			//arr[i] / base % 10可以取到个位、十位、百位对应的数字
			bucket[arr[i] / base % 10]++;
		}
		//循环结束就已经统计好了本轮每个桶里面应该装几个数


		//将桶里面的元素依次累加起来，就可以知道元素存放在临时数组中的位置
		for (int i = 1; i < 10; i++)
		{
			bucket[i] += bucket[i - 1];
		}
		//循环结束现在桶中就存放的是每个元素应该存放到临时数组的位置


		//开始放数到临时数组tmp
		for (int i = n - 1; i >= 0; i--)
		{
			tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
			bucket[arr[i] / base % 10]--;
		}
		//不能从前往后放，因为这样会导致十位排好了个位又乱了，百位排好了十位又乱了
		/*for (int i = 0; i < n; i++)
		{
			tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
			bucket[arr[i] / base % 10]--;
		}*/

		//把临时数组里面的数拷贝回去
		for (int i = 0; i < n; i++)
		{
			arr[i] = tmp[i];
		}
		base *= 10;
	}
	free(tmp);

	//还原原数组
	for (int i = 0; i < n; i++)
	{
		arr[i] -= abs(min);
	}
}

Python

N = 100010
w = n = 0
a = [0] * N
bucket = [[] for i in range(N)]


def insertion_sort(A):
    for i in range(1, len(A)):
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = key


def bucket_sort():
    bucket_size = int(w / n + 1)
    for i in range(0, n):
        bucket[i].clear()
    for i in range(1, n + 1):
        bucket[int(a[i] / bucket_size)].append(a[i])
    p = 0
    for i in range(0, n):
        insertion_sort(bucket[i])
        for j in range(0, len(bucket[i])):
            a[p] = bucket[i][j]
            p += 1

Java

public class BucketSort extends BaseSort {

    public static void main(String[] args) {
        BucketSort sort = new BucketSort();
        sort.printNums();
    }

    @Override
    protected void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        bucketSort(nums);
    }

    public void bucketSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        //找出最大值，最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        int length = nums.length;
        //桶的数量
        int bucketCount = (max - min) / length + 1;
        int[][] bucketArrays = new int[bucketCount][];
        //遍历数组，放入桶内
        for (int i = 0; i < length; i++) {
            //找到桶的下标
            int index = (nums[i] - min) / length;
            //添加到指定下标的桶里，并且使用插入排序排序
            bucketArrays[index] = insertSortArrays(bucketArrays[index], nums[i]);
        }
        int k = 0;
        //合并全部桶的
        for (int[] bucketArray : bucketArrays) {
            if (bucketArray == null || bucketArray.length == 0) {
                continue;
            }
            for (int i : bucketArray) {
                //把值放回到nums数组中
                nums[k++] = i;
            }
        }
    }

    //每个桶使用插入排序进行排序
    private int[] insertSortArrays(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return new int[]{num};
        }
        //创建一个temp数组，长度是arr数组的长度+1
        int[] temp = new int[arr.length + 1];
        //把传进来的arr数组，复制到temp数组
        for (int i = 0; i < arr.length; i++) {
            temp[i] = arr[i];
        }
        //找到一个位置，插入，形成新的有序的数组
        int i;
        for (i = temp.length - 2; i >= 0 && temp[i] > num; i--) {
            temp[i + 1] = temp[i];
        }
        //插入需要添加的值
        temp[i + 1] = num;
        //返回
        return temp;
    }
}

C++

#include<iterator>
#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;

struct ListNode{
        explicit ListNode(int i=0):mData(i),mNext(NULL){}
        ListNode* mNext;
        int mData;
};

ListNode* insert(ListNode* head,int val){
        ListNode dummyNode;
        ListNode *newNode = new ListNode(val);
        ListNode *pre,*curr;
        dummyNode.mNext = head;
        pre = &dummyNode;
        curr = head;
        while(NULL!=curr && curr->mData<=val){
                pre = curr;
                curr = curr->mNext;
        }
        newNode->mNext = curr;
        pre->mNext = newNode;
        return dummyNode.mNext;
}


ListNode* Merge(ListNode *head1,ListNode *head2){
        ListNode dummyNode;
        ListNode *dummy = &dummyNode;
        while(NULL!=head1 && NULL!=head2){
                if(head1->mData <= head2->mData){
                        dummy->mNext = head1;
                        head1 = head1->mNext;
                }else{
                        dummy->mNext = head2;
                        head2 = head2->mNext;
                }
                dummy = dummy->mNext;
        }
        if(NULL!=head1) dummy->mNext = head1;
        if(NULL!=head2) dummy->mNext = head2;
        
        return dummyNode.mNext;
}

void BucketSort(int n,int arr[]){
        vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
        for(int i=0;i<n;++i){
                int index = arr[i]/BUCKET_NUM;
                ListNode *head = buckets.at(index);
                buckets.at(index) = insert(head,arr[i]);
        }
        ListNode *head = buckets.at(0);
        for(int i=1;i<BUCKET_NUM;++i){
                head = Merge(head,buckets.at(i));
        }
        for(int i=0;i<n;++i){
                arr[i] = head->mData;
                head = head->mNext;
        }
}

Go

package main
 
import (
	"fmt"
	"container/list"
)
 
func bucketSort(theArray []int,num int){
	var theSort [99]int
	for i:=0;i< len(theArray);i++{
		theSort[10]=1
		if theSort[theArray[i]] !=0{
			theSort[theArray[i]] = theSort[theArray[i]]+1
		}else{
			theSort[theArray[i]] = 1
		}
	}
	l:=list.New()
	for j:=0;j<len(theSort);j++{
		if theSort[j]==0{
			//panic("error test.....")
		}else{
			for k:=0;k<theSort[j];k++{
				l.PushBack(j)
			}
		}
	}
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " ")
	}
 
}
 
func main() {
	var theArray = []int{10, 1, 18, 30, 23, 12, 7, 5, 18, 17}
	fmt.Print("排序前")
	fmt.Println(theArray)
	fmt.Print("排序后")
	bucketSort(theArray,11)
}

结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。

也可以点点关注，避免以后找不到我哦！

Crossoads主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是作者前进的动力！

带你初步了解排序算法：https://blog.csdn.net/2301_80191662/article/details/142211265
直接插入排序：https://blog.csdn.net/2301_80191662/article/details/142300973
希尔排序：https://blog.csdn.net/2301_80191662/article/details/142302553
直接选择排序：https://blog.csdn.net/2301_80191662/article/details/142312028
堆排序：https://blog.csdn.net/2301_80191662/article/details/142312338
冒泡排序：https://blog.csdn.net/2301_80191662/article/details/142324131
快速排序：https://blog.csdn.net/2301_80191662/article/details/142324307
归并排序：https://blog.csdn.net/2301_80191662/article/details/142350640
计数排序：https://blog.csdn.net/2301_80191662/article/details/142350741
桶排序：https://blog.csdn.net/2301_80191662/article/details/142375338
基数排序：https://blog.csdn.net/2301_80191662/article/details/142375592
十大经典排序算法总结与分析：https://blog.csdn.net/2301_80191662/article/details/142211564

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/883579.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

C# 利用simd比较两个文件是否相等（高性能）

C# 利用simd比较两个文件是否相等（高性能）

主要用到两个指令集&#xff0c;CompareEqual指令与MoveMask指令&#xff0c;因为电脑cpu原因&#xff0c;我们采用Avx2。 Avx2.CompareEqual&#xff0c;比较两个Vector256<byte>向量&#xff0c;如果元素相同返回255&#xff0c;否则返回0。 Avx2.MoveMask如果Vector…
阅读更多...
【初阶数据结构】详解二叉树 - 树和二叉树（三）（递归的魅力时刻）

【初阶数据结构】详解二叉树 - 树和二叉树（三）（递归的魅力时刻）

文章目录 前言1. 二叉树链式结构的意义2. 手搓一棵二叉树3. 二叉树的遍历&#xff08;重要&#xff09;3.1 遍历的规则3.2 先序遍历3.3 中序遍历3.4 后序遍历3.5 遍历的代码实现3.5.1 先序遍历代码实现3.5.2 中序遍历代码实现3.5.3 后序遍历代码实现 4. 统计二叉树结点的个数5.…
阅读更多...
2024年9月26日--- Spring-AOP

2024年9月26日--- Spring-AOP

SpringAOP 在学习编程过程中&#xff0c;我们对于公共方法的处理应该是这样的一个过程&#xff0c;初期阶段如下 f1(){Date now new Date();System.out.println("功能执行之前的各种前置工作"now)//...功能代码//...功能代码System.out.println("功能执行之前…
阅读更多...
Fyne ( go跨平台GUI )中文文档-入门(一)

Fyne ( go跨平台GUI )中文文档-入门(一)

本文档注意参考官网(developer.fyne.io/) 编写, 只保留基本用法go代码展示为Go 1.16 及更高版本, ide为goland2021.2 这是一个系列文章&#xff1a; Fyne ( go跨平台GUI )中文文档-入门(一)-CSDN博客 Fyne ( go跨平台GUI )中文文档-Fyne总览(二)-CSDN博客 Fyne ( go跨平台GUI )…
阅读更多...
SpringSecurity-用户认证

SpringSecurity-用户认证

1、用户认证 1.1 用户认证核心组件 我们系统中会有许多用户&#xff0c;确认当前是哪个用户正在使用我们系统就是登录认证的最终目的。这里我们就提取出了一个核心概念&#xff1a;当前登录用户/当前认证用户。整个系统安全都是围绕当前登录用户展开的&#xff0c;这个不难理…
阅读更多...
【若依RuoYi-Vue | 项目实战】帝可得后台管理系统（二）

【若依RuoYi-Vue | 项目实战】帝可得后台管理系统（二）

文章目录 一、人员管理1、需求说明2、生成基础代码&#xff08;1&#xff09;创建目录菜单&#xff08;2&#xff09;添加数据字典&#xff08;3&#xff09;配置代码生成信息&#xff08;4&#xff09;下载代码并导入项目 3、人员列表改造&#xff08;1&#xff09;基础页面&a…
阅读更多...
Latex和Vscode安装和配置

Latex和Vscode安装和配置

一、Latex安装教程 打开清华大学开源软件镜像站&#xff0c;下载texlive.iso文件 右键点击ios文件&#xff0c;点击装载 配置latex安装 4. 安装过程 二、VScode安装和配置教程 打开Vscode官网&#xff0c;下载安装包 2.右键&#xff0c;以管理员身份运行VSCode安装包&#…
阅读更多...
基于深度学习的药品三期OCR字符识别

基于深度学习的药品三期OCR字符识别

在药品生产线上，药品三期的喷码与条形码识别是保证药品追溯和安全管理的重要环节。传统的识别方法依赖于人工操作，不仅效率低下且容易出错。随着深度学习技术的不断发展，基于OCR（Optical Character Recognition，光学字符识别）的自动化识别系统逐渐成为主流。本文将以哪吒…
阅读更多...
微服务注册中⼼1

微服务注册中⼼1

1. 微服务的注册中⼼ 注册中⼼可以说是微服务架构中的”通讯录“ &#xff0c;它记录了服务和服务地址的映射关系。在分布式架构中&#xff0c; 服务会注册到这⾥&#xff0c;当服务需要调⽤其它服务时&#xff0c;就这⾥找到服务的地址&#xff0c;进⾏调⽤。 1.1 注册中⼼的…
阅读更多...
linux信号 | 学习信号三步走 | 全解析信号的产生方式

linux信号 | 学习信号三步走 | 全解析信号的产生方式

前言&#xff1a;本节内容是信号&#xff0c; 主要讲解的是信号的产生。信号的产生是我们学习信号的第二个阶段。 我们已经学习过第一个阶段——信号的概念与预备知识&#xff08;没有学过的友友可以查看我的前一篇文章&#xff09;。 以及我们还没有学习信号的第三个阶段——信…
阅读更多...
CleanMyMac X 评价、介绍、使用教学|Mac系统最推荐的系统优化和清理软件工具!

CleanMyMac X 评价、介绍、使用教学|Mac系统最推荐的系统优化和清理软件工具!

本篇文章要带大家看一款知名的Mac系统优化、清理工具– CleanMyMac X &#xff0c;并且也会附上详细的介绍和使用教学。 链接: https://pan.baidu.com/s/1_TFnrIVH1NGsZPsA3lpwAA 提取码: dpjw CleanMyMac X-安装包&#xff1a;https://souurl.cn/QUYb57 为什么Mac电脑需要装系…
阅读更多...
Cocos 3.8.3 实现外描边效果（逃课玩法）

Cocos 3.8.3 实现外描边效果（逃课玩法）

本来想着用Cocos 的Shader Graph照搬Unity的思路来加外描边&#xff0c;发现不行&#xff0c;然后我就想弄两个物体不就行了吗&#xff0c;一个是放大的版本&#xff0c;再放大的版本上加一个材质&#xff0c;这个材质面剔除选择前面的面剔除就行了&#xff0c;果不其然还真行。…
阅读更多...
前端开发必备：实用Tool封装工具类方法大全

前端开发必备：实用Tool封装工具类方法大全

程序员必备宝典网站https://tmxkj.top/#/ 1.判断空值 /*** 判断是否是空值*/ export function isEmpty(value) {if (typeof value string) {return value.length 0 || value "";} else if (typeof value number) {return value 0;} else if (Array.isArray(va…
阅读更多...
Kafka 面试题

Kafka 面试题

参考&#xff1a; https://javabetter.cn/interview/kafka-40.htmlhttps://javaguide.cn/high-performance/message-queue/kafka-questions-01.html Kafka 架构 名词概念 Producer&#xff08;生产者&#xff09; : 产生消息的一方。 Consumer&#xff08;消费者&#xff09; …
阅读更多...
MySQL---创建数据库（基于SQLyog）

MySQL---创建数据库（基于SQLyog）

目录 0.前言 1.基本认识 1.1编码集 1.2检验规则 2.库的创建和销毁 2.1指令介绍 2.2你可能会出现的问题 3.查看数据库属性 4.创建指定数据库 5.创建表操作 0.前言 之前写过一篇这个关于表的创建和销毁的操作&#xff0c;但是当时是第一次学习&#xff0c;肯定有些地方…
阅读更多...
failed to load steamui.dll的多种处理方法，steamui.dll的作用

failed to load steamui.dll的多种处理方法，steamui.dll的作用

在使用Steam平台时&#xff0c;不少玩家可能会遇到“failed to load steamui.dll”这样令人头疼的错误提示。这个错误会阻碍Steam客户端的正常运行&#xff0c;影响我们享受游戏和Steam平台的各种服务。不过&#xff0c;不必过于担心&#xff0c;因为有多种方法可以尝试解决这个…
阅读更多...
【Linux】当前进展

【Linux】当前进展

驱动层日志添加了下文件目录&#xff0c;函数&#xff0c;代码行的打印&#xff08;这里要小心&#xff0c;驱动目录源代码打印日志里边添进程号可能有问题&#xff0c;因为在驱动初始化的时候&#xff0c;内核还没有创建进程&#xff0c;不过猜测可以先不打印进程相关信息&…
阅读更多...
C++ | Leetcode C++题解之第419题棋盘上的战舰

C++ | Leetcode C++题解之第419题棋盘上的战舰

题目&#xff1a; 题解&#xff1a; class Solution { public:int countBattleships(vector<vector<char>>& board) {int row board.size();int col board[0].size();int ans 0;for (int i 0; i < row; i) {for (int j 0; j < col; j) { if (board…
阅读更多...
Linux下线程间的通信

Linux下线程间的通信

为什么需要线程通信&#xff1f; 线程是操作系统调度的最小单元&#xff0c;拥有自己的栈空间。如果线程之间孤立运行&#xff0c;可能会导致资源浪费。线程需要协调工作以完成共同的任务&#xff0c;这就需要线程间相互通信 在 Linux 系统中&#xff0c;线程间通信&#xff…
阅读更多...
MySQL数据库进阶知识（四）《视图、存储过程、触发器》

MySQL数据库进阶知识（四）《视图、存储过程、触发器》

学习目标&#xff1a; 掌握数据库视图基础知识 掌握数据库存储过程原理 掌握数据库触发器相关知识 学习内容&#xff1a; 一. 视图 介绍 视图&#xff08;View&#xff09;是一种虚拟存在的表。视图中的数据并不在数据库中实际存在&#xff0c;行和列数据来自定义视图的查询…
阅读更多...
最新文章

Copyright @ 2022~2023