桶排序

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）

---

桶排序经典题.png

SWIFT:

class Solution {
    func maximumGap(_ nums: [Int]) -> Int {
        if nums.count < 2 { return 0 }
        if nums.count == 2 { return abs(nums[1] - nums[0]) }
        var min = nums[0]
        var max = nums[0]
        for item in nums {
            min = min < item ? min : item
            max = max > item ? max : item
        }
        if max == min { return 0 }
        let len: Int = Int(ceilf(Float(max - min) / Float(nums.count - 1)))
        let numOfbucket = (max - min) / len + 1
        if numOfbucket == 1 {return max - min}
        var arr: [Bucket?] = [Bucket?](repeating: nil, count: numOfbucket)
        for item in nums {
            let index = (item - min) / len
            if let tmp = arr[index] {
                if item < tmp.min {
                    arr[index]?.min = item
                }
                if item > tmp.max {
                    arr[index]?.max = item
                }
            } else {
                arr[index] = Bucket(max: item, min: item)
            }
        }
        var i = 1
        var gap = 0
        var left = arr[0]!
        while i <= numOfbucket - 1 {
            if arr[i] != nil {
                let right = arr[I]!
                let tmpGap = right.min - left.max
                gap = tmpGap > gap ? tmpGap : gap
                left = right
            }
            i += 1
        }

        return gap
    }
}

public struct Bucket {
    public var max: Int = 0
    public var min: Int = 0
}