1.什么是桶排序?
桶排序是一种排序算法,实际上并没有进行比较排序,而是借助了数组。
2.实现原理
假定有1-100个编号的桶(既定义一个长度为100的整型一维数组),每输入一个数字·就在对应的桶上插一个小旗(也就是对应下标的桶加1次),如果这个数字出现了n次就在对应桶上插n个小旗,当所有数输入完毕时,只需要从下标1开始找那些数字是1,如果是1就打印1次,是2就打印2次,是多少就打印多少次。
3.疑惑点
为什么我们没有比较大小就排序出来了呢?因为数组下标本身就是已经排好了,只要出现一次数就在对应下标上+1,然后遍历数组中那些大于1就行。但是判断大于1不能用if判断,如果用if如果数字出现了两个虽然下标对应的数已经大于1但是只会打印一次,会造成数据丢失的bug。
4.优缺点
缺点:
使用桶排序占用内存很大,若果需要排序的数字是1和10000这两个数,就必须定义10000个桶,因为必须在10000这个桶上插小旗;由于桶的标号只能是整数(数组下标原因)所以他并不能排序小数,只能排序整数,且如果有负数那么代码量将大大增加,效率不在那么高。
优点:
相比冒泡排序桶排序程序实现更加简单,而且效率也高了很多,由于冒泡排序的双层for在排序的数字很多时则会使效率变得很低。
5.桶排序c语言代码
#include<stdio.h>int main(){ int improt; //申明整型数组,相当于申明了100个桶[100] int array[100]; //用于接受键盘输入的数 for(int i=0;i<100;i++){ array[i] = 0; //把数组赋值为0,也就是每个桶都没被占用过 } for(int j=1;j<=5;j++){ scanf("%d",&improt); //循环录入要比较的5个数 array[improt]++; //输入的是数字几,就在对应桶上+1次,表示被占用了 } for(int k=0;k<100;k++){ //把数组拿出来看看,当然其中可能也有为0的数,国为没被占 for(int z= 0;z<array[k];z++){ //可能你想的是用if判断是不是1,但是如果此数字出现了两次呢? printf("%d",k); } } return 0;}
5.桶排序Java代码
public static void main(String[] args) { int[] source = new int[]{8,3,7,12,5,6,9}; bucketSort(source);}
public static void bucketSort(int[] array){ int[] reslut = new int[13]; for (int i = 0; i < array.length; i++) { reslut[array[i]]++; }
for (int i = 0; i < reslut.length; i++) { for (int j = 1; j <= reslut[i]; j++) { System.out.println(i); } }}