排序算法之桶排序

Bucket_Sort(桶排序)

一、算法思想：

1. 根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数；
2. 遍历待排序集合，将每一个元素移动到对应的桶中；
3. 对每一个桶中元素进行排序，并移动到已排序集合中。

二、时间复杂度：O(n)  这是一种以空间换时间的排序算法。

三、稳定性：稳定.

四、代码段：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>

#define random_set(a,b) ((rand()%(b-a))+a) //获取a到b范围内随机数

int main(void)
{
	int array_stu[50];  //用来保存每个同学的分数
	int array_out[100];  //用来保存排序后的分数

	srand((int)time(NULL));// 设置随机数基准保证每次运行结果不同

	//先初始化两个数组
	memset(array_stu, 0, sizeof(array_stu));
	memset(array_out, 0, sizeof(array_out));

	//用程序随机给50个同学打分
	for (int i = 0; i < 50; i++)
	{
		array_stu[i] = random_set(1, 99);
	}

	//把50个学生的分数分别丢到对应的桶里去
	for (int i = 0; i < 50; i++)
	{
		for (int j = 1; j < 100; j++)
		{
			//如果分数根桶的编号一样，就把这个桶的数据增加
			if (array_stu[i] == j)
			{
				array_out[j]++;
			}
		}
	}
	//把排序后的数据输出
	for (int i = 0; i < 100; i++)
	{
		//有些同学的分数是一样的
		while (array_out[i]>0)
		{
			printf("%d\n", i);
			array_out[i]--;
		}
	}
	return 0;
}