全部频道

桶式排序

作者：原创时间：2022-05-25
文档
点击下载本文 文档为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格式
显示全文
计数排序算法c++实现 堆排序法排序怎么排 关于兰花的诗句古诗 快速排序c语言 两句关于动物的诗句 踏青的诗词名句 含有燕子的诗句 简述归并排序算法的基本思路 希尔排序怎么排 直接选择排序 基数排序流程图 python冒泡排序算法 桶排序c语言 计数排序菜鸟教程 堆排序算法规则 描写兰花的诗句古诗 快速排序算法java 带有动物的古诗 关于踏青的唯美诗句 关于描写燕子的诗句 关于放风筝的古诗 冒泡排序python 基数排序怎么排 选择排序法 希尔排序 归并排序python 描写燕子的古诗绝句 踏青诗句最出名诗句 描写夏天的诗句简单 关于写小动物的诗 java快速排序 关于兰花的诗句两句 堆排序怎么排 描写元宵节的唯美诗词 如何按照计数进行排序 桶排序 写与风筝有关的诗 冒泡排序python代码 基数排序 选择排序