浅显易懂的桶排序 原创 排序算法 2021年7月14日 07:08 夏至未至 1603 当前内容 2717 字，在路上，马上到，马上到 想准备将所有的排序算法都总结出来，方便你查阅，也方便我复习和记忆，下面来说桶排序： 首先必须申明，桶排序和计数排序完全不同，不可混为一谈：（这里实例用单链表来操作） 还是老方法，看文字就是烦，直接上图，图文结合，永远都是王道： 1.假设：桶待排序列：{ 49, 38, 35, 97, 76, 73, 27, 49 ,34,78}  看了之后有没有特莫感觉就是哈希桶，哈哈，满足一定条件差不多就是啦；言归正传，key值就是待排序序列，Bucket为桶，数据按某种函数，映射到桶中 2.关于映射及桶排原理分析： 桶中数据的十位都一样，那么映射函数算出的桶号就是这些数据的十位，也就是说，这种映射函数，目的就是为了找出数据的共同特点，可能是求余（哈希表直接定址，就是这样），可能是除某数求商，本例中就是取商； 即就是所有数据除某数取得的商相同的都放一个桶中，如图中的3号桶，刚开始，3号桶中的数据是无序的，第一遍操作，只能保证这些数据一定是在这个桶中， 但是桶中的顺序还是要排的，之后，遍历一遍桶，输出即就是一个有序序列，就这几句话，我感觉说完了，至于更深层 的剖析，稍后再说，先来代码： ```cpp #pragma once //每一个节点的结构 struct node { int key; //关键字，在桶中统计桶中数据量，在数据节点中就是节点的数据 struct node *next; }; //声明： void PrintBucketSort(node** bucket, int bucket_size); int f(int x); void BucketSort(int* a, int size,int bucket_size) { assert(a); //给桶申请空间 node** bucket = new node*[bucket_size*sizeof(node)]; //初始化 for (int i = 0; i < bucket_size; ++i) { bucket[i] = new node[sizeof(node)]; //每一个桶 bucket[i]->key = 0; bucket[i]->next = nullptr; } for (int j = 0; j < size; ++j) { node* sub_node = new node[sizeof(node)]; //桶下的每一个节点 sub_node->key = a[j]; sub_node->next = nullptr; //计算这数据在哪个桶中 int num = f(a[j]); //让一个指针指向这个桶号的头 node* sub_head = bucket[num]; //开始插入 if (sub_head->next == nullptr) { bucket[num]->next = sub_node; bucket[num]->key++; } //该桶号不为空，那么插入排序 else { while (sub_head->next != nullptr && sub_node->key >= sub_head->next->key) { sub_head = sub_head->next; } sub_node->next = sub_head->next; sub_head->next = sub_node; bucket[num]->key++; } } //打印 PrintBucketSort(bucket, bucket_size); } //映射函数 int f(int x) { return (x / 10); } //打印 void PrintBucketSort(node** bucket, int bucket_size) { //多少桶链(桶号) for (int i = 0; i < bucket_size; ++i) { node* cur = bucket[i]->next; while (cur) { cout << cur->key << " "; cur = cur->next; } } cout << endl; } void Test7() { int a[10] = { 49, 38, 35, 97, 76, 73, 27, 49, 34, 78 }; cout << "桶排序" << endl; BucketSort(a, 10, 10); //桶数据最大才97，所以需要10个桶 } ``` 看看结果：  第一个就是排序，第二个就是数据在桶中的分布，横行代表桶，10个桶，没有数据的桶是0； 桶排序就是这样： 对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为： O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM) 当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到```O(N)```。 桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。 此外，桶排序是稳定的。 本文标题： 浅显易懂的桶排序 本文作者： 夏至未至 发布时间： 2021年7月14日 07:08 最近更新： 2021年7月28日 07:03 原文链接： 许可协议： 署名-非商业性-禁止演绎 4.0 国际(CC BY-NC-ND 4.0) 请按协议转载并保留原文链接及作者 桶排序(1) 排序方法(4) 上一个 希尔排序 下一个 快速排序 当前文章评论暂未开放,请移步至留言处留言。
