首页 > 代码库 > 桶式排序
桶式排序
怎么理解桶式排序呢？
简单地说，桶式排序就是当我们知道待排序的每一个数据都大于等于零，并且小于一个正整数M，那么我们给出一个大小为M的数组，称之为bucket。于是这个数组能够容纳待排序的每一个数据的信息，我们遍历待排序数据，对于每一个数据i，我们使对应的bucket[i]加1。遍历完成之后，我们输出bucket数组中大于零的元素对应的序号（bucket[i]是多少，就打印多少个i出来）。那么输出的结果就是排好的数据。
桶式排序的复杂度分析：遍历待排序数据的过程O(N)，输出bucket中的元素的过程O(M)。所以复杂度为O(M+N)。
简单的代码实现如下：
1 #include <cstdio> 2 #include <cstdlib> 3 4 void 5 BucketSort(int arr[], int len, int bucket[]) 6 { 7 for (int i = 0; i < len; i++) { 8 bucket[arr[i]]++; 9 }10 }11 12 int13 main(int argc, char** argv) 14 {15 int arr[8] = {2, 7, 5, 29, 0, 3, 7, 21};16 int bucket[30] = {0};17 18 for (int i = 0; i < 8; i++) {19 printf("%d\t", arr[i]);20 }21 printf("\n");22 23 BucketSort(arr, 8, bucket);24 25 for (int i = 0; i < 30; i++) {26 while (bucket[i] >0) {27 printf("%d\t", i);28 bucket[i]--;29 }30 }31 printf("\n");32 33 system("pause");34 return 0;35 }
桶式排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。