chapter_sorting/bucket_sort/ #440
Replies: 13 comments 34 replies
-
这个结构有点像链式地址实现的哈希表 |
Beta Was this translation helpful? Give feedback.
-
最坏情况的时间复杂度为什么是O(n^2)呢? |
Beta Was this translation helpful? Give feedback.
-
合并结果那里是不是应该是遍历K个桶? |
Beta Was this translation helpful? Give feedback.
-
第九行:应该改为:i = int(num % k),不是:i = int(num*k) |
Beta Was this translation helpful? Give feedback.
-
笔记: |
Beta Was this translation helpful? Give feedback.
-
C++: // 建堆
int k = nums.size() / 2;
auto min_it = min_element(nums.begin(), nums.end());
int min_value = *min_it;
vector<vector<int>> buckets(k);
for (int num : nums) {
int i = (num - min_value) % k; // 分桶
buckets[i].push_back(num);
} |
Beta Was this translation helpful? Give feedback.
-
「桶排序 bucket sort」是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶,每个桶对应一个数据范围,将数据平均分配到各个桶中;然后,在每个桶内部分别执行排序;最终按照桶的顺序将所有数据合并。 |
Beta Was this translation helpful? Give feedback.
-
桶排序使用了内置的排序算法 sort,但是 sort 的时间复杂度是 O(nlogn),然后嵌套在 for 循环中,这不是时间复杂度更高了么? 是因为桶的数量是固定数量(常数级),因此这里的 sort 的时间复杂度就是一个常数级别 O(1) 么? 这里有点疑惑,望解惑 |
Beta Was this translation helpful? Give feedback.
-
大佬,cpp实现的桶内排序至少得是stable_sort, 这样清晰的指出以免误导后来者 |
Beta Was this translation helpful? Give feedback.
-
大神,c语言代码里 : // 1. 将数组元素分配到各个桶中
for (int i = 0; i < size; i++) {
// 输入数据范围为 [0, 1),使用 num * k 映射到索引范围 [0, k-1]
int bucket_idx = nums[i] * k;
int j = 0;
// 如果桶中有数据且数据小于当前值 nums[i], 要将其放到当前桶的后面,相当于 cpp 中的 push_back
while (buckets[bucket_idx][j] > 0 && buckets[bucket_idx][j] < nums[i]) {
j++;
}
float temp = nums[i];
while (j < ARRAY_SIZE && buckets[bucket_idx][j] > 0) {
swap(&temp, &buckets[bucket_idx][j]);
j++;
} 这段代码将元素放入桶中的时候感觉已经将桶里的元素给排序了,是我理解错了吗? |
Beta Was this translation helpful? Give feedback.
-
nlogn/k,为什么k很大时,趋近于n呢? |
Beta Was this translation helpful? Give feedback.
-
学习算法的的好方法 |
Beta Was this translation helpful? Give feedback.
-
桶排序在对每个桶进行快排的时候,不是也用了比较吗?这样是算非比较排序吗? |
Beta Was this translation helpful? Give feedback.
-
chapter_sorting/bucket_sort/
一本动画图解、能运行、可提问的数据结构与算法入门书
https://www.hello-algo.com/chapter_sorting/bucket_sort/
Beta Was this translation helpful? Give feedback.
All reactions