chapter_sorting/bucket_sort/

[giscus[bot]]

chapter_sorting/bucket_sort/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_sorting/bucket_sort/

[ahbji]

这个结构有点像链式地址实现的哈希表

[krahets]

非常形象！

[Ruijie-Qin]

最坏情况的时间复杂度为什么是O(n^2)呢？

[krahets]

Hi 最差情况下，所有元素被分至同一个桶中。如果我们采用 $O(n^2)$ 算法来排序这些元素，则时间复杂度为 $O(n^2)$

[buynonsense]

其实我看到这里的时候也有这个疑问，在最差情况下所有数据分配到1个桶，那么时间复杂度应该取决于桶内部的排序使用的排序算法？比如在桶内使用快速排序或者插入排序结果应该不一样

[HuaWang135608]

个人认为应当取决于内置排序算法的复杂度，一般和最优策略一样认为是 $O(\log n)$

[HuaWang135608]

不好意思：$O(n \log n)$

[Choukoo]

合并结果那里是不是应该是遍历K个桶？

[muzishuiji]

大佬，有一点疑惑，合并的地方是双层循环，为啥时间复杂度是O(n + k)？我以为是O(n * k)。我看的是js实现部分。

[krahets]

@muzishuiji 共 k 个桶、 n 个元素，因此最多循环 n + k 次，即遍历到所有桶中的所有元素。

[lxm520]

这个最多循环 n + k 次，在我理解下来是到了最坏的情况，比如都在最后一个桶，前面k-1是空，第k桶是要循环n个元素？

[krahets]

@lxm520 对，可以这样想。也可以更简单点：把遍历桶的 for 循环也计入的，那么仅 for 循环就是 O(k) ，循环体内遍历所有元素是 O(n) ，加起来是 $O(n + k)$ 。

[lxm520]

好的，谢谢大佬

[Tech-Liao]

第九行：应该改为：i = int(num % k)，不是：i = int(num*k）

[fwqaaq]

而且应该由范围决定桶的数量，代码太突兀了，让人非常不理解

[jianweijiang0905]

有没有可能作者给出的范例是数据被进行了归一化要求范围是[0,1)的数据？你list索引 out of range应该是你没注意num数值大于了1才会得到i>k,出现越界问题

[jianweijiang0905]

如果你是拿一组自己给定的随机数据集合去测试，你应该对这组数据进行归一化到[0,1)范围内再调用这个函数，而不是直接调初始数据列表做参数

[jianweijiang0905]

上面你提到的 i = int(num% k) 这种改法确实可以解决越界报错，但是你这每个桶里的数据就是无序的，无法保证每个桶子之间仍然是有序的

[Tech-Liao]

是的，你说的太对了，我理解出问题啦，很抱歉！耽误大佬的时间啦

[rookiexxj]

笔记：
桶映射第一步分桶，每个桶放多个元素
第二步，把元素送进桶里，要用映射将输入数据映射到【0，k-1】
第三步，桶内排序
第四步，合并

[Gaoshu101]

C++:
对建堆部分修改如下 可解决 下标越界问题。主要是分桶时每个元素都需要对数组的最小值进行归一。针对数组元素类型为int的情况(其它部分相应也要改成int)。【正文示例的最小值就是0，所以不需要这几步】

	// 建堆   
	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);
	}

[Gaoshu101]

就当没看到吧。。我再看看

[Gaoshu101]

先这个吧，感觉稍微通用点

#include<iostream>
#include<vector>
#include<algorithm> // sort()
using namespace std;

