全部频道

桶排序算法

作者：原创时间：2022-05-22
文档
点击下载本文 文档为doc格式

排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是桶排序算法：

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

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 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 < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }

    //桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    //利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                      
        }
    }

    return arr;
}

Java

实例

public class BucketSort implements IArraySort {

    private static final InsertSort insertSort = new InsertSort();

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

}

PHP

实例

function bucketSort($arr, $bucketSize = 5)
{
    if (count($arr) === 0) {
      return $arr;
    }

    $minValue = $arr[0];
    $maxValue = $arr[0];
    for ($i = 1; $i < count($arr); $i++) {
      if ($arr[$i] < $minValue) {
          $minValue = $arr[$i];
      } else if ($arr[$i] > $maxValue) {
          $maxValue = $arr[$i];
      }
    }

    $bucketCount = floor(($maxValue - $minValue) / $bucketSize) + 1;
    $buckets = array();
    for ($i = 0; $i < $bucketCount; $i++) {
        $buckets[$i] = [];
    }

    for ($i = 0; $i < count($arr); $i++) {
        $buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];
    }

    $arr = array();
    for ($i = 0; $i < count($buckets); $i++) {
        $bucketTmp = $buckets[$i];
        sort($bucketTmp);
        for ($j = 0; $j < count($bucketTmp); $j++) {
            $arr[] = $bucketTmp[$j];
        }
    }

    return $arr;
}

C++

实例

#include
#include
#include
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;
        }
}

参考地址：

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/9.bucketSort.md

https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F

以下是热心网友对桶排序算法的补充，仅供参考：

热心网友提供的补充1：

# coding=utf-8
# author: [email protected]
# datetime:2020/7/28 18:37

"""
程序说明：
    桶排序
    1）在额外空间充足的情况下，尽量增大桶的数量
    2）使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
      个人理解，如果都是整数还可以用计数排序来计数统计然后排序，但是如果是一个连续空间内的排序，即统计的是一个浮点类型的数组成
      的数组，那么，就无法开辟一个对应的空间使其一一对应的存储。此时，我们需要新建一个带有存储范围的空间，来存储一定范围内的元素
    空间复杂度：O(n)
    时间复杂度: O(n)
    稳定
"""


def bucket_sort_simplify(arr, max_num):
    """
    简化版
    """
    buf = {i: [] for i in range(int(max_num)+1)}  # 不能使用[[]]*(max+1)，这样新建的空间中各个[]是共享内存的
    arr_len = len(arr)
    for i in range(arr_len):
        num = arr[i]
        buf[int(num)].append(num)  # 将相应范围内的数据加入到[]中
    arr = []
    for i in range(len(buf)):
        if buf[i]:
            arr.extend(sorted(buf[i]))  # 这里还需要对一个范围内的数据进行排序，然后再进行输出
    return arr


if __name__ == "__main__":
    lis = [3.1, 4.2, 3.3, 3.5, 2.2, 2.7, 2.9, 2.1, 1.55, 4.456, 6.12, 5.2, 5.33, 6.0, 2.12]
    print(bucket_sort_simplify(lis, max(lis)))

热心网友提供的补充2：

又没把C#的写进来，我来写掉吧，代码如下：

static void BucketSort(List list, int bucketCount, int maxBucketCount)
{
    List> buckets = new List>(bucketCount);//二维列表
    for (int i = 0; i < bucketCount; i++)
    {
        buckets.Add(new List());
    }
    for (int i = 0; i < list.Count; i++)
    {
        // int j = Mathf.Min(list[i] / (maxBucketCount / bucketCount), bucketCount - 1);//j表示改放的哪个桶,不能大于n-1
        int j = Math.Min(list[i] / (maxBucketCount / bucketCount), bucketCount - 1);//j表示改放的哪个桶,不能大于n-1
        buckets[j].Add(list[i]);//放入对应桶
        for (int x = buckets[j].Count - 1; x > 0; x--)//放一个排序一次，两两对比就可以
        {
            if (buckets[j][x] < buckets[j][x - 1])//升序
            {
                int tmp = buckets[j][x];//交换
                buckets[j][x] = buckets[j][x - 1];
                buckets[j][x - 1] = tmp;
            }
            else
            {
                break;//如果不发生交换直接退出，因为前面的之前就排序好了
            }
        }
    }
    list.Clear();//输出
    for (int i = 0; i < buckets.Count; i++)
    {
        list.AddRange(buckets[i]);
    }
}

热心网友提供的补充3：

C 语言实现桶排序，桶内采用插入排序:

#include 
#include 
#include 


#define BUCKET_SIZE (5) /**< 假定均匀分布的情况下平均每个桶放几个元素*/


typedef struct Node
{
    int elem;
    struct Node* list_next;
} Node;

typedef struct BucketManager
{
    int nums;
    Node** buckets;  
} BucketManager;

typedef struct BucketSpaceManager
{
    int index;
    Node* nodes_space;
} BucketSpaceManager;


BucketSpaceManager* init_bucket_space(int size)
{
    BucketSpaceManager* space_mgr = (BucketSpaceManager*)malloc(sizeof(BucketSpaceManager));
    if (!space_mgr)
    {
        printf("out of memory,File:%s, Func:%s, Line:%d
", __FILE__, __func__, __LINE__);
        goto exit_1;
    }
    space_mgr->index = 0;
    space_mgr->nodes_space = (Node*)malloc(size * sizeof(Node));
    if (!space_mgr->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 <= 0)
    {
        return -1;
    }
    *p_max = arr[0];
    *p_min = arr[0];
    int i;
    for (i = 1; i < size; ++i)
    {
        if (arr[i] > *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 <= cur->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 个相等键值的顺序和排序之前它们的顺序相同

文档
点击下载本文 文档为doc格式
显示全文
基数排序算法 排序算法 助人为乐的谚语和名言 春天的谚语 春分的谚语 团结的谚语 帮助人的谚语 谚语的意思 关于关爱的谚语 学习的名言 关于学习的名人名言 关于爱国的名言 陶渊明的名句 激励自己的名言 关于保护环境的名言 叶圣陶的名言 关于家的名言 关于交友的名言警句 有关友谊的名言 关于乐观的名言 计数排序算法 堆排序算法 快速排序算法 归并排序算法 希尔排序算法 插入排序算法 选择排序算法 冒泡排序算法 清明的谚语 关于清明的谚语 清明节的谚语 珍惜时间的名言 愁的诗句 含雁的诗句 想念的诗句 牡丹花的诗句 带马字的诗句 关于思念的诗句 描写春天花朵的诗句 js中toString方法3个作用