项目背景
在实际开发中,我们经常会遇到这样一种排序需求:
file1.txt file2.txt file10.txt file20.txt
如果使用普通的字符串字典序排序,结果会变成:
file1.txt file10.txt file2.txt file20.txt
这是因为字符串比较是逐字符比较的:
- "1" < "2"
- 但 "10" < "2"(因为比较的是字符 '1' 和 '2')
这显然不符合人类直觉。
人类的排序逻辑是:
当遇到连续数字时,应按数值大小比较,而不是逐字符比较。
介绍 Go 语言中实现 Natural Sort 自然排序算法的方法。针对普通字符串字典序排序无法正确处理数字大小(如 file10 排在 file2 前)的问题,提出将字符串拆分为数字段和非数字段进行比较的方案。通过实现 sort.Interface 接口,利用双指针遍历提取数字并转为整数比较,支持前导零处理和版本号排序。代码包含完整实现及测试用例,适用于文件管理、日志编号等场景。
在实际开发中,我们经常会遇到这样一种排序需求:
file1.txt file2.txt file10.txt file20.txt
如果使用普通的字符串字典序排序,结果会变成:
file1.txt file10.txt file2.txt file20.txt
这是因为字符串比较是逐字符比较的:
这显然不符合人类直觉。
人类的排序逻辑是:
当遇到连续数字时,应按数值大小比较,而不是逐字符比较。
这种排序方式被称为:
Natural Sort(自然排序)
它广泛应用于:
在操作系统层面:
Go 标准库并未内置自然排序,因此我们需要自行实现。
本项目目标:
输入:
[]string{ "file1", "file10", "file2", "file20", }
输出:
file1 file2 file10 file20
Go 中:
sort.Strings(arr)
底层是逐字符比较:
缺点:
自然排序的关键:
将字符串拆分为'数字段'和'非数字段'进行比较
例如:
file20.txt
拆分为:
["file", 20, ".txt"]
比较规则:
Go 排序核心接口:
sort.Interface
需要实现:
我们只需实现 Less() 中的自然比较逻辑。
k 为字符串平均长度。
对于两个字符串 a 和 b:
使用:
unicode.IsDigit(rune)
当遇到数字:
例如:
file001 file1
策略:
本实现:
// =============================== // 文件名:main.go // ===============================
package main
import (
"fmt"
"sort"
"strconv"
"unicode"
)
// =============================== // 自然排序结构体定义 // ===============================
// NaturalSort 实现 sort.Interface
type NaturalSort struct {
data []string
}
// Len 返回元素数量
func (n NaturalSort) Len() int {
return len(n.data)
}
// Swap 交换元素
func (n NaturalSort) Swap(i, j int) {
n.data[i], n.data[j] = n.data[j], n.data[i]
}
// Less 核心自然比较逻辑
func (n NaturalSort) Less(i, j int) bool {
return naturalLess(n.data[i], n.data[j])
}
// =============================== // 核心自然比较函数 // ===============================
// naturalLess 比较两个字符串是否 a < b
func naturalLess(a, b string) bool {
i, j := 0, 0
la, lb := len(a), len(b)
for i < la && j < lb {
// 如果当前都是数字
if unicode.IsDigit(rune(a[i])) && unicode.IsDigit(rune(b[j])) {
// 提取完整数字
startI := i
for i < la && unicode.IsDigit(rune(a[i])) {
i++
}
startJ := j
for j < lb && unicode.IsDigit(rune(b[j])) {
j++
}
numA := a[startI:i]
numB := b[startJ:j]
// 转整数比较
intA, _ := strconv.Atoi(numA)
intB, _ := strconv.Atoi(numB)
if intA != intB {
return intA < intB
}
// 数值相同,长度短优先(处理前导零)
if len(numA) != len(numB) {
return len(numA) < len(numB)
}
} else {
// 非数字直接字符比较
if a[i] != b[j] {
return a[i] < b[j]
}
i++
j++
}
}
// 长度短优先
return la < lb
}
// =============================== // 对外排序函数 // ===============================
// NaturalSortStrings 对字符串数组进行自然排序
func NaturalSortStrings(arr []string) {
sort.Sort(NaturalSort{data: arr})
}
// =============================== // 测试代码 // ===============================
func main() {
arr := []string{
"file1.txt",
"file10.txt",
"file2.txt",
"file20.txt",
"file3.txt",
"file001.txt",
"file02.txt",
"file100.txt",
}
fmt.Println("排序前:")
fmt.Println(arr)
NaturalSortStrings(arr)
fmt.Println("\n排序后:")
fmt.Println(arr)
// 版本号测试
versionArr := []string{
"v1.2.10",
"v1.2.2",
"v1.10.1",
"v1.2.1",
}
fmt.Println("\n版本排序前:")
fmt.Println(versionArr)
NaturalSortStrings(versionArr)
fmt.Println("\n版本排序后:")
fmt.Println(versionArr)
}
封装字符串数组,实现 sort.Interface。
返回数组长度。
交换两个元素。
调用核心自然比较函数。
核心算法:
对外暴露排序函数。
测试:
本项目实现了:
优点:
缺点:
正则会增加开销,双指针更高效。
当前使用 strconv.Atoi,受 int 限制。 可以改为:
Go 默认 sort 不是稳定排序。 如需稳定排序:
sort.SliceStable
当前使用 unicode.IsDigit,可支持。
O(n log n * k)
k 为字符串长度。
简化结构体实现。
使用:
sort.SliceStable
对大数据分块排序。
在比较前:
strings.ToLower()
通过本篇文章,你已经掌握:
自然排序是:
文件系统、版本控制、日志分析中的核心排序能力。
掌握它,说明你已经具备工程级算法实现能力。

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online