请用C++写桶排序算法

#include <stdio.h>

void bucketSort(int arr[], int n) {
int i, j;
int buckets[n];

for (i = 0; i < n; i++) {
buckets[i] = 0;
}

for (i = 0; i < n; i++) {
(buckets[arr[i]])++;
}

for (i = 0, j = 0; i < n; i++) {
while ((buckets[i])--) {
arr[j++] = i;
}
}
}

int main() {
int arr[] = { 8, 1, 5, 3, 2, 6, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int i;

printf("Before sorting:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

bucketSort(arr, n);

printf("\nAfter sorting:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

相关问题

请用C++实现桶排序算法

桶排序是一种非比较型整数排序算法，它将输入数据分布到有限数量的“桶”中，每个桶再分别进行排序，最后汇总所有桶的结果得到有序序列。以下是C++实现的基本步骤：

#include <iostream>
#include <vector>
#include <list>

void bucketSort(int arr[], int n, int bucketSize) {
    // 创建大小为bucketSize的固定大小的桶
    std::vector<std::list<int>> buckets(bucketSize);

    // 将元素放入相应的桶中
    for (int i = 0; i < n; ++i) {
        int index = arr[i] / bucketSize;
        buckets[index].push_back(arr[i]);
    }

    // 对每个桶内的元素单独排序
    for (std::list<int>& bucket : buckets) {
        bucket.sort();
    }

    // 合并所有已排序的桶
    int sortedIndex = 0;
    for (const auto& bucket : buckets) {
        for (auto& num : bucket) {
            arr[sortedIndex++] = num;
        }
    }
}

int main() {
    int arr[] = {5, 8, 1, 9, 3, 7, 2, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original array: ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << "\n";

    bucketSort(arr, n, 5); // 假设我们选择桶的大小为5

    std::cout << "Sorted array: ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << "\n";

    return 0;
}

在这个例子中，我们首先计算出桶的数量，并创建相应数量的桶列表。然后遍历数组，将每个元素放到对应的桶中。接着对每个桶里的元素进行排序，最后合并所有的桶，就得到了排序后的数组。

用C++写一个桶排序算法

好的，以下是用C++实现的桶排序算法：

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

void bucketSort(vector<int>& nums, int max_val) {
    vector<int> bucket(max_val + 1, 0);

    for (int num : nums) {
        bucket[num]++;
    }

    int i = 0;
    for (int j = 0; j <= max_val; j++) {
        while (bucket[j] > 0) {
            nums[i++] = j;
            bucket[j]--;
        }
    }
}

int main() {
    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int max_val = 9;

    bucketSort(nums, max_val);

    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

这里用了一个辅助数组`bucket`来记录每个元素出现的次数。首先遍历原始数组，统计每个元素的出现次数，然后再根据桶的顺序依次将元素放回原始数组中。时间复杂度为O(n+k)，其中k是桶的个数，最坏情况下k=n，所以时间复杂度为O(n^2)。