【4】桶排序算法

桶排序是一种线性排序算法，其基本思想是将数据分到有限数量的桶子里。每个桶子再分别排序（可以使用别的排序算法或者以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。

桶排序的过程可以描述为：

1. 设置一个定量的数组当作空桶子。

2. 遍历输入数据，并且把数据一个一个放到对应的桶子里去。

3. 对每个不是空的桶子进行排序。

4. 从不是空的桶子里把排好序的数据拼接起来。

下面是一个用 C++ 编写的桶排序算法的代码实现，演示了对一组随机生成的数据进行排序：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void bucketSort(vector<double>& arr) {
    // 获取最大值和最小值
    double max_val = *max_element(arr.begin(), arr.end());
    double min_val = *min_element(arr.begin(), arr.end());

    // 计算桶的数量和桶的大小
    int num_buckets = arr.size();
    double bucket_size = (max_val - min_val) / num_buckets;

    // 创建桶并把数据分配到桶里
    vector<vector<double>> buckets(num_buckets);
    for (double val : arr) {
        int bucket_idx = (val - min_val) / bucket_size;
        buckets[bucket_idx].push_back(val);
    }

    // 对每个桶里的数据进行排序并把它们合并成一个有序序列
    arr.clear();
    for (vector<double>& bucket : buckets) {
        sort(bucket.begin(), bucket.end());
        arr.insert(arr.end(), bucket.begin(), bucket.end());
    }
}

int main() {
    // 生成一组随机数据
    vector<double> arr = {0.8, 0.1, 0.5, 0.7, 0.3, 0.2, 0.6, 0.4};

    // 对数据进行桶排序
    bucketSort(arr);

    // 输出排序后的结果
    for (double val : arr) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

上面的代码中，我们首先使用 max_element 和 min_element 函数来获取输入数据中的最大值和最小值。然后我们根据输入数据的数量计算出需要创建的桶的数量，以及每个桶的大小。接着我们创建一个二维数组 buckets 作为桶，把输入数据分配到不同的桶里。最后我们对每个桶里的数据进行排序，然后把它们合并成一个有序序列。

下面是一个不依赖 STL 的 C++ 桶排序算法的代码实现，演示了对一组随机生成的数据进行排序：

#include <iostream>

using namespace std;

const int MAX_VAL = 100; // 数据范围
const int BUCKET_SIZE = 5; // 每个桶的大小

void bucketSort(double arr[], int n) {
    // 获取最大值和最小值
    double max_val = arr[0], min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
        if (arr[i] < min_val) {
            min_val = arr[i];
        }
    }

    // 计算桶的数量
    int num_buckets = (max_val - min_val) / BUCKET_SIZE + 1;

    // 创建桶并把数据分配到桶里
    double buckets[num_buckets][BUCKET_SIZE] = {0};
    int bucket_counts[num_buckets] = {0};
    for (int i = 0; i < n; i++) {
        int bucket_idx = (arr[i] - min_val) / BUCKET_SIZE;
        buckets[bucket_idx][bucket_counts[bucket_idx]++] = arr[i];
    }

    // 对每个桶里的数据进行插入排序并把它们合并成一个有序序列
    int idx = 0;
    for (int i = 0; i < num_buckets; i++) {
        if (bucket_counts[i] == 0) {
            continue;
        }

        // 插入排序
        for (int j = 1; j < bucket_counts[i]; j++) {
            double key = buckets[i][j];
            int k = j - 1;
            while (k >= 0 && buckets[i][k] > key) {
                buckets[i][k + 1] = buckets[i][k];
                k--;
            }
            buckets[i][k + 1] = key;
        }

        // 把桶里的数据合并到数组中
        for (int j = 0; j < bucket_counts[i]; j++) {
            arr[idx++] = buckets[i][j];
        }
    }
}

