Go 语言实现 Natural Sort 自然排序算法源码

k 为字符串平均长度。

实现思路

整体思路

对于两个字符串 a 和 b：

1. 使用双指针 i, j 遍历
2. 如果当前位置都是数字：
   • 提取完整数字
   • 转为整数
   • 数值比较
3. 如果当前位置不是数字：
   • 逐字符比较
4. 如果完全相同：
   • 长度短的优先

关键点分析

1. 如何识别数字段？

使用：

unicode.IsDigit(rune)

2. 如何提取完整数字？

当遇到数字：

• 记录起始位置
• 直到不是数字为止

3. 如何处理前导零？

例如：

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)
}

代码详细解读

NaturalSort 结构体

封装字符串数组，实现 sort.Interface。

Len

返回数组长度。

Swap

交换两个元素。

Less

调用核心自然比较函数。

naturalLess

核心算法：

1. 双指针遍历两个字符串
2. 如果是数字：
   • 提取完整数字
   • 转整数比较
3. 如果不是数字：
   • 直接字符比较
4. 全部相同：
   • 长度短优先

NaturalSortStrings

对外暴露排序函数。

main

测试：

• 文件名排序
• 版本号排序

项目总结

本项目实现了：

• Go 语言自然排序
• 支持多数字段
• 支持版本号排序
• 支持前导零
• 兼容 sort.Interface

优点：

• 符合人类直觉
• 可扩展
• 易集成

缺点：

• 性能略低于纯字符串排序
• 需要解析数字

常见问题及解答

Q1：为什么不用正则？

正则会增加开销，双指针更高效。

Q2：支持大整数吗？

当前使用 strconv.Atoi，受 int 限制。 可以改为：

• big.Int
• 字符串长度优先比较

Q3：是否稳定？

Go 默认 sort 不是稳定排序。 如需稳定排序：

sort.SliceStable

Q4：支持 Unicode 数字吗？

当前使用 unicode.IsDigit，可支持。

Q5：时间复杂度？

O(n log n * k)

k 为字符串长度。

扩展方向与性能优化

1. 使用 sort.Slice

简化结构体实现。

2. 使用 big.Int 支持超大整数

3. 实现稳定版本

使用：

sort.SliceStable

4. 并发排序

对大数据分块排序。

5. 忽略大小写版本

在比较前：

strings.ToLower()

结语

通过本篇文章，你已经掌握：

• 自然排序原理
• Go 排序接口机制
• 数字段解析技巧
• 版本号排序实现
• 工程级排序扩展能力

自然排序是：

文件系统、版本控制、日志分析中的核心排序能力。

掌握它，说明你已经具备工程级算法实现能力。