用 Go 语言实现插入排序、希尔排序、冒泡排序、堆排序、选择排序、快速排序、归并排序算法，并注释说明时间复杂度及原理。

说明

• 下文函数均对切片 原地排序（归并排序内部使用临时数组）。
• 时间复杂度默认指 最坏情况；如有差异会另行标注。
• O(nlogn) 表示 (O(n\log n))，O(n^2) 表示 (O(n^2))。

---

1. 插入排序（Insertion Sort）

// 时间复杂度：平均 / 最坏 O(n^2)，最好 O(n)（已基本有序时）
// 空间复杂度：O(1)
// 稳定性：稳定
// 原理：构建有序序列；对待排序元素，在已排序部分从后向前扫描，找到合适位置插入。
func InsertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		for j := i; j > 0; j-- {
			if arr[j] < arr[j-1] {
				arr[j], arr[j-1] = arr[j-1], arr[j]
			} else {
				break // 前面已有序，可提前结束
			}
		}
	}
}

---

2. 希尔排序（Shell Sort）

// 时间复杂度：与增量序列有关；Knuth 增量下约为 O(n^{3/2})，实践中常优于 O(n^2) 的简单排序
// 空间复杂度：O(1)
// 稳定性：不稳定
// 原理：按一定增量将记录分组，对每组做插入排序；增量逐步减小，直至增量为 1 时对整组做插入排序并结束。
func ShellSort(arr []int) {
	n := len(arr)
	h := 1
	// Knuth 增量序列：1, 4, 13, 40, ...
	for h < n/3 {
		h = 3*h + 1
	}
	for h >= 1 {
		for i := h; i < n; i++ {
			for j := i; j >= h && arr[j] < arr[j-h]; j -= h {
				arr[j], arr[j-h] = arr[j-h], arr[j]
			}
		}
		h /= 3
	}
}

---

3. 冒泡排序（Bubble Sort）

// 时间复杂度：平均 / 最坏 O(n^2)，最好 O(n)（加入提前退出标志时）
// 空间复杂度：O(1)
// 稳定性：稳定
// 原理：反复遍历待排序列，比较相邻元素，若顺序错误则交换，较大（或较小）元素逐步“冒泡”到一端。
func BubbleSort(arr []int) {
	n := len(arr)
	for i := 0; i < n; i++ {
		swapped := false
		for j := 0; j < n-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				swapped = true
			}
		}
		if !swapped {
			break // 本轮无交换，说明已有序
		}
	}
}

---

4. 堆排序（Heap Sort）

// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
// 稳定性：不稳定
// 原理：树形选择排序。将序列调整为大顶堆后，反复将堆顶与末尾交换并缩小堆，再下沉调整，直至有序。
// 堆定义（1-based 下标）：对 i = 1..n/2，满足 hi ≥ h(2i) 且 hi ≥ h(2i+1)（大顶堆），
// 或 hi ≤ h(2i) 且 hi ≤ h(2i+1)（小顶堆）。Go 中常用 0-based：左子 i*2+1，右子 i*2+2。
func HeapSort(arr []int) {
	n := len(arr)
	// 构建大顶堆
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, i, n)
	}
	// 依次将堆顶放到末尾
	for i := n - 1; i > 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		heapify(arr, 0, i)
	}
}

// heapify：从下标 i 开始向下调整，使以 i 为根的子树满足大顶堆（范围 [0, n)）
func heapify(arr []int, i, n int) {
	for {
		maxPos := i
		left, right := i*2+1, i*2+2
		if left < n && arr[left] > arr[maxPos] {
			maxPos = left
		}
		if right < n && arr[right] > arr[maxPos] {
			maxPos = right
		}
		if maxPos == i {
			break
		}
		arr[i], arr[maxPos] = arr[maxPos], arr[i]
		i = maxPos
	}
}

---

5. 选择排序（Selection Sort）

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
// 稳定性：不稳定
// 原理：每一趟从待排序区间选出最小（或最大）元素，放到区间起始位置，直到全部排完。
func SelectionSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		minIndex := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		arr[i], arr[minIndex] = arr[minIndex], arr[i]
	}
}

---

6. 快速排序（Quick Sort）

// 时间复杂度：平均 O(nlogn)，最坏 O(n^2)（如已有序且枢轴选得不好）
// 空间复杂度：平均 O(logn)（递归栈），最坏 O(n)
// 稳定性：不稳定
// 原理：分治。一趟划分将序列分成两部分，左侧均不大于枢轴、右侧均不小于枢轴，再对左右两侧递归快速排序。
func QuickSort(arr []int) {
	if len(arr) == 0 {
		return
	}
	quickSort(arr, 0, len(arr)-1)
}

func quickSort(arr []int, left, right int) {
	if left < right {
		pivot := partition(arr, left, right)
		quickSort(arr, left, pivot-1)
		quickSort(arr, pivot+1, right)
	}
}

// partition：以最右侧元素为枢轴，返回枢轴最终下标
func partition(arr []int, left, right int) int {
	pivot := arr[right]
	i := left
	for j := left; j < right; j++ {
		if arr[j] < pivot {
			arr[i], arr[j] = arr[j], arr[i]
			i++
		}
	}
	arr[i], arr[right] = arr[right], arr[i]
	return i
}

---

7. 归并排序（Merge Sort）

// 时间复杂度：O(nlogn)（最好 / 平均 / 最坏）
// 空间复杂度：O(n)
// 稳定性：稳定
// 原理：分治。先递归使左右子序列有序，再将两个有序子序列合并（2-路归并）得到整体有序序列。
func MergeSort(arr []int) {
	if len(arr) == 0 {
		return
	}
	mergeSort(arr, 0, len(arr)-1)
}

func mergeSort(arr []int, left, right int) {
	if left < right {
		mid := left + (right-left)/2 // 避免 left+right 溢出
		mergeSort(arr, left, mid)
		mergeSort(arr, mid+1, right)
		merge(arr, left, mid, right)
	}
}

func merge(arr []int, left, mid, right int) {
	tmp := make([]int, right-left+1)
	i, j, k := left, mid+1, 0
	for i <= mid && j <= right {
		if arr[i] <= arr[j] { // <= 保证稳定性
			tmp[k] = arr[i]
			i++
		} else {
			tmp[k] = arr[j]
			j++
		}
		k++
	}
	for i <= mid {
		tmp[k] = arr[i]
		i++
		k++
	}
	for j <= right {
		tmp[k] = arr[j]
		j++
		k++
	}
	copy(arr[left:right+1], tmp)
}

---

复杂度与特性对照

算法	平均时间	最坏时间	空间	稳定性
插入排序	(O(n^2))	(O(n^2))	(O(1))	稳定
希尔排序	取决于增量	取决于增量	(O(1))	不稳定
冒泡排序	(O(n^2))	(O(n^2))	(O(1))	稳定
堆排序	(O(n\log n))	(O(n\log n))	(O(1))	不稳定
选择排序	(O(n^2))	(O(n^2))	(O(1))	不稳定
快速排序	(O(n\log n))	(O(n^2))	(O(\log n))	不稳定
归并排序	(O(n\log n))	(O(n\log n))	(O(n))	稳定

---

简单调用示例

package main

import "fmt"

func main() {
	data := []int{5, 2, 9, 1, 5, 6}
	arr := append([]int(nil), data...) // 复制一份，避免互相影响

	InsertionSort(arr)
	fmt.Println("插入排序:", arr)

	arr = append([]int(nil), data...)
	QuickSort(arr)
	fmt.Println("快速排序:", arr)
}

可将上述各排序函数放在同一 package 中，按需调用。