桶排序算法（桶排序算法图解）

本篇文章给大家谈谈桶排序算法，以及桶排序算法图解对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、什么是桶排序，它和希尔排序的区别是什么？
• 2、桶排序与哈希桶排序
• 3、桶排序算法c语言

什么是桶排序，它和希尔排序的区别是什么？

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的困蠢桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排雀慎序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

区别就汪岁陪是桶排序要求数据的长度必须完全一样，而希尔排序是非稳定排序算法。

[img]

桶排序与哈希桶排序

桶排序 (箱排序)的原理是将待排序序列分到有限数量的桶里面，然后对每个桶再分别排序（可以使用其它的排序算法或者是递归使用桶排序算法），最后将各个桶中的数据有序的合并起来成为一个整体有序的序列。

排序过程：

1.假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶

2.将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序

3.将各个桶中的数据有序的合并起来

设有数组 array = [29, 25, 3, 49, 9, 37, 21, 43]，那么数组中最大数为 49，先设置 5 个桶，那么每个桶可存放数的范围为：09、1019、2029、3039、40~49，然后分别将这些数放人自己所属的桶，如下图：

1.时间复杂度：O(m+n)

2.空间复杂度：O(m+n)

适用于序列比较均匀的情况，否则会很耗空间。

或者特殊的场景，袭伍例如需要对一个公司的员工的年龄进行排序，年龄的范围为1-120，此时就可以开辟120个桶进行统计排序。

另，桶排序的瓶颈主要是桶数量的选择。

另此算法为稳定的排序算法。

排序算法主要是用分治法，用哈希函数对序列进行划分，最后使用其它的排序算法或者递归使用哈希排序进行排序从而得到一个整体有序的序列。下面先介绍几个自定义的概念：

1.哈希桶排序：因为本算法是使用了哈希函数把序列划分到对应的桶里面，所以本排序算法取名为哈希桶排序。

2.哈希桶因子（hashFactor）：hashFactor = （max - min） / length

计算公式如上式，当结果小于等于0的时候再做特殊处理，据此因子进行桶的划分。

设有数组 array = [10011, 10001, 16, 14, 12, 10000, 10, 10002, 10003, 1]，那么数组中最大值max = 10011，最小值min = 1，哈希桶因子hashFactor = （10011 - 1） / 10 = 1001。对数组进行划分，10011 / 1001 = 10，所以10011放在keywei10的桶里面；10001 / 1001 = 9， 所以10001放在key为9的桶里面，以此类态纯推，最后得帆禅咐到的桶的情况为：{0=[1, 10, 12, 14, 16], 9=[10000, 10001, 10002, 10003], 10=[10011]}。再分别对每个桶进行排序即可。

1.时间复杂度：O(m+n)

2.空间复杂度：O(m+n)

此算法与桶排序对比，主要是通过哈希建桶的方式减少了空间的消耗，对序列进行了一个归约，时间上跟桶排序相当。

使用与序列的最小最大值相差比较大同时又出现在某一个取值区间的集聚的情况。

另此算法为稳定的排序算法。

桶排序算法c语言

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《数据结构与型誉算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过搏睁程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是桶排序算法：

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在基租岁于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

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

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

1. 什么时候最快

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

2. 什么时候最慢

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

3. 示意图

元素分布在桶中：

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

代码实现 JavaScript 实例 function bucketSort ( arr , bucketSize ) {

    if ( arr. length === 0 ) {

      return arr ;

    }

    var i ;

    var minValue = arr [ 0 ] ;

    var maxValue = arr [ 0 ] ;

    for ( i = 1 ; i nodes_space) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__); goto exit_2; } return space_mgr; exit_2: free(space_mgr); exit_1: return NULL; } BucketManager* init_buckets(int bucket_nums) { BucketManager* bucket_mgr = (BucketManager*)malloc(sizeof(BucketManager)); if (!bucket_mgr) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__); goto exit_1; } bucket_mgr-nums = bucket_nums; bucket_mgr-buckets = (Node**)calloc(bucket_mgr-nums, sizeof(Node*)); if (!bucket_mgr-buckets) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__); goto exit_2; } return bucket_mgr; exit_2: free(bucket_mgr); exit_1: return NULL; } Node* get_bucket_space(BucketSpaceManager* space_mgr) { if (space_mgr) { return space_mgr-nodes_space[space_mgr-index++]; } else { return NULL; } } void release_bucket_space(BucketSpaceManager* space_mgr) { if (space_mgr) { if (space_mgr-nodes_space) { free(space_mgr-nodes_space); } free(space_mgr); } } void release_buckets(BucketManager* buckets_mgr) { if (buckets_mgr) { if (buckets_mgr-buckets) { free(buckets_mgr-buckets); } free(buckets_mgr); } } int find_max_min(int* arr, int size, int* p_max, int* p_min) { if (size *p_max) { *p_max = arr[i]; } if (arr[i] *p_min) { *p_min = arr[i]; } } return 0; } int insert_bucket(BucketManager* bucket_mgr, int index, Node* new_node) { Node* cur, *pre; if (!bucket_mgr-buckets[index]) { bucket_mgr-buckets[index] = new_node; } else { /** 桶内使用插入排序 */ cur = bucket_mgr-buckets[index]; pre = cur; while (cur-list_next new_node-elem cur-elem) { pre = cur; cur = cur-list_next; } if (new_node-elem elem) { if (pre == cur) { new_node-list_next = cur; bucket_mgr-buckets[index] = new_node; } else { new_node-list_next = cur; pre-list_next = new_node; } } else { cur-list_next = new_node; } } return 0; } void bucket_sort(int* arr, int size) { int max, min; int ret = find_max_min(arr, size, max, min); if (ret 0) { return; } BucketSpaceManager* space_mgr = init_bucket_space(size); if (!space_mgr) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__); goto exit_1; } int bucket_nums = (max - min) / BUCKET_SIZE + 1; BucketManager* bucket_mgr = init_buckets(bucket_nums); if (!bucket_mgr) { goto exit_2; } int i; for (i = 0; i size; ++i) { int index = (arr[i] - min) / BUCKET_SIZE; Node* new_node = get_bucket_space(space_mgr); if (!new_node) { goto exit_3; } new_node-elem = arr[i]; new_node-list_next = NULL; insert_bucket(bucket_mgr, index, new_node); } for (i = 0; i bucket_mgr-nums; ++i) { Node* node = bucket_mgr-buckets[i]; while(node) { printf("%d ", node-elem); node = node-list_next; } } printf(" "); exit_3: release_buckets(bucket_mgr); exit_2: release_bucket_space(space_mgr); exit_1: return; }

下载测试代码

以上为桶排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括：

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

n：数据规模

k："桶"的个数

In-place：占用常数内存，不占用额外内存

Out-place：占用额外内存

稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

关于桶排序算法和桶排序算法图解的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。