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)$

[xbsheng]

这地方可能有点歧义，个人认为这句话的意思是：最差的情况下所有的数据分布到一个桶中，并且桶内排序使用最差的O(n^2)的算法，这是最差的情况下的复杂度O(n^2)

[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$ 趋向于常数级别。

[Jetmores]

大佬,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的区间长度明显不匹配

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

牛逼

[ikunycj]

    float[] nums1 = {0.49f,0.96f,0.82f,0.09f,0.57f,0.43f,0.91f,0.75f,0.15f,37f};为什么我用java测试会报索引越界异常？

[fhm233]

注意审题：元素是范围[0,1)内的浮点数，你整个37f

[HighBigSky]

离散数学?二项分布、泊松分布妙，妙啊（doge

[xiaoyaozizaiwoweidu]

上面浮点数范围 [0, 1) 的桶排序，桶索引index = int(num * bucket_count)

下面实现整数和负数的整数和负数的桶排序，桶索引index = (num + offset) // bucket_size

def bucket_sort(nums, bucket_count):
    """
    桶排序算法
    :param nums: 待排序的数组
    :param bucket_count: 桶的数量
    :return: 排序后的数组
    """
    # 找到数组中的最小值
    min_val = min(nums)
    # 找到数组中的最大值
    max_val = max(nums)
    
    # 计算索引偏移量，用于将所有元素转换为非负数
    offset = -min_val
    
    # 计算每个桶的大小
    # 确保桶的大小至少为 1，避免出现桶大小为 0 的情况
    bucket_size = max(1, (max_val - min_val) // bucket_count + 1)
    
    # 初始化桶，创建 bucket_count 个空桶
    buckets = [[] for _ in range(bucket_count)]
    
    # 将数组中的元素分配到各个桶中
    for num in nums:
        # 计算元素 num 应该分配到的桶的索引
        index = (num + offset) // bucket_size
        # 将元素 num 添加到对应的桶中
        buckets[index].append(num)
    
    # 对每个桶中的元素进行排序
    # 这里使用 Python 的内置排序函数
    for bucket in buckets:
        bucket.sort()
    
    # 合并所有桶中的元素，将排序后的结果写回原数组 nums
    i = 0  # 原数组的索引
    for bucket in buckets:
        for num in bucket:
            nums[i] = num  # 将排序后的元素写回原数组
            i += 1  # 索引加 1
    
    return nums

[MarsToken]

感觉这个也可以用于任意数吧，不一定是[0,1)；关键看怎么塞到桶里。
看我的代码：
private static void buketSort(int[] array) {
int bucket_deep = 2;
int bucket_count = array.length / bucket_deep;
List<List> buckets = new ArrayList<>();
for (int i = 0; i < bucket_count; i++) {
buckets.add(new ArrayList<>());
}
for (Integer element : array) {
int index = getIndex(array, element, bucket_count);
buckets.get(index).add(element);
}
for (List bucket : buckets) {
Collections.sort(bucket);
}
int i = 0;
for (List bucket : buckets) {
for (Integer element : bucket) {
array[i++] = element;
}
}
}

private static int getIndex(int[] array, int element, int bucket_count) {
    int min = array[0];
    int max = array[0];
    for (int ele : array) {
        if(min>ele){
            min=ele;
        }
        if(max<ele){
            max=ele;
        }
    }
    // 这一步很关键，确保索引不会数组越界
    return element / (max - min) * bucket_count;
}

[xiaozhuge123]

day09

[WangYun0918]

合并结果时需要遍历所有桶和元素，花费 O(n + k) 时间
请问合并结果不管有多少个桶，其元素总和不是 n 吗，为啥时间复杂度不是 O(n) 呢？

[WangYun0918]

不用解答了，已明白

[rainnnnnnnnnnnnnnnnnnnnnn]

不明白为什么桶排序不属于基于比较的排序哇，每个桶的内部不还是基于比较的排序算法嘛
在我理解中，桶排序也是在以空间（构建了一个尽可能使更多元素得到对应的桶序列）换时间（如果k=n的话，那么时间复杂度只有O（n））

[KahanaT800]

我的理解是这样：
比如6个数，0.1 0.2 0.4 0.6 0.8 0.9，给四个桶子，k就是4
乘出来就是 0.4 0.8 1.6 2.4 3.2 3.6， 然后向下取整就是 0, 0, 1, 2, 3, 3；这里其实很像哈希表，给数据一个新的地址；
然后每个桶里面的比较基本可以看成线性时间，因为桶的划分的目的就是尽量每个桶都放2个；
但是如果数据太集中然后桶给的不好，就会劣化很严重

[mygit10636]

c语言代码我看出两个问题
1.注释没说数组区间
2.每个桶都分配了n个元素的空间

[mygit10636]

疑问：为什么时间复杂度为O(n + k)