排序算法是计算机科学中的基础算法之一。不同的排序算法有不同的特点和时间复杂度。以下是常见的排序算法，以及每种算法的 Go 实现和时间复杂度分析。
1. 冒泡排序 (Bubble Sort)
原理：从头到尾依次比较相邻的元素，如果顺序错误则交换，直到整个序列有序。
时间复杂度：
- 最优：O(n)
- 平均：O(n²)
- 最差：O(n²)
Go 实现：
go
package main
import "fmt"
func bubbleSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
for j := 0; j < n-i-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j] // 交换
}
}
}
}
func main() {
arr := []int{5, 3, 8, 4, 2}
bubbleSort(arr)
fmt.Println(arr) // 输出: [2 3 4 5 8]
}2. 选择排序 (Selection Sort)
原理：每次遍历未排序部分，选择最小元素并与未排序部分的第一个元素交换，直到所有元素有序。
时间复杂度：
- 最优：O(n²)
- 平均：O(n²)
- 最差：O(n²)
Go 实现：
go
package main
import "fmt"
func selectionSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
minIdx := i
for j := i + 1; j < n; j++ {
if arr[j] < arr[minIdx] {
minIdx = j
}
}
arr[i], arr[minIdx] = arr[minIdx], arr[i] // 交换
}
}
func main() {
arr := []int{5, 3, 8, 4, 2}
selectionSort(arr)
fmt.Println(arr) // 输出: [2 3 4 5 8]
}3. 插入排序 (Insertion Sort)
原理：将当前元素插入到已排序部分的合适位置，直到所有元素都有序。
时间复杂度：
- 最优：O(n)
- 平均：O(n²)
- 最差：O(n²)
Go 实现：
go
package main
import "fmt"
func insertionSort(arr []int) {
n := len(arr)
for i := 1; i < n; i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
func main() {
arr := []int{5, 3, 8, 4, 2}
insertionSort(arr)
fmt.Println(arr) // 输出: [2 3 4 5 8]
}4. 快速排序 (Quick Sort)
原理：选择一个基准元素，将序列分为两部分：一部分小于基准，一部分大于基准。然后递归对这两部分排序。
时间复杂度：
- 最优：O(n log n)
- 平均：O(n log n)
- 最差：O(n²)（当选取的基准元素总是最小或最大时）
Go 实现：
go
package main
import "fmt"
func quickSort(arr []int) {
if len(arr) < 2 {
return
}
pivot := arr[0]
left := 0
right := len(arr) - 1
for left < right {
for left < right && arr[right] >= pivot {
right--
}
arr[left] = arr[right]
for left < right && arr[left] <= pivot {
left++
}
arr[right] = arr[left]
}
arr[left] = pivot
quickSort(arr[:left])
quickSort(arr[left+1:])
}
func main() {
arr := []int{5, 3, 8, 4, 2}
quickSort(arr)
fmt.Println(arr) // 输出: [2 3 4 5 8]
}5. 归并排序 (Merge Sort)
原理：将序列分为两部分，递归排序每部分，然后合并两部分已排序的结果。
时间复杂度：
- 最优：O(n log n)
- 平均：O(n log n)
- 最差：O(n log n)
Go 实现：
go
package main
import "fmt"
func mergeSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
mid := len(arr) / 2
left := mergeSort(arr[:mid])
right := mergeSort(arr[mid:])
return merge(left, right)
}
func merge(left, right []int) []int {
result := []int{}
i, j := 0, 0
for i < len(left) && j < len(right) {
if left[i] < right[j] {
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
result = append(result, left[i:]...)
result = append(result, right[j:]...)
return result
}
func main() {
arr := []int{5, 3, 8, 4, 2}
arr = mergeSort(arr)
fmt.Println(arr) // 输出: [2 3 4 5 8]
}6. 堆排序 (Heap Sort)
原理：构建最大堆，每次将最大元素与堆的最后元素交换，然后调整堆。
时间复杂度：
- 最优：O(n log n)
- 平均：O(n log n)
- 最差：O(n log n)
Go 实现：
go
package main
import (
"fmt"
"container/heap"
)
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } // 大根堆
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func heapSort(arr []int) {
h := &IntHeap{}
heap.Init(h)
for _, v := range arr {
heap.Push(h, v)
}
for i := 0; i < len(arr); i++ {
arr[i] = heap.Pop(h).(int)
}
}
func main() {
arr := []int{5, 3, 8, 4, 2}
heapSort(arr)
fmt.Println(arr) // 输出: [8 5 4 3 2]
}7. 希尔排序 (Shell Sort)
原理：对序列进行分组，分组内使用插入排序，逐渐减少组的大小，直到整个序列有序。
时间复杂度：
- 最优：O(n log n)
- 平均：O(n^(3/2))
- 最差：O(n²)
Go 实现：
go
package main
import "fmt"
func shellSort(arr []int) {
n := len(arr)
gap := n / 2
for gap > 0 {
for i := gap; i < n; i++ {
temp := arr[i]
j := i
for j >= gap && arr[j-gap] > temp {
arr[j] = arr[j-gap]
j -= gap
}
arr[j] = temp
}
gap /= 2
}
}
func main() {
arr := []int{5, 3, 8, 4, 2}
shellSort(arr)
fmt.Println(arr) // 输出: [2 3 4 5 8]
}总结
以下是常见排序算法的时间复杂度总结：
| 排序算法 | 最优复杂度 | 平均复杂度 | 最差复杂度 |
|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) |
| 选择排序 | O(n²) | O(n²) | O(n²) |
| 插入排序 | O(n) | O(n²) | O(n²) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) |
| 希尔排序 | O(n log n) | O(n^(3/2)) | O(n²) |
这些排序算法各有优缺点，选择合适的排序算法要根据数据规模、性能要求以及具体应用场景。