请用C++写桶排序算法
时间: 2023-11-24 20:06:20 浏览: 36
#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++实现的桶排序算法:
```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)。
请写一下桶排序的算法
桶排序是一种线性排序算法,它的基本思想是将待排序的元素分配到一定数量的桶中,然后对每个桶中的元素进行排序,最后依次将每个桶中的元素输出,从而得到有序的序列。
桶排序的算法步骤如下:
1. 创建一个定量的空桶子列表。
2. 遍历输入数据,并且把数据一个一个放到对应的桶子里去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把排好序的数据拼接起来。
以下是桶排序的 C++ 代码实现:
```cpp
void bucket_sort(int arr[], int n) {
const int bucket_size = 10; // 桶的数量,这里设为10
vector<int> buckets[bucket_size]; // 创建桶
int max_val = *max_element(arr, arr + n); // 获取最大值
for (int i = 0; i < n; i++) {
int bucket_idx = arr[i] * bucket_size / (max_val + 1); // 计算元素所在的桶编号
buckets[bucket_idx].push_back(arr[i]); // 把元素放入对应的桶中
}
for (int i = 0; i < bucket_size; i++) {
sort(buckets[i].begin(), buckets[i].end()); // 对每个桶中的元素进行排序
}
int idx = 0;
for (int i = 0; i < bucket_size; i++) {
for (int j = 0; j < buckets[i].size(); j++) {
arr[idx++] = buckets[i][j]; // 把排序后的元素依次放回原数组
}
}
}
```
桶排序的时间复杂度为O(n),但是需要额外的空间来存储桶,因此空间复杂度取决于桶的数量。