排序方法——桶排序

• 概念：
• • leetcode164

概念：

Bucket Sort——
基本思路是：

1.将待排序元素划分到不同的痛。先扫描一遍序列求出最大值 maxV 和最小值 minV ，设桶的个数为 k ，则把区间 [minV, maxV] 均匀划分成 k 个区间，每个区间就是一个桶。将序列中的元素分配到各自的桶。
2.对每个桶内的元素进行排序。可以选择任意一种排序算法。
3.将各个桶中的元素合并成一个大的有序序列。

假设数据是均匀分布的，则每个桶的元素平均个数为 n/k 。假设选择用快速排序对每个桶内的元素进行排序，那么每次排序的时间复杂度为 O(n/klog(n/k)) 。总的时间复杂度为 O(n)+O(k)O(n/klog(n/k)) = O(n+nlog(n/k)) = O(n+nlogn-nlogk 。当 k 接近于 n 时，桶排序的时间复杂度就可以金斯认为是 O(n) 的。即桶越多，时间效率就越高，而桶越多，空间就越大。

leetcode164

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

思路:
利用桶排序，需要设计桶的大小（间隔），具体公式如下——

链接: leetcode 分析link.

代码:

// An highlighted block
class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if not nums or len(nums) < 2: return 0        
        max_ = max(nums)
        min_ = min(nums)
        max_gap = 0
        
        each_bucket_len = max(1,(max_-min_) // (len(nums)-1))#每个桶的长度至少为1
        # if max_==min_:
        #     return 0
        buckets =[[] for _ in range((max_-min_) // each_bucket_len + 1)]
        
        for i in range(len(nums)):
            loc = (nums[i] - min_) // each_bucket_len
            buckets[loc].append(nums[i])
        print(buckets)
        prev_max = float('inf')
        for i in range(len(buckets)):
            if buckets[i] and prev_max != float('inf'):
                max_gap = max(max_gap, min(buckets[i])-prev_max)
            
            if buckets[i]:
                prev_max = max(buckets[i])               
        return max_gap