数组-桶排序

采用桶排序方式对数组进行排序

桶排序百科:桶排序(Bucket Sort),或者所谓的箱排序是一种非比较排序.工作的原理是将数组分到有限数量的桶子里.每个桶子再个别排序.当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间O(n).

摘一个示例做个说明.
示例 1：
输入: [0,5,9,3,12,7]
输出: [0,3,5,7,9,12]

算法原理:

桶排序算法要求，数据的长度必须完全一样，程序过程要产生长度相同的数据

1. 设置一个定量的数组当作空桶；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来
5. 算法图示: 桶排序演示.png

算法分析:

1. 时间复杂度
   桶排序最好、最坏、平均时间复杂度为O(n)、O(n²)、O(n+k).
2. 空间复杂度
   桶排序空间复杂度为O(n+k).
3. 算法稳定性
   桶排序是一种稳定排序算法.

代码实现-Swift版本:

func bucketSort(_ num: [Int], _ gap: Int) -> [Int]{
    // 数组最大最小元素
    let maxNum: Int = num.max()!
    let minNum: Int = num.min()!
    // 桶的个数
    let bucketCount: Int = (maxNum - minNum) / gap + 1
    // 初始化桶
    var  bucketArray: [[Int]] = [[Int]](repeating: [Int](), count: bucketCount)
    for i in 0 ..< num.count {
        // 计算数据在桶的位置
        let index: Int = (num[i] - minNum) / gap
        bucketArray[index].append(num[i])
    }
    
    for i in 0 ..< bucketCount {
        if bucketArray[i].count > 0 {
            // 对桶内数据进行希尔排序,希尔排序为之前写的代码
            shellSort(nums: &bucketArray[i])
        }
    }
    
    var result = [Int]()
    
    for i in 0 ..< bucketCount {
        let bucket: [Int] = bucketArray[i]
        if bucket.count > 0 {
            // 数组添加桶数据
            result += bucket
        }
    }
    
    return result
}

测试用例:

var nums = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

参考:

• 桶排序百科
• 一像素

考察要点:

• 数组
• 排序