这是我之前踩坑的真实案例，我使用sort.Slice对切片进行排序，当有多个排序值相等的元素时，排序后这些排序值相等的元素的相对顺序却前后颠倒。

排序之前，排序值相同的张三在王五前面：

{"张三", 85}, {"李四", 90},  {"王五", 85}, ...

排序后，排序值同为 85 的王五却跑到了张三的前面：

{"王五", 85}, {"张三", 85}, {"李四", 90}, ...

排查到这个问题时，我知道我肯定有踩坑了...

在日常开发中，我们经常需要对切片进行排序。Go语言提供了强大的sort包，但是：​为什么排序值相等的元素，它们的相对顺序有时候会发生变化？​​

真实案例

假设我们有一个学生列表，需要按成绩排序：

package main

import (
    "fmt"
    "sort"
)

func main() {
    // 创建长度大于12的切片，其中包含多个年龄相同的人员
    people := []struct {
        Name string
        Age  int
    }{
        {"Alice", 25}, {"Bob", 30}, {"Charlie", 25}, {"David", 35},
        {"Eva", 30}, {"Frank", 25}, {"Grace", 40}, {"Henry", 30},
        {"Ivy", 35}, {"Jack", 25}, {"Kate", 40}, {"Leo", 30},
        {"Mia", 35}, {"Nathan", 25}, {"Olivia", 40}
    }

    fmt.Println("排序前:")
    for i, p := range people {
        fmt.Printf("%d: %s (%d岁)\n", i, p.Name, p.Age)
    }

    // 使用sort.Slice按年龄排序
    sort.Slice(people, func(i, j int) bool {
        return people[i].Age < people[j].Age
    })

    fmt.Println("\n使用sort.Slice排序后:")
    for i, p := range people {
        fmt.Printf("%d: %s (%d岁)\n", i, p.Name, p.Age)
    }
}

运行这段代码，你可能会发现一个有趣的现象：成绩相同的张三、王五和赵六，在排序后的相对顺序并不总是保持不变。

幕后真相

这个现象背后的核心原因是排序算法的稳定性差异。

什么是稳定排序？

稳定排序是指：当两个元素比较结果相等时，排序后它们的相对顺序与排序前保持一致。

举个例子，假设我们有一组学生数据，如果张三排在王五前面，且两人成绩相同，稳定排序后张三仍然会在王五前面。

sort.Slice为什么不稳定？

sort.Slice函数使用的是被称为PDQSort的混合排序算法，它结合了快速排序、插入排序和堆排序的优点。

这种算法在排序过程中可能会交换相等元素的位置，因为它的设计目标主要是最高性能，而不是保持相等元素的原始顺序。

深入理解PDQSort的工作原理

PDQSort算法的工作流程可以简化为：

  1. 判断切片长度，如果很短（≤12）则使用插入排序
  2. 检查分区平衡性，如果多次分区不平衡则转为堆排序
  3. 选择基准点，尝试识别数组是否接近有序
  4. 进行分区操作，这可能导致相等元素位置交换

正是这个分区过程，使得相等元素的相对顺序可能被打乱。

解决方案：使用sort.SliceStable

如果你需要保持相等元素的原始顺序，Go提供了另一个函数：sort.SliceStable。

// 使用稳定排序保持相等元素的原始顺序
sort.SliceStable(students, func(i, j int) bool {
    return students[i].Score > students[j].Score
})

sort.SliceStable采用归并排序算法，它会保证相等元素的相对顺序不变。这意味着无论运行多少次，成绩相同的学生都会保持他们在原始切片中的先后顺序。

实际应用场景

什么时候应该选择稳定排序呢？

  1. 多条件排序：先按次要条件排序，再按主要条件排序
// 先按姓名排序（稳定）
sort.SliceStable(students, func(i, j int) bool {
    return students[i].Name < students[j].Name
})

// 再按成绩排序，姓名顺序保持不变
sort.SliceStable(students, func(i, j int) bool {
    return students[i].Score > students[j].Score
})
  1. 保持业务逻辑顺序：如按提交时间、优先级等
  2. 需要可预测结果的场合

性能考量

当然，稳定性是有代价的。sort.SliceStable通常比sort.Slice稍慢一些，因为在保持顺序的同时需要更多的比较和移动操作。

在大多数应用场景中，这种性能差异可以忽略不计。但如果你排序的数据量非常大，且不关心相等元素的顺序，那么sort.Slice可能是更好的选择。

写在最后

现在终于明白为什么sort.Slice在排序值相等时，元素的相对顺序会发生变化了。这不是bug，而是算法设计的特性。

  • 使用 sort.Slice：当你不关心相等元素的顺序，或追求最高性能时
  • 使用 sort.SliceStable：当需要保持相等元素的原始顺序时

下次遇到排序需求时，不妨先问问自己：我是否需要保持相等元素的原始顺序？ 根据答案选择合适的排序函数，让你的代码行为更加符合预期。