C语言之简单桶排序

小咪咪 2022-03-11 02:10 172阅读 0赞

说到排序，生活中无处不在，比如身高，成绩等等。在我们学习语言中排序也是最热门的一个话题，那么我今天来就给大家分享一下简单的桶排序。估计大多数人听到桶排序这三个字时和我一样是懵的，因为我们最熟悉的莫过于冒泡排序，插入排序，快速排序等，桶排序到底是个神马东东。今天看到这个排序时，确实觉得它很牛，所以来和大家分享一下。

例：有6个同学考试成绩为 2 5 1 9 5 8 分，满分10分，现要求对其排序按照从小到大的方式。

桶排序思路：我们用一个数组表示桶，初始化全为0 ，将数组下标也就是桶的编号与学生成绩一一对应，满分十分成绩便在0~10之间，故此需要数组大小为11，即11个桶，然后我们便可以进行输入，将同学的成绩进行输入，分数对应桶的编号，成绩出现一次，我们便给桶里面放一面棋子，也就是让下标为i（成绩/痛的编号）的数组加一，直至输入结束。那么这样一来，数组里面便有了数字，即成绩，我们按顺序打印即可。数组下标即成绩，直接遍历，便已经排序好了。  
具体实现过程如下：

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    
    //桶排序 时间复杂度 O(M+N)
    
    int main()
    {
    	//对成绩进行排序  满分十分   
    	//6个同学分别考了  2 5 1 9 5 8 分
    	//按照从小到大的方式对这些分数进行排序
    	int arr[11] = { 0 };    //用arr数组来表示桶
    	int tmp;
    	printf("请输入要排序的学生人数：n= ");
    	int n;
    	scanf("%d", &n);
    	printf("请输入学生成绩：\n");
    	for (int i = 0; i < n; i++)
    	{
    		scanf("%d", &tmp);  //将输入的成绩保存到变量tmp中
    		arr[tmp]++;    //给桶中放入旗子，计数
    	}
    	//输出排序之后的成绩
    	printf("学生成绩按照从小到大排序为：\n");
    	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
    	{
    		for (int j = 0; j < arr[i]; j++)
    		{
    			printf("%d\t", i);
    		}
    	}
    	system("pause");
    	return 0;
    }

这个桶排序的时间复杂度为O(M+N),已经很快了，不过在这里我补充一下，这个是简易版的桶排序，真正的桶排序还是很复杂的，这个桶排序也有很多不足，比如它很浪费空间，假如有5个数为1 100 33949543 23 1232437955，那么岂不是要有非常多的桶来容纳了，再一个如果要排序的数是负数或者小数也就没办法了，所以有一定的局限性，不过我们可以吸收这种想法，在某些特殊时候，我们采用桶排序也会很方便的，值得大家去看一下。