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】
第三步，桶内排序
第四步，合并

[Gaoshu-root]

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);
	}

[Gaoshu-root]

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

[Gaoshu-root]

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

#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]

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

[Lirous587]

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

[Lirous587]

 // 如果桶中有数据且数据小于当前值 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)。

[backtraxe]

元素数量n个，所以桶的数量k在范围[0,n]之间，最少每个桶1个元素，再多桶也无意义。

$$ \lim_{k \to n} n \log\left(\frac{n}{k}\right) = 0 $$

所以排序复杂度 $O(1)$，再加上遍历复杂度 $O(n)$，总体时间复杂度 $O(n)$。

[tronespant]

学习算法的的好方法

[abjzk]

桶排序在对每个桶进行快排的时候，不是也用了比较吗？这样是算非比较排序吗？

[SCUTking]

但是核心思想没有使用比较排序

[SCUTking]

映射函数的选取：index := (nums[i] - minNum) / bucketSize //减去最小值，然后查看对应的索引在哪
桶的大小：所有桶的容量必须要大于数组的大小
桶的数量：bucketCount := (maxNum-minNum)/bucketSize + 1 //桶的数量，这么算可以将所有的数据都涵盖进来

[Teslajia]

图11-15是不是有点问题，不过不影响整体理解，μ=25的话，10-25与25-80的区间长度明显不匹配

[lexnewgate]

如果把排序理解为从一个初位置移动到最终位置，那么桶排序之所以快的原因是因为在放入桶的过程中某种意义就完成了粗略的排序。从快排的视角来看，就像是有k个哨兵，然后哨兵范围的相对顺序都整理好了

[tstanon]

桶排序的C语言实现，桶内排序采用插入排序

void insertion_sort(float *arr, int size) {
    for (int i = 1; i < size; i++) {
        float key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
void bucket_sort(float *arr, int size, int k = 4){
    float *buckets[k], max_val, min_val, interval; int bucket_size[k], idx; if (size > 0) { max_val = arr[0]; min_val = arr[0];} // 最大最小值用于计算桶间隔
    for (int i = 0; i < k; i++) { buckets[i] = (float *)malloc(sizeof(float) * size); bucket_size[i] = 0; }
    for (int i = 1; i < size; i++) { if (arr[i] > max_val) max_val = arr[i]; if (arr[i] < min_val) min_val = arr[i]; } interval = (max_val - min_val) / k; if (max_val == min_val) return; // 计算桶的间隔；如果最大值和最小值相等，直接返回; 避免出现后续的除以0的情况
    for (int i = 0; i < size; i++) { idx = (int)((arr[i] - min_val) / interval); if (idx >= k) idx = k - 1; buckets[idx][bucket_size[idx]++] = arr[i]; } // 计算当前元素所属的桶；当 arr[i] 恰好等于 max_val 时，idx 会计算为 k，而 k 是桶的数量，这会导致数组越界。
    for (int i = 0; i < k; i++) { insertion_sort(buckets[i], bucket_size[i]); } // 对每个桶进行排序
    idx = 0; for (int i = 0; i < k; i++) { for (int j = 0; j < bucket_size[i]; j++) { arr[idx++] = buckets[i][j]; } free(buckets[i]); } // 将桶中的元素取出
}

[tstanon]

桶排序的C语言实现，桶内排序采用快速排序

int compare_floats(const void *a, const void *b) {
    float fa = *(const float*)a;
    float fb = *(const float*)b;
    return (fa > fb) - (fa < fb); // fa > fb 返回正数, fa < fb 返回负数, 相等返回0
}
void bucket_sort(float *arr, int size, int k = 4){
    float *buckets[k], max_val, min_val, interval; int bucket_size[k], idx; if (size > 0) { max_val = arr[0]; min_val = arr[0];} // 最大最小值用于计算桶间隔
    for (int i = 0; i < k; i++) { buckets[i] = (float *)malloc(sizeof(float) * size); bucket_size[i] = 0; }
    for (int i = 1; i < size; i++) { if (arr[i] > max_val) max_val = arr[i]; if (arr[i] < min_val) min_val = arr[i]; } interval = (max_val - min_val) / k; if (max_val == min_val) return; // 计算桶的间隔；如果最大值和最小值相等，直接返回; 避免出现后续的除以0的情况
    for (int i = 0; i < size; i++) { idx = (int)((arr[i] - min_val) / interval); if (idx >= k) idx = k - 1; buckets[idx][bucket_size[idx]++] = arr[i]; } // 计算当前元素所属的桶；当 arr[i] 恰好等于 max_val 时，idx 会计算为 k，而 k 是桶的数量，这会导致数组越界。
    for (int i = 0; i < k; i++) { qsort(buckets[i], bucket_size[i], sizeof(float), compare_floats); } // 对每个桶进行排序
    idx = 0; for (int i = 0; i < k; i++) { for (int j = 0; j < bucket_size[i]; j++) { arr[idx++] = buckets[i][j]; } free(buckets[i]); } // 将桶中的元素取出
}

[Aziteee]

不换行看着好难受啊

[tstanon]

可以用IDE一键排版，vscode和clion都有

[checkma-xh]

import random


def sort(nums):
    k = len(nums) // 2
    buckets = [[] for _ in range(k)]
    new_nums = []

    for num in nums:
        buckets[int(num * k)].append(num)
    for bucket in buckets:
        bucket.sort()
        new_nums.extend(bucket)
    
    return new_nums

# nums = [random.random() for _ in range(10)]
nums = [random.randrange(0, 100) / 100 for _ in range(10)]
print(nums)
print(sort(nums))

[0.26, 0.6, 0.49, 0.1, 0.27, 0.93, 0.7, 0.76, 0.95, 0.55]
[0.1, 0.26, 0.27, 0.49, 0.55, 0.6, 0.7, 0.76, 0.93, 0.95]

[YangyuChenXS]

这里的空间复杂度为什么不是 O(n)？

[syutengu]

[syutengu]

js最后一步合并各桶可以这样简写：

return buckets.flat(Infinity)

[syutengu]

进一步利用内置函数，还可以one line实现

const bucketSort = nums => Object.values(
  Object.groupBy(nums, num => Math.floor(num * nums.length / 2))//1. 分
)
  .map(e => e.sort((a, b) => a - b))//2. 排
  .flat()//3. 合

[MoRongsi]

牛逼