对比排序和非对比排序

排序
├── 比较排序(下界 O(n log n))
│   ├── O(n²):  冒泡 / 选择 / 插入
│   └── O(nlogn):快排 / 归并 / 堆排
└── 非比较排序(可到 O(n),有前提)
    └── 计数 / 桶 / 基数

func bubbleSort(a []int) {
    n := len(a)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-1-i; j++ {
            if a[j] > a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
                swapped = true
            }
        }
        if !swapped { // 一趟没交换,说明已经有序,提前退出,节省时间
            break
        }
    }
}

func selectionSort(a []int) {
    n := len(a)
    for i := 0; i < n-1; i++ {
        min := i
        for j := i + 1; j < n; j++ {
            if a[j] < a[min] {
                min = j
            }
        }
        a[i], a[min] = a[min], a[i]
    }
}

// Example:
// 将整个数组分为 已排序 | 乱序 两个分区
// [2 5 8]| 3      取 3,往左挪:8>3、5>3、2<3 → 停
// [2 3 5 8]        3 插到 2 和 5 之间

func insertionSort(a []int) {
    for i := 1; i < len(a); i++ { // i 从1开始
        key := a[i]
        j := i - 1
        for j >= 0 && a[j] > key { // 比 key 大的整体右移一格
            a[j+1] = a[j]
            j--
        }
        a[j+1] = key
    }
}

// Example:
// 选 pivot=5
// [3 8 1 5 7 2]
// partition 后: [3 1 2] 5 [8 7]    5 已归位
//               ↓递归      ↓递归

func quickSort(a []int, low, hi int) {
    if low >= hi {
        return
    }
    p := partition(a, low, hi) // p 是 pivot 归位后的下标
    quickSort(a, low, p-1)
    quickSort(a, p+1, hi)
}

func partition(a []int, low, hi int) int { // 拿 a[hi] 当 pivot,把它放到最终位置并返回该下标
    pivot := a[hi]
    i := low // i 指向"小于区"的下一个位置
    for j := low; j < hi; j++ {
        if a[j] < pivot {
            a[i], a[j] = a[j], a[i]
            i++
        }
    }
    a[i], a[hi] = a[hi], a[i] // pivot 归位:左边全小于它,右边全不小于它
    return i
}

// Example
//        [5 3 8 1 2 7]
//        /           \
//   [5 3 8]         [1 2 7]      递归切分
//   ...              ...
//   [3 5 8]         [1 2 7]      触底后逐层 merge
//        \           /
//        [1 2 3 5 7 8]           双指针合并两个有序段

func mergeSort(a []int) []int {
    if len(a) <= 1 {
        return a
    }
    mid := len(a) / 2
    left := mergeSort(a[:mid])
    right := mergeSort(a[mid:])
    return merge(left, right)
}

func merge(l, r []int) []int {
    res := make([]int, 0, len(l)+len(r))
    i, j := 0, 0
    for i < len(l) && j < len(r) {
        if l[i] <= r[j] { // <= 是稳定的关键:相等时先取左边
            res = append(res, l[i])
            i++
        } else {
            res = append(res, r[j])
            j++
        }
    }
    res = append(res, l[i:]...)
    res = append(res, r[j:]...)
    return res
}

// Example
// 1. build max-heap:     [8 5 7 1 3 2]  堆顶=8 最大
// 2. 堆顶↔末尾,size--:    [2 5 7 1 3|8]  8 归位,再 sift-down 修复前 5 个
// 3. 重复...最终整体有序

func heapSort(a []int) {
    n := len(a)
    // 建堆:从最后一个非叶子节点开始下沉
    for i := n/2 - 1; i >= 0; i-- {
        siftDown(a, i, n)
    }
    // 反复取堆顶
    for end := n - 1; end > 0; end-- {
        a[0], a[end] = a[end], a[0] // 最大值扔到末尾
        siftDown(a, 0, end)         // 修复 [0, end)
    }
}