int main() {
    // 生成一组随机数据
    double arr[] = {0.8, 0.1, 0.5, 0.7, 0.3, 0.2, 0.6, 0.4};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 对数据进行桶排序
    bucketSort(arr, n);

    // 输出排序后的结果
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

上面的代码中，我们首先遍历输入数据，获取最大值和最小值。然后我们根据数据范围和每个桶的大小计算出需要创建的桶的数量。接着我们创建一个二维数组 buckets 作为桶，以及一个一维数组 bucket_counts 用于记录每个桶里的元素数量。我们把输入数据分配到不同的桶里，并对每个桶里的数据进行插入排序，最后把所有桶里的数据按照顺序合并成一个有序序列。

在上面的代码中，我们使用一个二维数组 buckets 来模拟桶，其中第一维表示桶的编号，第二维表示桶里的元素。我们还使用一个一维数组 bucket_counts 记录每个桶里的元素数量。在分配数据到桶里时，我们根据每个元素的值把它放入对应的桶中，并记录该桶里元素数量的增加。在对每个桶里的元素进行插入排序时，我们使用标准的插入排序算法。在最后合并桶里的元素时，我们按照桶的编号从小到大依次把桶里的元素按照顺序放入输出数组中。

下面是一个使用上面的代码实现桶排序算法的演示。我们随机生成一组长度为 10 的 double 类型数组，并对它们进行桶排序：

Before sorting: 57.86 1.47 10.56 68.76 83.98 87.44 89.43 31.54 52.25 97.63
After sorting: 1.47 10.56 31.54 52.25 57.86 68.76 83.98 87.44 89.43 97.63

可以看到，桶排序算法成功地将这组随机数据从小到大排序了。

简单的桶排序例子：

#include <iostream>
using namespace std;

void bucket_sort(double A[], int n) {
    // 计算输入数组中的最小值和最大值
    double min_val = A[0], max_val = A[0]; // 最小值和最大值
    for (int i = 1; i < n; i++) {
        if (A[i] < min_val) min_val = A[i];
        if (A[i] > max_val) max_val = A[i];
    }
    
    // 计算每个桶的大小，并创建桶数组
    int bucket_size = 10; // 桶的数量
    double range = max_val - min_val; // 输入数组的范围
    double bucket_range = range / bucket_size; // 每个桶的范围
    int* bucket_counts = new int[bucket_size]; // 每个桶中元素的数量
    double** buckets = new double*[bucket_size]; // 每个桶中元素的数组
    for (int i = 0; i < bucket_size; i++) {
        bucket_counts[i] = 0; // 初始化每个桶中元素的数量为0
        buckets[i] = new double[n]; // 初始化每个桶中元素的数组为空
    }
    
    // 将元素插入到相应的桶中
    for (int i = 0; i < n; i++) {
        // 计算元素属于哪个桶
        int bucket_idx = (int)((A[i] - min_val) / bucket_range); // 元素所属的桶的下标
        if (bucket_idx == bucket_size) bucket_idx--; // 处理元素位于最大值时的情况
        // 将元素插入到相应的桶中
        buckets[bucket_idx][bucket_counts[bucket_idx]++] = A[i];
    }
    
    // 对每个桶中的元素进行插入排序
    for (int i = 0; i < bucket_size; i++) {
        for (int j = 1; j < bucket_counts[i]; j++) {
            // 将第j个元素插入到前面已经排好序的子数组中
            double key = buckets[i][j];
            int k = j - 1;
            while (k >= 0 && buckets[i][k] > key) {
                buckets[i][k + 1] = buckets[i][k];
                k--;
            }
            buckets[i][k + 1] = key;
        }
    }
    
    // 将各个桶中的元素合并到输入数组中
    int idx = 0;
    for (int i = 0; i < bucket_size; i++) {
        for (int j = 0; j < bucket_counts[i]; j++) {
            A[idx++] = buckets[i][j];
        }
    }
    
    // 释放桶数组的内存
    for (int i = 0; i < bucket_size; i++) {
        delete[] buckets[i];
    }
    delete[] buckets;
    // 释放桶元素数量数组的内存
    delete[] bucket_counts;
}

int main() {
    double A[] = {57.86, 1.47, 10.56, 68.76, 83.98, 87.44, 89.43, 31.54, 52.25, 97.63};
    int n = sizeof(A) / sizeof(A[0]);

    cout << "Before sorting: ";
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;

    bucket_sort(A, n);

    cout << "After sorting: ";
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;

    return 0;
}

在桶排序算法中，桶的数量通常是一个常数，可以根据经验或实验来确定。一般来说，桶的数量越大，排序的效率越高，但同时需要更多的空间来存储桶数组。在这个例子中，桶的数量被设置为10，这是一种比较常见的做法，因为它可以使得每个桶的大小比较合适，同时又不需要太大的空间来存储桶数组。

 int bucket_size = 10; // 为什么 定义桶的数量  是10

在桶排序算法中，桶的数量通常是一个常数，可以根据经验或实验来确定。一般来说，桶的数量越大，排序的效率越高，但同时需要更多的空间来存储桶数组。在这个例子中，桶的数量被设置为10，这是一种比较常见的做法，因为它可以使得每个桶的大小比较合适，同时又不需要太大的空间来存储桶数组。

为什么要用  (int)((A[i] - min_val) / bucket_range) 计算下标？

这个计算是为了决定把当前元素A[i]放在哪个桶里。桶的编号是根据元素的值来决定的，而不是根据元素的下标。

首先，我们需要知道最小值min_val和最大值max_val。然后，我们计算出桶的范围bucket_range=(max_val-min_val)/bucket_size，也就是每个桶所包含的元素值的范围。例如，如果最小值是10，最大值是90，桶的数量是10，那么每个桶的范围就是8，也就是第一个桶包含的元素值是10到17，第二个桶包含的元素值是18到25，以此类推。

接着，我们需要计算出当前元素A[i]应该放在哪个桶里。这个计算是通过先将元素值减去最小值，然后再除以桶的范围来得到的。例如，如果当前元素A[i]的值是23，最小值是10，桶的范围是8，那么 (A[i] - min_val) / bucket_range = (23 - 10) / 8 = 1.625，这个值是一个小数，但是我们需要一个整数桶的编号，所以使用强制类型转换将其转换为整数，得到桶的编号1。

最后，我们将当前元素A[i]放入编号为1的桶中。这个操作将在桶数组buckets[1]中添加一个元素A[i]，也就是说，所有具有值在18到25之间的元素都会被放入这个桶中。

if (bucket_idx == bucket_size) bucket_idx--;   //为什么要这样写？

这行代码的作用是处理特殊情况，当元素A[i]的值等于最大值max_val时，如果不进行处理，就会导致数组越界的问题。

具体来说，如果元素A[i]的值等于最大值max_val，那么根据上面的计算公式，它的桶编号bucket_idx将等于bucket_size，也就是超出了桶数组的索引范围。此时，我们需要将它放到桶数组的最后一个桶中，而不是越界的桶。因此，我们需要将桶编号bucket_idx的值减1，将元素A[i]放入正确的桶中。

例如，如果最大值是90，最小值是10，桶的数量是10，那么每个桶的范围是8。如果当前元素A[i]的值是90，那么根据上面的计算公式，它的桶编号bucket_idx将等于10，这是越界的，但是我们将其减1，得到桶编号bucket_idx=9，将其放入最后一个桶中。

 int* bucket_counts = new int[bucket_size];  为什么要动态分配？

这段代码使用了动态内存分配语法，即使用 new 运算符在堆上分配内存。动态内存分配可以在程序运行时动态地分配内存，而不是在编译时确定内存大小，这使得程序更加灵活。

在这段代码中，动态内存分配用于创建一个大小为 bucket_size 的数组，用于存储每个桶中元素的数量。因为 bucket_size 是在运行时确定的，所以我们需要使用动态内存分配来分配一块大小为 bucket_size 的内存，用于存储计数器数组。

需要注意的是，在使用动态内存分配后，我们需要在不需要使用这些内存时，使用 delete 运算符释放它们。否则，这些内存将一直存在于程序中，占用计算机的内存资源，可能导致内存泄漏等问题。因此，我们应该在程序结束之前，使用 delete 运算符释放分配的内存，以保证程序的正确性和稳定性。

double** buckets = new double*[bucket_size]; 这个代码怎么理解？

这段代码使用了动态内存分配语法，即使用 new 运算符在堆上分配内存。它用于创建一个二维数组，表示桶排序中的桶。我们知道，桶排序算法的核心是将数据根据一定的规则分配到不同的桶中，因此需要用二维数组来表示多个桶。

首先，使用 new double*[bucket_size] 创建一个大小为 bucket_size 的数组，用于存储每个桶的指针。每个元素都是一个指向 double 类型的指针，用于指向该桶的第一个元素。这里 double* 表示指向 double 类型的指针。

然后，我们需要为每个桶分配空间。对于每个桶，我们使用 new double[bucket_counts[i]] 分配一个大小为该桶中元素数量的数组空间，用于存储该桶中的元素。

需要注意的是，在使用动态内存分配后，我们需要在不需要使用这些内存时，使用 delete 运算符释放它们。否则，这些内存将一直存在于程序中，占用计算机的内存资源，可能导致内存泄漏等问题。因此，我们应该在程序结束之前，使用 delete 运算符释放分配的内存，以保证程序的正确性和稳定性。

double** buckets 是什么意思？

double** buckets 表示一个指向指针的指针，也可以称为二级指针。在这里，buckets 是一个指向指针数组的指针，它用于存储指向每个桶的指针。具体来说，它是一个二维数组的指针，用于存储多个桶的地址。

使用 double** 类型的指针可以动态地分配内存，并且可以方便地访问多维数组中的元素。在桶排序算法中，我们使用 double** 类型的指针来表示多个桶，每个桶又是一个 double 类型的指针，指向该桶中的元素。这样可以更加方便地对多个桶进行操作，以实现桶排序算法的功能。

这种 double** buckets = new double*[bucket_size];  是二维数组？

double** buckets = new double*[bucket_size] 并不是一个二维数组，而是一个指针数组。

在 C/C++ 中，二维数组和指针数组有着不同的表示方式。二维数组是一个连续的内存块，它的每个元素都有固定的大小，可以通过指针访问其中的元素。而指针数组是一个由指针组成的数组，每个元素都是一个指针，指向一个独立的内存块。

在桶排序算法中，我们使用指针数组来存储多个桶的地址，这些桶在内存中是独立的内存块，每个桶又是由一个指针指向的 double 数组，用于存储该桶中的元素。因此，double** buckets 表示一个指针数组，其中每个元素都是一个指向 double 数组的指针，用于存储桶中的元素。可以将其理解为一个由多个一维数组组成的数组。

用示意图把buckets 演示出来

好的，下面是一个简单的示意图，它展示了一个大小为 5 的 buckets 数组，每个元素指向一个 double 数组，用于存储该桶中的元素：

buckets:
+---+    +---+---+---+
|   | -> |   |   |   |
+---+    +---+---+---+
|   | -> |   |   |   |   +---+
+---+    +---+---+---+   |   |
|   | -> |   |   |   |   +---+
+---+    +---+---+---+   |   |
|   | -> |   |   |   |   +---+
+---+    +---+---+---+   |   |
|   | -> |   |   |   |   +---+
+---+    +---+---+---+   |   |
                         +---+

在这个示意图中，buckets 数组中的每个元素都是一个指向 double 数组的指针，用于存储该桶中的元素。例如，buckets[0] 指向的 double 数组中存储了第一个桶中的元素，buckets[1] 指向的 double 数组中存储了第二个桶中的元素，以此类推。