Go 语言算法之美—线性排序
Go 语言算法之美—线性排序
前面的两篇文章分别讲述了基础的排序算法，以及应用更加广泛的 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，排序专题到这篇文章就结束了，期待下一篇！