企业seo网站推广,北京做网站设计招聘,广西城乡住房建设部网站,苏州建站之家上榜理由#xff1a; 如果没见过这种排序题#xff0c;可能首先想到的就是常用的排序算法#xff0c;比如快速排序#xff0c;归并排序#xff0c;那如果输入的n足够大#xff0c;时间复杂度肯定比较高。其实题目0-1000的范围是一个题眼#xff0c;所以一定有更优的排序…上榜理由 如果没见过这种排序题可能首先想到的就是常用的排序算法比如快速排序归并排序那如果输入的n足够大时间复杂度肯定比较高。其实题目0-1000的范围是一个题眼所以一定有更优的排序算法这里用到了桶排序
回顾经典排序算法有
冒泡排序Bubble Sort插入排序Insertion Sort希尔排序Shell Sort选择排序Selection Sort快速排序Quick Sort归并排序Merge Sort堆排序Heap Sort计数排序Counting Sort桶排序Bucket Sort 思路就是
首先0-1000的值域创建1001个桶每个桶都对应一个index里面放一个初始值count0表示大小是index的数出现的个数。
然后遍历n个数就把这1001个桶里的count更新一次
接着再根据要求从大到小或者从下到大遍历1001个桶如果count0表示出现过count就打印count个对应桶index的值
最后就完成了排序算法输出 //bucket_sort.cpp#include stdio.h#include cstringint main(){int bucket[1001],i,j,t,n;memset(bucket,0,sizeof bucket);printf(please enter total number \n);scanf(%d,n);//输入一个数n表示接下来有n个数printf(now please enter the data\n);for(i1;in;i)//循环读入n个数并进行桶排序{scanf(%d,t); //把每一个数读到变量t中bucket[t]; //进行计数对编号为t的桶放一个小旗子}printf(sort data is: \n);for(i1000;i0;i--) //依次判断编号1000~0的桶for(j1;jbucket[i];j) //出现了几次就将桶的编号打印几次printf(%d ,i);printf(\n);return 0;}
附个编译代码和输出测试
gcc -o test bucket_sort.cpp./test
