全部频道

c语言桶式排序

作者：原创时间：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语言选择排序从小到大 冒泡排序法的基本思路 桶排序java 堆排序是稳定的排序算法 快速排序算法原理 归并排序算法c语言 数据结构希尔排序流程图 什么是选择排序法 降序排序冒泡排序优化 堆是一种什么排序方法 实现归并排序利用的算法 希尔排序c 排序算法的一般选择规则 冒泡排序流程图 堆排序计算 归并排序算法流程图解 冒泡法排序c语言编写 选择排序发 希尔排序代码实现 归并排序算法详解 快速排序的详细过程 堆排序代码数据结构 桶排序是什么意思 冒泡排序代码 基数排序c 简单选择排序流程图 希尔排序怎么排序 归并排序的具体过程 快速排序思想 堆排序算法思想 桶排序算法c 冒泡排序法流程图 基数排序算法的基本思想 描述选择排序算法 希尔排序图解流程图 归并排序算法时间复杂度