func siftDown(a []int, i, n int) {
    for {
        l, r, largest := 2*i+1, 2*i+2, i
        if l < n && a[l] > a[largest] {
            largest = l
        }
        if r < n && a[r] > a[largest] {
            largest = r
        }
        if largest == i {
            return
        }
        a[i], a[largest] = a[largest], a[i]
        i = largest
    }
}

原始(按到达顺序): (A,3) (B,1) (C,3) (D,1)
按第二个字段排序:
稳定结果:   (B,1) (D,1) (A,3) (C,3)   ← 1 里 B 仍在 D 前,3 里 A 仍在 C 前
不稳定结果: (D,1) (B,1) (C,3) (A,3)   ← 相等元素顺序被打乱了

2^h ≥ n!  →  h ≥ log2(n!)  ≈  n·log n   (斯特林公式)

// Example
// 数据: [2 5 2 1 5]   值域 0..5
// 计数: cnt[1]=1 cnt[2]=2 cnt[5]=2
// 摊开: 1,2,2,5,5

按个位排 → 按十位排 → 按百位排 ...   每趟必须用稳定排序

func radixSort(a []int) { // 非负整数
	if len(a) == 0 {
		return
	}
	max := slices.Max(a)
	buf := make([]int, len(a))
	for exp := 1; max/exp > 0; exp *= 10 { // 依次按个位、十位、百位……
		var cnt [10]int
		for _, v := range a {
			cnt[v/exp%10]++ // 只看当前这一位是数字几
		}
		for d := 1; d < 10; d++ {
			cnt[d] += cnt[d-1] // 前缀和:cnt[d] = 这一位 ≤ d 的元素个数,
		}                      // 也就是数字 d 那一段在结果里的右边界
		for i := len(a) - 1; i >= 0; i-- { // 从后往前搬 → 相等的保持原顺序(稳定)
			d := a[i] / exp % 10
			cnt[d]--
			buf[cnt[d]] = a[i]
		}
		copy(a, buf) // 这一位排完,进入下一位
	}
}

import (
    "sort"
    "slices" // Go 1.21+
)

// 1. sort.Interface:老派,自定义类型实现 Len/Less/Swap
type ByAge []Person
func (p ByAge) Len() int           { return len(p) }
func (p ByAge) Less(i, j int) bool { return p[i].Age < p[j].Age }
func (p ByAge) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
sort.Sort(ByAge(people))

// 2. sort.Slice:传比较闭包,不用定义类型,最常用
sort.Slice(people, func(i, j int) bool {
    return people[i].Age < people[j].Age
})

// 3. slices.Sort / SortFunc:Go 1.21+ 泛型,首选
slices.Sort(unsortArray)                        // 基础类型,直接排
slices.SortFunc(people, func(a, b Person) int {
    return cmp.Compare(a.Age, b.Age)     // 返回 <0 / 0 / >0
})

pdqsort 的缝合逻辑:
① 默认走快排(平均最快、缓存友好)
② 子区间长度 ≤ 12  → 切回插入排序
③ 递归深度超过阈值(约 2*log n,快排要退化了)→ 切堆排(保证最坏也是 O(n log n))
④ pivot 用近似中位数,并检测"已经有序/近乎有序"的模式直接短路
⑤ 对大量重复元素做三路处理,避免在相等元素上白干

sort.Stable(ByAge(people))
sort.SliceStable(people, func(i, j int) bool { return ... })
slices.SortStableFunc(people, func(a, b Person) int { return ... }) // 1.21+

sort.Ints(a); sort.Strings(s); sort.Float64s(f) // 老式便捷函数
slices.SortFunc(...)                            // 新式泛型,优先用
i, found := slices.BinarySearch(sortedNums, x)  // 排好序后二分查找
slices.IsSorted(nums)                           // 判断是否已有序
sort.Search(n, func(i int) bool { ... })        // 通用二分,找满足条件的最小下标