Lwaxx的博客

十大排序算法（八） - 桶排序算法

发表于 分类于 ， 阅读次数： Valine：

桶排序（Bucket Sort）是一种分布式排序算法，它根据元素的值将它们分散到不同的桶中，并对每个桶中的元素进行排序。最后，将所有非空桶的元素按照顺序合并成排序后的数组。本文将详细介绍桶排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。

桶排序的基本思想

桶排序的核心思想是将待排序的元素根据其值分配到不同的桶中，然后对每个桶中的元素进行独立排序，最后将所有桶合并为一个有序序列。

具体步骤如下：

  1. 桶的设置： 根据待排序元素的特性，确定需要设置多少个桶以及每个桶的范围。
  2. 元素分配： 将待排序元素根据其值分配到相应的桶中。
  3. 每个桶排序： 对每个非空桶中的元素进行独立排序，可以选择不同的排序算法。
  4. 桶的合并： 将所有非空桶中的元素合并成排序后的数组。

桶排序的示例

让我们通过一个示例来理解桶排序的工作原理。假设我们有一个浮点数数组 [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]，我们希望按升序排序它。

  1. 设置桶： 假设我们设置3个桶，分别对应范围[0, 0.3333), [0.3333, 0.6666), [0.6666, 1.0)。
  2. 元素分配： 将元素分配到对应的桶中。
    • 桶1: [0.1234]
    • 桶2: [0.565, 0.656]
    • 桶3: [0.897, 0.665, 0.3434]
  3. 每个桶排序： 对每个桶中的元素进行排序。
    • 桶1: [0.1234]
    • 桶2: [0.565, 0.656]
    • 桶3: [0.3434, 0.665, 0.897]
  4. 桶的合并： 将所有非空桶中的元素合并成排序后的数组。
    • 排序后的数组: [0.1234, 0.3434, 0.565, 0.656, 0.665, 0.897]

桶排序的时间复杂度

桶排序的时间复杂度取决于桶的数量和每个桶中元素的排序算法。假设n是待排序元素的数量，k是桶的数量，t是桶内排序的平均时间复杂度。

  1. 桶分配时间： O(n)
  2. 每个桶内排序时间： O(k * t)
  3. 桶的合并时间： O(n)
    综合起来，桶排序的时间复杂度为O(n + k * t)，其中k和t取决于具体实现和数据分布。

桶排序是一种稳定的排序算法，适用于分布均匀的数据。它在对浮点数等分布广泛的数据排序时表现出色。

示例代码

以下是桶排序的示例代码，分别使用Python、Go、Java和C语言编写。

Python 桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def bucket_sort(arr):
    # 确定桶的数量
    num_buckets = len(arr)
    buckets = [[] for _ in range(num_buckets)]

    # 将元素分配到对应的桶中
    for num in arr:
        bucket_index = int(num * num_buckets)
        buckets[bucket_index].append(num)

    # 对每个非空桶进行排序
    for i in range(num_buckets):
        buckets[i].sort()

    # 合并桶
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr

arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
sorted_arr = bucket_sort(arr)
print("排序后的数组:", sorted_arr)

Go 桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package main

import (
	"fmt"
	"sort"
)

func bucketSort(arr []float64) []float64 {
	numBuckets := len(arr)
	buckets := make([][]float64, numBuckets)

	// 将元素分配到对应的桶中
	for _, num := range arr {
		bucketIndex := int(num * float64(numBuckets))
		buckets[bucketIndex] = append(buckets[bucketIndex], num)
	}

	// 对每个非空桶进行排序
	for i := 0; i < numBuckets; i++ {
		sort.Float64s(buckets[i])
	}

	// 合并桶
	sortedArr := make([]float64, 0, len(arr))
	for i := 0; i < numBuckets; i++ {
		sortedArr = append(sortedArr, buckets[i]...)
	}

	return sortedArr
}

func main() {
	arr := []float64{0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}
	sortedArr := bucketSort(arr)
	fmt.Println("排序后的数组:", sortedArr)
}

Java 桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BucketSort {
    public static double[] bucketSort(double[] arr) {
        int numBuckets = arr.length;
        List<Double>[] buckets = new ArrayList[numBuckets];

        // 初始化桶
        for (int i = 0; i < numBuckets; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 将元素分配到对应的桶中
        for (double num : arr) {
            int bucketIndex = (int) (num * numBuckets);
            buckets[bucketIndex].add(num);
        }

        // 对每个非空桶进行排序
        for (int i = 0; i < numBuckets; i++) {
            buckets[i].sort(Double::compare);
        }

        // 合并桶
        double[] sortedArr = new double[arr.length];
        int index = 0;
        for (int i = 0; i < numBuckets; i++) {
            for (double num : buckets[i]) {
                sortedArr[index++] = num;
            }
        }

        return sortedArr;
    }

    public static void main(String[] args) {
        double[] arr = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
        double[] sortedArr = bucketSort(arr);
        System.out.print("排序后的数组: ");
        System.out.println(Arrays.toString(sortedArr));
    }
}

C 语言 桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    double data;
    struct Node *next;
} Node;

typedef struct Bucket {
    Node *head;
} Bucket;

double* bucketSort(double arr[], int n) {
    // 确定桶的数量
    int numBuckets = n;
    Bucket *buckets = (Bucket *)malloc(numBuckets * sizeof(Bucket));

    // 初始化桶
    for (int i = 0; i < numBuckets; i++) {
        buckets[i].head = NULL;
    }

    // 将元素分配到对应的桶中
    for (int i = 0; i < n; i++) {
        int bucketIndex = (int)(arr[i] * numBuckets);
        Node *node = (Node *)malloc(sizeof(Node));
        node->data = arr[i];
        node->next = buckets[bucketIndex].head;
        buckets[bucketIndex].head = node;
    }

    // 合并桶并获取排序后的数组
    double *sortedArr = (double *)malloc(n * sizeof(double));
    int index = 0;
    for (int i = 0; i < numBuckets; i++) {
        Node *current = buckets[i].head;
        while (current != NULL) {
            sortedArr[index++] = current->data;
            Node *temp = current;
            current = current->next;
            free(temp);
        }
    }

    free(buckets);
    return sortedArr;
}

int main() {
    double arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
    int n = sizeof(arr) / sizeof(arr[0]);
    double *sortedArr = bucketSort(arr, n);
    printf("排序后的数组: ");
    for (int i = 0; i < n; i++) {
        printf("%.4f ", sortedArr[i]);
    }
    free(sortedArr);
    return 0;
}

以上示例代码展示了不同编程语言中的桶排序算法实现。这些示例帮助你理解桶排序的工作原理，并提供了可供参考和使用的代码示例。桶排序是一种适用于分布广泛数据的高效排序算法。