前置知识：无
基于比较的排序 VS. 不基于比较的排序
- 基于比较的排序：只需要定义好两个对象之间怎么比较即可，很通用
- 不基于比较的排序：不进行比较，对于对象的数据特征有要求，并不通用
计数排序
不基于比较的排序，对于对象的数据特征有要求：数值范围不能太大
如：一个数组中的每个数在 [0, 60) 范围内，对这个数组进行排序
遍历一遍数组，记录每个数值出现的次数，再直接填充即可
package main
import (
"fmt"
"math/rand"
"sort"
)
const (
MIN = 0
MAX = 60
N = 10000
TEST_TIMES = 10000
)
func main() {
for i := 0; i < TEST_TIMES; i++ {
arr := generateArr()
copiedArr := copyArr(arr)
sort.Ints(arr)
countSort(copiedArr)
n := len(arr)
for j := 0; j < n; j++ {
if arr[j] != copiedArr[j] {
panic("error")
}
}
}
fmt.Println("success")
}
func countSort(arr []int) {
counts := [MAX - MIN]int{}
for _, num := range arr {
counts[num]++
}
idx := 0
for num, count := range counts {
for ; count > 0; count-- {
arr[idx] = num
idx++
}
}
}
func generateArr() []int {
n := rand.Intn(N)
arr := make([]int, n)
for i := range arr {
arr[i] = rand.Intn(MAX-MIN) + MIN
}
return arr
}
func copyArr(arr []int) []int {
n := len(arr)
dist := make([]int, n)
copy(dist, arr)
return dist
}- 时间复杂度：
- 空间复杂度：， 为数值范围
计数排序非常简单、非常高效，但是数值范围比较大就不行了
基数排序
不基于比较的排序，对于对象的数据特征有要求：样本是 m 进制的非负整数（这里以 10 进制为例）
元素依次以个位、十位、百位……入桶，十位入桶时，个位已有序，所以十位相同的元素会按从小到大的顺序依次入相同的十位桶
有负数怎么办？所有元素都加同一个数，加成非负数，如果可能溢出，就将 int 改成 uint
两个技巧之一：前缀数量分区
如：有数组 [0, 1, 3, 3, 2, 0, 0, 1]
统计每个数出现的次数：
0: 3 次
1: 2 次
2: 1 次
3: 2 次计算前缀和，含义变成 <= x 的数有几个：
<= 0: 3 个
<= 1: 5 个 (3 + 2)
<= 2: 6 个 (5 + 1)
<= 3: 8 个 (6 + 2)从后往前遍历原数组：
[0, 1, 3, 3, 2, 0, 0, 1]
|
遍历到最后一个1，<= 1 的数有 5 个，所以这个 1 放到第 5 个（索引为 4）
因为这个 1 已经放置好了，所以 <= 1 的数要减一
以此类推，继续往前遍历数组为什么要从后往前遍历？这样能保证 稳定性（最后一个 1 仍然再所有 1 的最后一位）
这个技巧可以很优雅快速地使得某一位（如：个位）置入桶中正确的位置
两个技巧之二：数字提取某一位
有一个数字，如何提取它的个位、十位、百位……？
offset = 1，个位：num / offset % 10，之后 offset *= 10 继续提取接下来的位数
测试链接
代码
package main
import (
"bufio"
"os"
"strconv"
)
const (
MAXN = 501 // 数组最大长度
BASE = 10 // 进制
)
var (
n int
minn int // 数组中的最小值，看看有没有负数，有负数的话需要所有元素都加成非负数
maxx int // 非负数数组中的最大值，用于计算最高是几位
arr = [MAXN]int{}
bucket = [MAXN]int{}
counts = [BASE]int{}
)
func main() {
in := bufio.NewScanner(os.Stdin)
in.Split(bufio.ScanWords)
out := bufio.NewWriterSize(os.Stdout, 4096)
for in.Scan() {
n, _ = strconv.Atoi(in.Text())
if n == 0 {
continue
}
minn = 0
maxx = 0
for i := 0; i < n; i++ {
in.Scan()
arr[i], _ = strconv.Atoi(in.Text())
if arr[i] < minn {
minn = arr[i]
}
if arr[i] > maxx {
maxx = arr[i]
}
}
if minn < 0 { // 有负数
for i := 0; i < n; i++ {
arr[i] -= minn
}
maxx -= minn
}
radixSort(getBitCount(maxx))
out.WriteString(strconv.Itoa(arr[0] - minn))
for i := 1; i < n; i++ {
out.WriteByte(' ')
out.WriteString(strconv.Itoa(arr[i] - minn))
}
out.WriteByte('\n')
}
out.Flush()
}
func radixSort(bitCount int) {
offset := 1
for ; bitCount > 0; bitCount-- {
for i := range counts {
counts[i] = 0
}
for i := 0; i < n; i++ {
counts[arr[i]/offset%BASE]++
}
for i := 1; i < BASE; i++ {
counts[i] += counts[i-1]
}
for i := n - 1; i >= 0; i-- {
counts[arr[i]/offset%BASE]--
bucket[counts[arr[i]/offset%BASE]] = arr[i]
}
copy(arr[:n], bucket[:n])
offset *= BASE
}
}
// 返回 num 在 BASE 进制下有几位
func getBitCount(num int) int {
ans := 0
for num > 0 {
ans++
num /= BASE
}
return ans
}- 时间复杂度：
- 额外空间复杂度：
- 为进制数
- 需要辅助空间做类似桶的作用，来不停的装入、弹出数字
不基于比较的排序总结
一般来讲，计数排序要求，样本是整数，且范围比较窄
一般来讲，基数排序要求，样本是 m 进制的非负整数
如果不符合要求就需要转化，代码里可以设置任何进制来进行基数排序
一旦比较的对象不再是常规数字，那么改写代价的增加是显而易见的，所以不基于比较的排序并不通用