桶排序算法图文详解

本节您将系统学习桶排序算法，还会看到实现桶排序算法的 C、Java 以及 Python 程序。

桶排序算法的核心思想是：将待排序序列中的元素根据规则分组，每一组采用快排、插入排序等算法完成排序，然后再将所有组进行合并，最终就可以得到一个有序序列。

也就是说，采用桶排序算法对目标序列进行排序，会经历下图所示的三个阶段：

桶排序算法的工作原理

我们以对如下序列进行升序排序为例，详细讲解桶排序算法的工作原理。

针对序列存储的元素的特点，这里采用的分组规则是：将各个元素乘以 10 然后取整，得到的值即为该元素的组号。由此，我们可以得到如下所示的几个分组：

接下来，选择适当的排序算法对各组元素分别进行升序排序，最终可以得到如下的各个组：

最后，通过逐个遍历各个组中的元素，即可得到我们想要的升序序列。

桶排序算法的具体实现

如下为实现桶排序算法的 C 语言程序：

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

#define N 7   // 待排序序列中的元素个数
#define NBUCKET 6  // 桶的数量
#define INTERVAL 10  // 每个桶能存放的元素个数
//建立桶
struct Node {
    float data;
    struct Node *next;
};

void BucketSort(float arr[]);
struct Node *InsertionSort(struct Node *list);
void print(float arr[]);

int main() {
    float array[N] = { 0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51 };
    BucketSort(array);
    print(array);
    return 0;
}

// 桶排序，arr 为待排序序列
void BucketSort(float arr[]) {
    int i, j;
    struct Node **buckets;
    // 创建所有桶
    buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);
    // 设置每个桶为空桶
    for (i = 0; i < NBUCKET; ++i) {
        buckets[i] = NULL;
    }
    // 根据规定，将 arr 中的每个元素分散存储到各个桶中
    for (i = 0; i < N; ++i) {
        struct Node *current;
        int pos = arr[i] * 10;  //根据规则，确定元素所在的桶
        //创建存储该元素的存储块，并连接到指定的桶中
        current = (struct Node *)malloc(sizeof(struct Node));
        current->data = arr[i];
        current->next = buckets[pos];
        buckets[pos] = current;
    }
    // 调用自定义的排序算法，对各个桶进行排序
    for (i = 0; i < NBUCKET; ++i) {
        buckets[i] = InsertionSort(buckets[i]);
    }
    // 合并所有桶内的元素
    for (j = 0, i = 0; i < NBUCKET; ++i) {
        struct Node *node;
        node = buckets[i];
        while (node) {
            arr[j++] = node->data;
            node = node->next;
        }
    }
}

// 自定义的排序算法，用于对各个桶内元素进行排序
struct Node *InsertionSort(struct Node *list) {
    struct Node *k, *nodeList;
    if (list == NULL || list->next == NULL) {
        return list;
    }
    nodeList = list;
    k = list->next;
    nodeList->next = NULL;
    while (k != NULL) {
        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;
}

void print(float ar[]) {
    int i;
    for (i = 0; i < N; ++i) {
        printf("%.2f ", ar[i]);
    }
}

如下为实现桶排序算法的 Java 程序：

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {
    public static void bucketSort(float[] arr) {
        int n = arr.length;
        if (n <= 0)
            return;
        @SuppressWarnings("unchecked")
        ArrayList<Float>[] bucket = new ArrayList[n];
        // 创建空桶
        for (int i = 0; i < n; i++)
            bucket[i] = new ArrayList<Float>();
        // 根据规则将序列中元素分散到桶中
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int) arr[i] * n;
            bucket[bucketIndex].add(arr[i]);
        }
        // 对各个桶内的元素进行排序
        for (int i = 0; i < n; i++) {
            Collections.sort((bucket[i]));
        }
        // 合并所有桶内的元素
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0, size = bucket[i].size(); j < size; j++) {
                arr[index++] = bucket[i].get(j);
            }
        }
    }

    public static void main(String[] args) {
        float[] arr = { (float) 0.42, (float) 0.32, (float) 0.23, (float) 0.52, (float) 0.25, (float) 0.47,
                (float) 0.51 };
        bucketSort(arr);

        for (float i : arr)
            System.out.print(i + " ");
    }
}

如下为实现桶排序算法的 Python 程序：

格式化复制

#桶排序算法，array 为待排序序列
def bucketSort(array):
    bucket = []
    # 创建空桶
    for i in range(len(array)):
        bucket.append([])
    # 根据规则将所有元素分散到各个桶中
    for j in array:
        index_b = int(10 * j)
        bucket[index_b].append(j)
    # 分别对各个桶进行排序
    for i in range(len(array)):
        bucket[i] = sorted(bucket[i])
    # 合并所有桶内的元素
    k = 0
    for i in range(len(array)):
        for j in range(len(bucket[i])):
            array[k] = bucket[i][j]
            k += 1
    return array

array = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]
print(bucketSort(array))

以上各个程序的输出结果为：

0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52