前面的两篇文章分别讲述了基础的排序算法,以及应用更加广泛的 O(nlogn) 的排序算法,今天再来看看几种特殊的线性排序算法,之所以叫线性,是因为他们的主要思想都不是基于数据比较,而且时间复杂度接近 O(n)。
桶排序的原理理解起来很简单,首先根据要排序的数据的最大和最小值,划分若干个区间,假设排序数据中的最小值是 1 ,最大值是 25,那么可以划分为 5 个区间,每个区间分别是 0-5,5-10,10-15,15-20,20-25
。
每个数据区间,一般叫做“桶”,然后可以将数据划分到各个桶内,如下:
划分完成之后,在桶内部分别进行排序(可以选择复杂度为 O(nlogn) 的排序算法),然后再依次将数据从桶内取出,这样整个数据就是有序的了。
桶排序看似简单,但应用场景并不是很多,因为它对于数据的要求比较苛刻,必须能够将数据尽量均匀的分到各个桶中,如果分布不均,那么时间复杂度会受到影响,在极端情况下,如果数据只分到了一个桶内,那么就退化成 O(nlogn) 的复杂度了。
桶排序的一个简单代码示例如下:
// 桶数量,可调整
const bucketNum = 10
// 桶排序
func BucketSort(data []int) {
if len(data) == 0 {
return
}
// 寻找到最大值和最小值
min, max := math.MaxInt32, math.MinInt32
for _, v := range data {
if v < min {
min = v
}
if v > max {
max = v
}
}
// 这里可能有整数溢出,根据实际情况再进行调整
if min < 0 {
for i := range data {
data[i] += -min
}
max += -min
}
if max == 0 {
return
}
// 新建桶并进行划分
threshold := max / bucketNum
if max%bucketNum != 0 {
threshold += 1
}
var buckets [bucketNum + 1][]int
for _, v := range data {
buckets[v/threshold] = append(buckets[v/threshold], v)
}
// 桶内排序并拷贝回原数组
var k int
for i := 0; i < bucketNum + 1; i++ {
sort.Ints(buckets[i])
for _, v := range buckets[i] {
if min < 0 {
v += min
}
data[k] = v
k++
}
}
}
计数排序可以理解为桶排序的一种特殊情况,例如针对数据最大值并不是很大的情况,假如数据 4 2 2 8 3 3 1
最大值是 8,那么可以直接划分 8 个桶,将数据直接划分到对应的桶内,每个桶内的数据都是一样的,因此桶内数据并不需要排序。
可以参考下图来理解计数排序:
我再以一个简单的例子来讲解下计数排序的代码实现,假如有数据 4 2 2 8 3 3 1
最大值 max 为 8。
新建一个计数数组 count,count 大小为 max + 1,count 存储的是原数组每个值出现的次数,如下:
然后将 count 数组的值进行逐项累加,得到下面的结果:
最后进行最关键的一步,新建一个临时数组 output,遍历原数组,取出值做为 count 数组的下标,然后取出对应的 count 数组的值,将其减 1 做为临时数组的下标,原数组的值就存储在这个位置。
可以通过下面的图进行理解:
理解了这个之后,代码就会比较简单了:
// 计数排序
func CountingSort(data []int) {
if len(data) <= 1 {
return
}
// 寻找最大值
max := data[0]
for _, v := range data {
if max < v {
max = v
}
}
// 记录数值出现次数
count := make([]int, max+1)
for _, v := range data {
count[v]++
}
// count数组累加
for i := 1; i < len(count); i++ {
count[i] += count[i-1]
}
temp := make([]int, len(data))
for _, v := range data {
temp[count[v]-1] = v
count[v]--
}
copy(data[:], temp[:])
}
基数排序比较适用于数值较大或者字符串排序的场景,比如要针对一批手机号进行排序,手机号有 11 位,数值较大,不太适合使用桶排序或者计数排序。
而基数排序就比较适用于这种场景。
手机号码太长,举个简单的例子,假设有数据 121, 432, 564, 23, 1, 45, 788
进行排序,首先取这些数字的个位分别进行排序比较,然后取十位进行比较,因为这些数字最大的就到百位,所以比较到百位就结束了。如下图:
一个简单的代码演示如下:
// 基数排序(只适用于整数)
func RadixSort(data []int) {
if len(data) <= 1 {
return
}
// 找到数组中最大值
max := data[0]
for _, v := range data {
if max < v {
max = v
}
}
buckets := make([][]int, 10)
mod := 1
for ; max > 0; max /= 10 {
for _, v := range data {
buckets[(v/mod)%10] = append(buckets[(v/mod)%10], v)
}
count := 0
for i, buc := range buckets {
for _, v := range buc {
data[count] = v
count++
}
buckets[i] = []int{}
}
mod *= 10
}
}
完整代码示例在我的 Github 上可进行查看:https://github.com/roseduan/Go-Algorithm,排序专题到这篇文章就结束了,期待下一篇!
本文分享自 roseduan写字的地方 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!