桶排序

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

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

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

1.什么时候最快

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

2.什么时候最慢

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

3.示意图

元素分布在桶中：

bucket_sort_1.svg_.png

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

bucket_sort_2.svg_.png

4.代码

#include <stdio.h>
#include <stdlib.h>

#define BUCKET_NUM 10

struct ListNode {
    struct ListNode* next;
    int data;
};

struct ListNode*
insert(struct ListNode *head, int value)
{
    struct ListNode dummyNode;
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *pre, *curr;

    newNode->data = value;
    dummyNode.next = head;
    pre = &dummyNode;
    curr = head;

    while (curr != NULL && curr->data <= value) {
        pre = curr;
        curr = curr->next;
    }
    newNode->next = curr;
    pre->next = newNode;
    return dummyNode.next;
}

struct ListNode*
merge(struct ListNode *head1, struct ListNode *head2)
{
    struct ListNode dummyNode;
    struct ListNode *dummy = &dummyNode;

    while (head1 != NULL && head2 != NULL) {
        if (head1->data <= head2->data) {
            dummy->next = head1;
            head1 = head1->next;
        } else {
            dummy->next = head2;
            head2 = head2->next;
        }
        dummy = dummy->next;
    }

    if (head1 != NULL) dummy->next = head1;
    if (head2 != NULL) dummy->next = head2;
    return dummyNode.next;
}

void
bucket_sort(int n, int arr[])
{
    struct ListNode* buckets[BUCKET_NUM] = {0};

    int i;
    for (i = 0; i < n; ++i) {
        int index = arr[i] / BUCKET_NUM;
        struct ListNode *head = buckets[index];
        buckets[index] = insert(head, arr[i]);
    }

    struct ListNode *head = buckets[0];
    for (i = 1; i < BUCKET_NUM; ++i) {
        head = merge(head, buckets[i]);
    }

    for (i = 0; i < n; ++i) {
        arr[i] = head->data;
        head = head->next;
    }
}

int
main()
{
    int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
    int len = (int) sizeof(arr) / sizeof(*arr);

    bucket_sort(len, arr);

    int i;
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

部分内容转载于菜鸟教程

2021.01.29 16:47 深圳