Go 語言排序

Go 語言排序是一種排序演算法，它可以將一個陣列中的元素按照指定的順序排列。Go 語言排序演算法可以分為兩種：比較排序和非比較排序。比較排序是指比較兩個元素的大小，然後按照指定的順序排列，而非比較排序則是指不比較兩個元素的大小，而是根據元素的特性來排序。

Go 語言比較排序演算法有很多種，其中最常用的是快速排序（Quick Sort）、堆排序（Heap Sort）、归并排序（Merge Sort）和冒泡排序（Bubble Sort）。

快速排序（Quick Sort）

快速排序是一種分治演算法，它的基本思想是：將一個數組分成兩個子數組，其中一個子數組的所有元素都比另一個子數組的所有元素都要小，然後對兩個子數組分別進行快速排序，直到所有的子數組都被排序完成為止。

func QuickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    pivot := arr[0]
    left := []int{}
    right := []int{}

    for i := 1; i < len(arr); i++ {
        if arr[i] < pivot {
            left = append(left, arr[i])
        } else {
            right = append(right, arr[i])
        }
    }

    left = QuickSort(left)
    right = QuickSort(right)

    return append(append(left, pivot), right...)
}

堆排序（Heap Sort）

堆排序是一種比較排序演算法，它的基本思想是：將一個數組轉換為一個完全二叉樹，然後對該完全二叉樹進行排序。

func HeapSort(arr []int) []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)
    }

    return arr
}

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

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

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

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

归并排序（Merge Sort）

归并排序是一種分治演算法，它的基本思想是：將一個數組分成兩個子數組，然後對兩個子數組分別排序，最後將兩個子數組合併成一個有序的數組。

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{}

    for len(left) > 0 && len(right) > 0 {
        if left[0] < right[0] {
            result = append(result, left[0])
            left = left[1:]
        } else {
            result = append(result, right[0])
            right = right[1:]
        }
    }

    if len(left) > 0 {
        result = append(result, left...)
    }

    if len(right) > 0 {
        result = append(result, right...)
    }

    return result
}

冒泡排序（Bubble Sort）

冒泡排序是一種比較排序演算法，它的基本思想是：比較相鄰的兩個元素，如果它們的順序錯誤，則交換它們的位置，直到所有的元素都按照指定的順序排列為止。

func BubbleSort(arr []int) []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]
            }
        }
    }

    return arr
}

Go 語言排序演算法可以幫助我們將一個數組中的元素按照指定的順序排列，它們的時間複雜度和空間複雜度都不同，因此我們可以根據不同的情況來選擇合適的排序演算法。

Categorized in:

gogolang

Tagged in:

,