Golang排序詳解

一、基本排序算法

Golang提供了多種基本排序算法，最常用的有冒泡排序、插入排序和選擇排序。三種算法的主要區別在於排序的穩定性、時間複雜度和空間複雜度。

1. 冒泡排序

func BubbleSort(data sort.Interface) {
    for i := 0; i < data.Len()-1; i++ {
        for j := 0; j < data.Len()-1-i; j++ {
            if data.Less(j+1, j) {
                data.Swap(j, j+1)
            }
        }
    }
}

冒泡排序是一種基本的排序算法，它相鄰的元素進行比較，如果滿足條件則交換位置。該算法的時間複雜度為O(n^2)。

2. 插入排序

func InsertionSort(data sort.Interface) {
    for i := 1; i  0 && data.Less(j, j-1); j-- {
            data.Swap(j, j-1)
        }
    }
}

插入排序是一種比較穩定的排序算法，它將數組分為已排序和未排序兩部分，每次從未排序的元素中選擇一個插入到已排序的元素中。該算法的時間複雜度為O(n^2)。

3. 選擇排序

func SelectionSort(data sort.Interface) {
    for i := 0; i < data.Len()-1; i++ {
        minIndex := i
        for j := i + 1; j < data.Len(); j++ {
            if data.Less(j, minIndex) {
                minIndex = j
            }
        }
        if minIndex != i {
            data.Swap(i, minIndex)
        }
    }
}

選擇排序是一種比較簡單的排序算法，它每次選擇最小的元素放到已排序的元素中。該算法的時間複雜度為O(n^2)。

二、快速排序

快速排序是一種比較常用的排序算法，它的時間複雜度為O(nlogn)。該算法利用分治的思想，將一個大問題分成多個小問題解決，然後將小問題的結構合併起來。

func QuickSort(data sort.Interface) {
    quickSort(data, 0, data.Len()-1)
}

func quickSort(data sort.Interface, left, right int) {
    if left >= right {
        return
    }
    pivotIndex := partition(data, left, right)
    quickSort(data, left, pivotIndex-1)
    quickSort(data, pivotIndex+1, right)
}

func partition(data sort.Interface, left, right int) int {
    pivotIndex := left
    pivot := right
    for i := left; i < right; i++ {
        if data.Less(i, pivot) {
            data.Swap(i, pivotIndex)
            pivotIndex++
        }
    }
    data.Swap(pivotIndex, right)
    return pivotIndex
}

快速排序的主要思想是選擇一個基準值（通常是數組的最後一個值），將數組分為兩部分，一部分小於基準值，一部分大於基準值，然後按照同樣的方式遞歸處理兩部分的子數組，直到排序完成。

三、歸併排序

歸併排序是一種比較高效的排序算法，它的時間複雜度為O(nlogn)。該算法利用分治的思想，將一個大問題分成多個小問題解決，然後將小問題的結構合併起來。

func MergeSort(data sort.Interface) {
    mergeSort(data, 0, data.Len()-1)
}

func mergeSort(data sort.Interface, left, right int) {
    if left >= right {
        return
    }
    mid := (left + right) / 2
    mergeSort(data, left, mid)
    mergeSort(data, mid+1, right)
    merge(data, left, mid, right)
}

func merge(data sort.Interface, left, mid, right int) {
    tmp := make([]reflect.Value, right-left+1)
    i, j, k := left, mid+1, 0
    for i <= mid && j <= right {
        if data.Less(i, j) {
            tmp[k] = data.Index(i)
            i++
        } else {
            tmp[k] = data.Index(j)
            j++
        }
        k++
    }
    for i <= mid {
        tmp[k] = data.Index(i)
        k++
        i++
    }
    for j <= right {
        tmp[k] = data.Index(j)
        k++
        j++
    }
    for i, j := left, 0; i <= right; i, j = i+1, j+1 {
        data.Swap(i, reflect.Indirect(tmp[j]).Interface().(int))
    }
}

歸併排序將數組分成兩部分，分別排序，然後再將兩個有序數組合併成一個有序數組。該算法需要額外的內存空間存儲數組的拷貝，因此空間複雜度為O(n)。

四、堆排序

堆排序是一種比較常用的排序算法，它的時間複雜度為O(nlogn)。該算法利用堆的性質來實現排序。

func HeapSort(data sort.Interface) {
    heap := &Heap{data}
    heap.Init()
    for i := data.Len() - 1; i >= 0; i-- {
        heap.data.Swap(0, i)
        heap.size--
        heap.down(0)
    }
}

type Heap struct {
    data sort.Interface
    size int
}

func (h *Heap) Init() {
    h.size = h.data.Len()
    for i := h.size/2 - 1; i >= 0; i-- {
        h.down(i)
    }
}

func (h *Heap) down(root int) {
    for {
        left := root*2 + 1
        if left >= h.size {
            break
        }
        right := left + 1
        maxChildIndex := left
        if right < h.size && h.data.Less(left, right) {
            maxChildIndex = right
        }
        if h.data.Less(root, maxChildIndex) {
            h.data.Swap(root, maxChildIndex)
            root = maxChildIndex
        } else {
            break
        }
    }
}

堆是一種數據結構，它可以很方便地實現排序。堆排序分為兩個階段，第一階段是建立一個最大堆，第二階段是依次取出堆頂元素，並將剩餘元素重新構建一個最大堆。

五、小結

本文介紹了Golang中的排序算法，包括冒泡排序、插入排序、選擇排序、快速排序、歸併排序和堆排序。每種算法的時間複雜度和空間複雜度各有不同，開發者應該根據實際情況選擇最合適的算法。