以下是几种常见排序算法的 Go 实现以及它们的时间复杂度。

一、冒泡排序

 (Bubble Sort)

package main

import "fmt"

// BubbleSort implements the bubble sort algorithm
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, 2, 9, 1, 5, 6}
    BubbleSort(arr)
    fmt.Println("Sorted array:", arr)
}

时间复杂度：

• 平均：O(n^2)

• 最坏：O(n^2)

• 最好：O(n)（当数组已经有序时）

稳定性：稳定

二、选择排序

 (Selection Sort)

package main

import "fmt"

// SelectionSort implements the selection sort algorithm
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{29, 10, 14, 37, 14}
    SelectionSort(arr)
    fmt.Println("Sorted array:", arr)
}

时间复杂度：

• 平均：O(n^2)

• 最坏：O(n^2)

• 最好：O(n^2)

稳定性：不稳定

三、插入排序

 (Insertion Sort)

package main

import "fmt"

// InsertionSort implements the insertion sort algorithm
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{12, 11, 13, 5, 6}
    InsertionSort(arr)
    fmt.Println("Sorted array:", arr)
}

时间复杂度：

• 平均：O(n^2)

• 最坏：O(n^2)

• 最好：O(n)（当数组已经有序时）

稳定性：稳定

四、归并排序

(Merge Sort)

package main

import "fmt"

// MergeSort implements the merge sort algorithm
func MergeSort(arr []int) []int {
    if len(arr) < 2 {
        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{12, 11, 13, 5, 6, 7}
    sortedArr := MergeSort(arr)
    fmt.Println("Sorted array:", sortedArr)
}

时间复杂度：

• 平均：O(n log n)

• 最坏：O(n log n)

• 最好：O(n log n)

稳定性：稳定

五、快速排序

 (Quick Sort)

package main

import "fmt"

// QuickSort implements the quick sort algorithm
func QuickSort(arr []int) {
    if len(arr) < 2 {
        return
    }
    left, right := 0, len(arr)-1
    pivot := arr[len(arr)/2]
    for left <= right {
        for arr[left] < pivot {
            left++
        }
        for arr[right] > pivot {
            right--
        }
        if left <= right {
            arr[left], arr[right] = arr[right], arr[left]
            left++
            right--
        }
    }
    QuickSort(arr[:right+1])
    QuickSort(arr[left:])
}

func main() {
    arr := []int{10, 7, 8, 9, 1, 5}
    QuickSort(arr)
    fmt.Println("Sorted array:", arr)
}

时间复杂度：

• 平均：O(n log n)

• 最坏：O(n^2)（当数组已经有序时）

• 最好：O(n log n)

稳定性：不稳定

六、堆排序

 (Heap Sort)

package main

import "fmt"

// HeapSort implements the heap sort algorithm
func HeapSort(arr []int) {
    n := len(arr)
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
    for i := n - 1; i >= 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
}

func heapify(arr []int, n, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    if left < n && arr[left] > arr[largest] {
        largest = left
    }

    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

func main() {
    arr := []int{12, 11, 13, 5, 6, 7}
    HeapSort(arr)
    fmt.Println("Sorted array:", arr)
}

时间复杂度：

• 平均：O(n log n)

• 最坏：O(n log n)

• 最好：O(n log n)

稳定性：不稳定

七、计数排序

 (Counting Sort)

package main

import "fmt"

// CountingSort implements the counting sort algorithm
func CountingSort(arr []int, max int) []int {
    count := make([]int, max+1)
    for _, num := range arr {
        count[num]++
    }
    idx := 0
    for num, c := range count {
        for c > 0 {
            arr[idx] = num
            idx++
            c--
        }
    }
    return arr
}

func main() {
    arr := []int{4, 2, 2, 8, 3, 3, 1}
    sortedArr := CountingSort(arr, 8)
    fmt.Println("Sorted array:", sortedArr)
}

时间复杂度：

• 平均：O(n + k)（k 是元素的范围）

• 最坏：O(n + k)
  

• 最好：O(n + k)

稳定性：稳定

八、桶排序

 (Bucket Sort)

package main

import (
    "fmt"
    "sort"
)

// BucketSort implements the bucket sort algorithm
func BucketSort(arr []int, bucketSize int) []int {
    if len(arr) == 0 {
        return arr
    }

    // Determine minimum and maximum values
    minValue := arr[0]
    maxValue := arr[0]
    for _, num := range arr {
        if num < minValue {
            minValue = num
        } else if num > maxValue {
            maxValue = num
        }
    }

    // Initialize buckets
    bucketCount := (maxValue-minValue)/bucketSize + 1
    buckets := make([][]int, bucketCount)

    // Distribute input array values into buckets
    for _, num := range arr {
        bucketIndex := (num - minValue) / bucketSize
        buckets[bucketIndex] = append(buckets[bucketIndex], num)
    }

    // Sort individual buckets and concatenate them
    sortedArr := []int{}
    for _, bucket := range buckets {
        sort.Ints(bucket)
        sortedArr = append(sortedArr, bucket...)
    }

    return sortedArr
}

func main() {
    arr := []int{42, 32, 33, 52, 37, 47, 51}
    sortedArr := BucketSort(arr, 5)
    fmt.Println("Sorted array:", sortedArr)
}

时间复杂度：

• 平均：O(n + k)（k是桶的数量）

• 最坏：O(n^2)（当所有元素分布到同一桶内）

• 最好：O(n + k)

稳定性：稳定