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

ops/2024/10/18 20:17:15/

在这里插入图片描述

文章目录

  • 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];}//循环结束现在桶中就存放的是每个元素应该存放到临时数组的位置//开始放数到临时数组tmpfor (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 - 1while j >= 0 and A[j] > key:A[j + 1] = A[j]j -= 1A[j + 1] = keydef 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 = 0for 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();}@Overrideprotected 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数组的长度+1int[] 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 mainimport ("fmt""container/list"
)func bucketSort(theArray []int,num int){var theSort [99]intfor i:=0;i< len(theArray);i++{theSort[10]=1if 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.ppmy.cn/ops/117474.html

相关文章

学习最佳实践G4F中的编程技术：获得python项目的当前安装版本

学习最佳实践G4F中的编程技术：获得python项目的当前安装版本

获得当前python软件包版本 用importlib获取软件版本 from importlib.metadata import version as get_package_version, PackageNotFoundError PACKAGE_NAME "g4f"try:x get_package_version(PACKAGE_NAME) except PackageNotFoundError:pass 如果没有安装g4f&a…
阅读更多...
react的组件的概念和使用

react的组件的概念和使用

文章目录 1. **组件的定义****函数组件****类组件** 2. **组件的生命周期**3. **状态管理****类组件中的状态管理****函数组件中的状态管理** 4. **组件之间的通信****通过 Props 传递数据****上下文&#xff08;Context&#xff09;** 5. **组件的样式**6. **处理表单**7. **错…
阅读更多...
11. Map和Set

11. Map和Set

一、二叉搜索树 1. 概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树&#xff1a; 若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值若它的右子树不为空&#xff0c;则右子树上所有节点的值都大于根…
阅读更多...
【RabbitMQ】消息堆积、推拉模式

【RabbitMQ】消息堆积、推拉模式

消息堆积 原因 消息堆积是指在消息队列中&#xff0c;待处理的消息数量超过了消费者处理能力&#xff0c;导致消息在队列中不断堆积的现象。通常有以下几种原因&#xff1a; 消息生产过快&#xff1a;在高流量或者高负载的情况下&#xff0c;生产者以极高的速率发送消息&…
阅读更多...
【Java】异常处理 —— Throwable 及其应用

【Java】异常处理 —— Throwable 及其应用

通过一张图来展示Throwable类的继承体系&#xff0c;如图2所示。 图2 Throwable异常体系结构图 ● Error类称为错误类&#xff0c;它表示Java运行时产生的系统内部错误或资源耗尽的错误&#xff0c;是比较严重的&#xff0c;仅靠修改程序本身是不能恢复执行的&#xff0c;例如…
阅读更多...
关于JDK的选择问题

关于JDK的选择问题

虽然TongWeb本身支持Open JDK、Oracle JDK、TongJDK、毕昇JDK等&#xff0c;但在商用项目上使用时&#xff0c;需要注意Oracle JDK的商业授权问题。目前部分Oracle JDK版本用于商业是收费的&#xff0c;版本如下&#xff1a; Oracle JDK 8之前版本&#xff0c;全免费。 Oracl…
阅读更多...
node-red-L3-重启指定端口的 node-red

node-red-L3-重启指定端口的 node-red

重启指定端口 目的步骤查找正在运行的Node.js服务的进程ID&#xff08;PID&#xff09;&#xff1a;停止Node.js服务&#xff1a;启动Node.js服务&#xff1a; 目的 重启指定端口的 node-red 步骤 在Linux系统中&#xff0c;如果你想要重启一个正在运行的Node.js服务&#x…
阅读更多...
Linux本地服务器搭建开源监控服务Uptime Kuma与远程监控实战教程

Linux本地服务器搭建开源监控服务Uptime Kuma与远程监控实战教程

文章目录 前言**主要功能**一、前期准备本教程环境为&#xff1a;Centos7&#xff0c;可以跑Docker的系统都可以使用本教程安装。本教程使用Docker部署服务&#xff0c;如何安装Docker详见&#xff1a; 二、Docker部署Uptime Kuma三、实现公网查看网站监控四、使用固定公网地址…
阅读更多...
最新文章

Copyright @ 2022~2023