/* 桶排序 */
void bucketSort(vector<int>& nums) {
    auto minmax =  minmax_element(nums.begin(), nums.end());
    int min_value = *minmax.first;
    int max_value = *minmax.second;
    // 确定 桶的个数
    int k = (max_value - min_value ) / nums.size() + 1;    // 修改1
    vector<vector<int>> buckets(k);
    // 1. 将数组元素分配到各个桶中
    for (int num : nums) {
        // 
        int i = (num - min_value)/ nums.size();    //  修改2
        // 将 num 添加进桶 bucket_idx
        buckets[i].push_back(num);
    }
    // 2. 对各个桶执行排序
    for (vector<int>& bucket : buckets) {
        // 使用内置排序函数，也可以替换成其他排序算法
        sort(bucket.begin(), bucket.end());
    }
    // 3. 遍历桶合并结果
    int i = 0;
    for (vector<int>& bucket : buckets) {
        for (int num : bucket) {
            nums[i++] = num;
        }
    }
}


int main() {
    vector<int> nums = { 4, 1, 3, 1, 5, 2 };
	cout << "排序前：\n";
	for (auto it = begin(nums); it != end(nums); it++)
		cout << *it << " ";
	cout << "\n排序后：\n";
	bucketSort(nums);
	for (int i = 0; i < nums.size(); i++)
		cout << nums[i] << " ";
	return 0;
}

[krahets]

谢谢分享，本文没有对桶排序的通用性做充足考虑。主要还是理解桶排序的原理，取之范围的处理加一个归一化操作就好

[zeinsshiri]

怎么理解这个值（key）映射到[0,k-1]的函数？

// 1. 将数组元素分配到各个桶中
    for (int num : nums) {
        // 
        int i = (num - min_value)/ nums.size();    //  修改2
        // 将 num 添加进桶 bucket_idx
        buckets[i].push_back(num);
    }

[zeinsshiri]

明白了，区间放缩

[peng-yq]

「桶排序 bucket sort」是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。
将平均二字去掉会不会好些？

[peng-yq]

没看到后文，不好意思x

[hash-panda]

桶排序使用了内置的排序算法 sort，但是 sort 的时间复杂度是 O(nlogn)，然后嵌套在 for 循环中，这不是时间复杂度更高了么？ 是因为桶的数量是固定数量（常数级），因此这里的 sort 的时间复杂度就是一个常数级别 O(1) 么？

这里有点疑惑，望解惑

[krahets]

Hi，推算过程在本文“算法特性”有讲。核心点在于：每个桶内的元素数量是 $n / k$ ，当 $k$ 比较大时，我们就认为 $n \ k$ 趋向于常数级别。

[lets2zg]

大佬,cpp实现的桶内排序至少得是stable_sort, 这样清晰的指出以免误导后来者

[krahets]

Hi，在这里我们没有限定一定需要“稳定排序”。

[hlc199399]

大神，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++;
        }

这段代码将元素放入桶中的时候感觉已经将桶里的元素给排序了，是我理解错了吗？

[YannisLing]

个人认为你理解得非常正确

[Lijingwoquan]

我也赞成你 我刚刚看的时候也感觉很奇怪 感觉就是在排序

[Lijingwoquan]

 // 如果桶中有数据且数据小于当前值 nums[i], 要将其放到当前桶的后面，相当于 cpp 中的 push_back
        while (buckets[bucket_idx][j] > 0 && buckets[bucket_idx][j] < nums[i]) {
            j++;
        }
        float temp = nums[i];
        while (j < size && buckets[bucket_idx][j] > 0) {
            swap(&temp, &buckets[bucket_idx][j]);
            j++;
        }
        buckets[bucket_idx][j] = temp;

改成

    while (buckets[bucket_idx][j] > 0 ) {
            j++;
        }

就是只进行插入了

[krahets]

谢谢指正！已于 #1272 修复

@Lijingwoquan 提出的方法可能不完全正确：由于数据有可能为 0 ，因此用 buckets[bucket_idx][j] > 0 作为判断条件并不安全。并且 while 循环也不是必须的，它会引入额外的时间开销

[jackgit-ui]

nlogn/k，为什么k很大时，趋近于n呢？

[nors1993]

个人认为：k趋近于n时，logn/k相当于常数0，复杂度为O(1)。

[tronespant]

学习算法的的好方法