算法基础--桶排序(计数排序,基数排序)
2018-11-23 本文已影响23人
kirito_song
本文只是自己的笔记，并不具备过多的指导意义。
代码的初衷是便于理解，网上大神优化过的代码很多，也不建议在项目中copy本文代码。
目录
- 桶排序
- 记数排序
- 基数排序
- 桶排序
桶排序
桶排序并不是一个具体的排序，而是一个逻辑概念。
之所以叫桶，是因为他会根据数据状况设计出一个容器，里面每个index将相当于一个桶。
在遍历数据的时候将根据划分将数据一次放入每个桶中，遍历结束后将桶依次倒出。
在每个桶内部，数据会被处理成有序结构。
具体操作可以参考记数排序。
-
桶排序的特点
- 非基于比较的排序，与被排序的样本的实际数据状况很有关系。
并不能作为一个通解被应用在普遍场景下，所以实际中并不经常使用。 - 时间复杂度O(N)，额外空间复杂度O(N)
- 稳定的排序
记数排序
桶排序的具体实现,根据数据状况的最大值开辟一个容器空间
核心在于将数据值转化为键存储在额外开辟的容器空间中。
数据遍历完成，将容器空间的数据填充给原数组。
/// 计数排序
///
/// - 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)，并且稳定
桶排序
网上有写了桶排序的，就是通过有限个数的桶，将数据源按区间放入，然后将某个桶内部排序。最后倒出。
感觉在桶内部排序的时候已经需要比较的排序方式了，违背了初衷吧。
有兴趣自己可以看一下
十大经典排序算法（动图演示）
