Go 算法实战全景

Go 标准库算法以直白、高效、易于内联为核心哲学：

• 现代标准库 slices / cmp (Go 1.21+)：提供泛型排序、二分查找、有序性判定，无需额外反射。
• 分治与指针交换：通过清晰的切片重划分完成快速排序与原位变换。

---

📊 核心算法与复杂度

算法专题	典型问题 / 算法	核心思想	时间复杂度	空间复杂度
排序	Generic QuickSort / slices.Sort	泛型类型约束 ~int | ~string、双指针分区	$O(n \log n)$	$O(\log n)$
二分查找	slices.BinarySearch	单调切片二分，返回索引与匹配布尔值	$O(\log n)$	$O(1)$
图遍历	BFS / DFS	切片队列 / 递归映射图	$O(V + E)$	$O(V)$

---

1. 泛型排序算法：快速排序 (QuickSort)

利用类型约束 [T ~int | ~string | ~float64] 实现通用原地快速排序，并配合 slices.IsSorted 验证：

package main

import (
	"fmt"
	"slices"
)

func QuickSort[T ~int | ~string | ~float64](arr []T) {
	if len(arr) <= 1 {
		return
	}
	pivot := arr[len(arr)-1]
	i := 0
	for j := 0; j < len(arr)-1; j++ {
		if arr[j] <= pivot {
			arr[i], arr[j] = arr[j], arr[i]
			i++
		}
	}
	arr[i], arr[len(arr)-1] = arr[len(arr)-1], arr[i]
	QuickSort(arr[:i])
	QuickSort(arr[i+1:])
}

func main() {
	fmt.Println("=== Go Generic QuickSort & slices.Sort ===")
	data := []int{64, 25, 12, 22, 11}
	QuickSort(data)

	if !slices.IsSorted(data) {
		panic("Not sorted")
	}
	fmt.Printf("Sorted: %v\n", data)
	fmt.Println("Go QuickSort tests passed successfully.")
}

🐳 Docker Verified📋golang:1.22-alpine

Exit Code: 0

=== Go Generic QuickSort & slices.Sort ===
Sorted: [11 12 22 25 64]
Go QuickSort tests passed successfully.