算法基础--桶排序(计数排序,基数排序)

本文只是自己的笔记，并不具备过多的指导意义。

代码的初衷是便于理解，网上大神优化过的代码很多，也不建议在项目中copy本文代码。

---

目录

• 桶排序
• 记数排序
• 基数排序
• 桶排序

---

桶排序

桶排序并不是一个具体的排序，而是一个逻辑概念。

之所以叫桶，是因为他会根据数据状况设计出一个容器，里面每个index将相当于一个桶。
在遍历数据的时候将根据划分将数据一次放入每个桶中，遍历结束后将桶依次倒出。
在每个桶内部，数据会被处理成有序结构。
具体操作可以参考记数排序。

• 桶排序的特点

1. 非基于比较的排序，与被排序的样本的实际数据状况很有关系。
   并不能作为一个通解被应用在普遍场景下，所以实际中并不经常使用。
2. 时间复杂度O(N)，额外空间复杂度O(N)
3. 稳定的排序

---

记数排序

桶排序的具体实现,根据数据状况的最大值开辟一个容器空间

核心在于将数据值转化为键存储在额外开辟的容器空间中。
数据遍历完成，将容器空间的数据填充给原数组。

/// 计数排序
///
/// - Parameters:
///   - arr: 目标数组
///   - max: 最大值
func countingSort(arr : inout [Int] ,max:Int)  {
    var containerArr = [Int](repeating: 0, count: max+1)  //生成长度为最大值的容器数组
    var p = 0
    while p<arr.count {
        containerArr[arr[p]]+=1 //容器数组指定位置计数+1
        p+=1
    }
    p = 0
    var containerP = 0 //容器数组遍历指针
    while containerP<max { //遍历容器数组
        while containerArr[containerP]>0 { //如果容器数组指定位置大于0
            arr[p] = containerP //依次将容器数组的index填充回目标数组
            p+=1
            containerArr[containerP]-=1
        }
        containerP+=1
    }
}

算法的时间复杂度O(N),空间复杂度O(N)，并且稳定

---

基数排序

也是桶排序的一种实现，相比记数排序堆桶的利用更加精致。

具体实现上，从个位数开始，逐位进行排序。由于每次partition都是稳定的，从而保证整体有序。
通俗点来讲，百位相同的数，按照十位排序，十位相同的数按照个位排序。

/// 基数排序
///
/// - Parameters:
///   - arr: 目标数组
///   - maxDigit: 最大位数
func radixSort(arr: inout [Int] ,maxDigit: Int) {
    var mod=10 //取余
    var containerArr = [[Int]](repeating: [Int](repeating: 0, count: 0), count: 9) //创建一个长度为9的二位容器数组
    
    while mod<=kt_pow(a: 10, b: maxDigit) {  //取余位数 小于等于 最大位数 100/10 <=10^2
        var p = 0
        while p < arr.count { //在容器数组中，将原数组以某位的值进行排列
            //获取某位的值
            let bucket = arr[p]%mod/(mod/10)  // 120%100=@20  ==> @20/(100/10) = 2
            containerArr[bucket].append(arr[p])  //加入有序数组的指定位置
            p+=1
        }
        
        p = 0
        while p < arr.count {  //将容器数组中的顺序，回倒给原数组
            for index in 0..<containerArr.count {
                while containerArr[index].count>0 { //将容器数组指定位置的元素依次出队
                    arr[p] = containerArr[index][0] //首位出队
                    containerArr[index].remove(at: 0) //移除首位
                    p+=1
                }
            }
        }
        mod*=10 //对下一位进行排序
    }
}

/// 乘方运算
///
/// - Returns: a^b
func kt_pow(a:Int ,b:Int) -> Int {
    var a=a
    let c=a
    if b == 0 {
        return 1
    }
    
    var i = 1
    while i<b {
        a=a*c
        i+=1
    }

    return a
}

算法的时间复杂度O(N),空间复杂度O(N)，并且稳定

---

桶排序

网上有写了桶排序的，就是通过有限个数的桶，将数据源按区间放入，然后将某个桶内部排序。最后倒出。

感觉在桶内部排序的时候已经需要比较的排序方式了，违背了初衷吧。
有兴趣自己可以看一下
十大经典排序算法（动图演示）

---

参考资料

左神牛课网算法课
十大经典排序算法（动图演示）