Go 语言：字符串排序详解

🔹 核心三步：字符串排序的标准流程

1
2
3
4
5
6
7
8
9
10
11
str := "eat"

//  第一步：字符串 → 字节切片（因为 string 不可修改）
s := []byte(str)           // ['e', 'a', 't']

//  第二步：对字节切片排序
sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
                           // ['a', 'e', 't']

//  第三步：字节切片 → 字符串
sortedStr := string(s)     // "aet"

🔹 为什么要转 []byte？

因为 Go 的 string 是不可变的，不能原地修改：

1
2
str := "eat"
str[0] = 'x'    // ❌ 编译错误：cannot assign to str[0]
类型 可变性 是否可排序
string ❌ 不可变 ❌ 不能原地排序
[]byte ✅ 可变 ✅ 可原地排序

💡 必须先转成 []byte（可修改），排完再转回 string。

🔹 sort.Slice 工作原理

参考链接

1
2
3
sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
//         ↑           ↑
//      要排序的切片   比较函数：s[i] < s[j] 表示升序

🔸 比较的是 ASCII 码值

byte 本质是 uint8，比较的是字符的 ASCII 码：

1
2
字符  'a'   'e'   't'
ASCII  97   101   116
1
2
排序前: ['e', 'a', 't']  → [101, 97, 116]
排序后: ['a', 'e', 't']  → [97, 101, 116]   ✅ 升序排列

🔸 常用比较函数写法

1
2
3
4
5
6
7
8
9
10
// 升序（小 → 大）
sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })

// 降序（大 → 小）
sort.Slice(s, func(i, j int) bool { return s[i] > s[j] })

// 按字母顺序（忽略大小写）
sort.Slice(s, func(i, j int) bool { 
    return strings.ToLower(string(s[i])) < strings.ToLower(string(s[j])) 
})

🔹 在算法中的应用：字母异位词分组

🎯 核心思想

字母异位词排序后得到相同的字符串，可以作为 map 的 key 来分组。

1
2
3
4
5
6
7
8
9
"eat"  → 排序 → "aet"  ┐
"tea"  → 排序 → "aet"  ├→ 同一组
"ate"  → 排序 → "aet"  ┘

"tan"  → 排序 → "ant"  ┐
"nat"  → 排序 → "ant"  ├→ 同一组
                        ┘

"bat"  → 排序 → "abt"  → 单独一组

🗂️ Map 分组状态

1
2
3
4
5
map[string][]string{
    "aet": {"eat", "tea", "ate"},
    "ant": {"tan", "nat"},
    "abt": {"bat"},
}

🔹 完整流程图解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]

遍历每个字符串：
┌─────────────────────────────────────────┐
│ "eat" → []byte → 排序 → "aet"          │
│         mp["aet"] = ["eat"]             │
├─────────────────────────────────────────┤
│ "tea" → []byte → 排序 → "aet"          │
│         mp["aet"] = ["eat", "tea"]      │
├─────────────────────────────────────────┤
│ "tan" → []byte → 排序 → "ant"          │
│         mp["ant"] = ["tan"]             │
├─────────────────────────────────────────┤
│ "ate" → []byte → 排序 → "aet"          │
│         mp["aet"] = ["eat", "tea", "ate"]│
├─────────────────────────────────────────┤
│ "nat" → []byte → 排序 → "ant"          │
│         mp["ant"] = ["tan", "nat"]      │
├─────────────────────────────────────────┤
│ "bat" → []byte → 排序 → "abt"          │
│         mp["abt"] = ["bat"]             │
└─────────────────────────────────────────┘

收集 map 的所有 value：
输出: [["eat","tea","ate"], ["tan","nat"], ["bat"]]

🔹 完整代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func groupAnagrams(strs []string) [][]string {
    mp := make(map[string][]string)
    
    for _, str := range strs {
        // 1. string → []byte
        s := []byte(str)
        
        // 2. 排序
        sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
        
        // 3. []byte → string（作为 key）
        key := string(s)
        
        // 4. 分组
        mp[key] = append(mp[key], str)
    }
    
    // 收集结果
    result := make([][]string, 0, len(mp))
    for _, group := range mp {
        result = append(result, group)
    }
    return result
}

🔹 小结：关键步骤与原因

步骤 代码 原因
转字节切片 []byte(str) string 不可变，转成可修改的 []byte
排序 sort.Slice(s, ...) 按 ASCII 码升序排列字节，异位词排序后相同
转回字符串 string(s) 排完序转回 string，作为 map 的 key
分组 mp[key] = append(...) 相同 key 的字符串归为一组

整体思路：异位词排序后相同 → 用排序结果做 key 分组 → 一次遍历完成分类

🔹 进阶技巧

✅ 预分配容量（提升性能）

1
2
3
4
5
// 如果知道大概的分组数量，预分配 map 容量
mp := make(map[string][]string, len(strs)/2)

// 如果知道每组大概大小，预分配 slice 容量
mp[key] = append(mp[key], str)  // Go 会自动扩容，但预分配更高效

✅ 使用 sort.Strings 排序字符串切片

如果需要对多个字符串整体排序（而非单个字符串内部）：

1
2
words := []string{"banana", "apple", "cherry"}
sort.Strings(words)  // ["apple", "banana", "cherry"]

✅ 处理 Unicode 字符

[]byte 只适合 ASCII 字符，处理中文等多字节字符需用 []rune：

1
2
3
4
5
6
str := "你好世界"

// ✅ 正确：转成 rune 切片（每个 rune 是一个 Unicode 码点）
runes := []rune(str)
sort.Slice(runes, func(i, j int) bool { return runes[i] < runes[j] })
sorted := string(runes)
类型 适用场景 注意事项
[]byte ASCII / 英文 每个元素 1 字节，效率高
[]rune Unicode / 中文 每个元素 4 字节，支持多语言

🔑 关键要点速记

要点 说明
string 不可变 必须先转 []byte 或 []rune 才能排序
sort.Slice 通用排序函数，需传入比较函数
比较的是码值 byte 比较 ASCII，rune 比较 Unicode 码点
异位词分组 排序后相同 → 可作为 map key 聚合
转回 string string(s) 会拷贝底层数据，生成新字符串
Unicode 支持 中文等多字节字符需用 []rune

📌 一句话总结：字符串排序的本质是”转切片→排序→转回”，理解 string 的不可变性和 sort.Slice 的比较机制，是处理字母异位词等字符串算法题的关键。