你好,请问桶排序有什么特点,方便给出解释和相关C代码吗?
时间: 2023-02-22 08:55:00 浏览: 58
你好!桶排序是一种非比较型排序算法,它的特点是:
1. 时间复杂度:O(n),当数据分布比较均匀时效率高。
2. 空间复杂度:O(n),因为需要开辟若干个桶。
3. 稳定性:稳定。
桶排序适用于数据分布比较均匀的情况,因为它的时间复杂度与数据的分布有关,而与数据的范围无关。
以下是C语言代码实现的桶排序:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void bucket_sort(int arr[], int n)
{
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
int *bucket = (int *)malloc((max + 1) * sizeof(int));
memset(bucket, 0, (max + 1) * sizeof(int));
for (int i = 0; i < n; i++)
bucket[arr[i]]++;
int k = 0;
for (int i = 0; i <= max; i++)
for (int j = 0; j < bucket[i]; j++)
arr[k++] = i;
free(bucket);
}
int main(void)
{
int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
bucket_sort(arr, n);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)