桶排序分析

桶排序概述

桶排序的流程：

• 创建几个存储桶，将元素分别划分到存储桶中
• 分别对存储桶中的元素进行排序
• 将存储桶中的元素进行收集

适用场景： 输入均匀地分布在一个范围内。

桶排序代码

// Bucket sort in C++

#include <iomanip>
#include <iostream>
using namespace std;

#define NARRAY 7   // Array size
#define NBUCKET 6  // Number of buckets
#define INTERVAL 10  // Each bucket capacity

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

void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node *list);
int getBucketIndex(int value);

// Sorting function
void BucketSort(int arr[]) {
    int i, j;
    struct Node **buckets;

    // Create buckets and allocate memory size
    buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);

    // Initialize empty buckets
    for (i = 0; i < NBUCKET; ++i) {
        buckets[i] = NULL;
    }

    // Fill the buckets with respective elements
    for (i = 0; i < NARRAY; ++i) {
        struct Node *current;
        int pos = getBucketIndex(arr[i]);
        current = (struct Node *)malloc(sizeof(struct Node));
        current->data = arr[i];
        current->next = buckets[pos];
        buckets[pos] = current;
    }

    // Print the buckets along with their elements
    for (i = 0; i < NBUCKET; i++) {
        cout << "Bucket[" << i << "] : ";
        printBuckets(buckets[i]);
        cout << endl;
    }

    // Sort the elements of each bucket
    for (i = 0; i < NBUCKET; ++i) {
        buckets[i] = InsertionSort(buckets[i]);
    }

    cout << "-------------" << endl;
    cout << "Bucktets after sorted" << endl;
    for (i = 0; i < NBUCKET; i++) {
        cout << "Bucket[" << i << "] : ";
        printBuckets(buckets[i]);
        cout << endl;
    }

    // Put sorted elements on arr
    for (j = 0, i = 0; i < NBUCKET; ++i) {
        struct Node *node;
        node = buckets[i];
        while (node) {
        arr[j++] = node->data;
        node = node->next;
        }
    }

    for (i = 0; i < NBUCKET; ++i) {
        struct Node *node;
        node = buckets[i];
        while (node) {
        struct Node *tmp;
        tmp = node;
        node = node->next;
        free(tmp);
        }
    }
    free(buckets);
    return;
}

// Function to sort the elements of each bucket
struct Node *InsertionSort(struct Node *list) {
    struct Node *k, *nodeList;
    if (list == 0 || list->next == 0) {
        return list;
    }

    nodeList = list;
    k = list->next;
    nodeList->next = 0;
    while (k != 0) {
        struct Node *ptr;
        if (nodeList->data > k->data) {
        struct Node *tmp;
        tmp = k;
        k = k->next;
        tmp->next = nodeList;
        nodeList = tmp;
        continue;
        }

        for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
        if (ptr->next->data > k->data)
            break;
        }

        if (ptr->next != 0) {
        struct Node *tmp;
        tmp = k;
        k = k->next;
        tmp->next = ptr->next;
        ptr->next = tmp;
        continue;
        } else {
        ptr->next = k;
        k = k->next;
        ptr->next->next = 0;
        continue;
        }
    }
    return nodeList;
}

int getBucketIndex(int value) {
    return value / INTERVAL;
}

// Print buckets
void print(int ar[]) {
    int i;
    for (i = 0; i < NARRAY; ++i) {
        cout << setw(3) << ar[i];
    }
    cout << endl;
}

void printBuckets(struct Node *list) {
    struct Node *cur = list;
    while (cur) {
        cout << setw(3) << cur->data;
        cur = cur->next;
    }
}

// Driver code
int main(void) {
    int array[NARRAY] = {42, 32, 33, 52, 37, 47, 51};

    cout << "Initial array: " << endl;
    print(array);
    cout << "-------------" << endl;

    BucketSort(array);
    cout << "-------------" << endl;
    cout << "Sorted array: " << endl;
    print(array);
}


执行结果：

```shell
Initial array: 
 42 32 33 52 37 47 51
-------------
Bucket[0] : 
Bucket[1] : 
Bucket[2] : 
Bucket[3] :  37 33 32
Bucket[4] :  47 42
Bucket[5] :  51 52
-------------
Bucktets after sorted
Bucket[0] : 
Bucket[1] : 
Bucket[2] : 
Bucket[3] :  32 33 37
Bucket[4] :  42 47
Bucket[5] :  51 52
-------------
Sorted array: 
 32 33 37 42 47 51 52

https://github.com/apachecn/programiz-zh/blob/master/docs/dsal/60.md