排序算法

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的比较排序算法，它通过不断地交换相邻的元素，使较大的元素逐渐移动到数组的末尾。

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{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("Unsorted array:", arr)
    bubbleSort(arr)
    fmt.Println("Sorted array:", arr)
}

2. 选择排序（Selection Sort）

选择排序在未排序部分中找到最小（或最大）的元素，然后将其放到已排序部分的末尾。

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{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("Unsorted array:", arr)
    selectionSort(arr)
    fmt.Println("Sorted array:", arr)
}

3. 插入排序（Insertion Sort）

插入排序将数组分成已排序和未排序两部分，然后逐一将未排序部分的元素插入到已排序部分的合适位置。

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{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("Unsorted array:", arr)
    insertionSort(arr)
    fmt.Println("Sorted array:", arr)
}

4. 快速排序（Quick Sort）

快速排序是一种分治算法，它选择一个元素作为”枢纽”（pivot）并将数组分为两个子数组，一个子数组的所有元素小于枢纽，另一个子数组的所有元素大于枢纽。然后，递归地对这两个子数组进行排序。最后，将子数组合并起来，整个数组就被排序了。快速排序的关键在于选择枢纽元素和分区过程。

package main

import "fmt"

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

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("Unsorted array:", arr)
    quickSort(arr, 0, len(arr)-1)
    fmt.Println("Sorted array:", arr)
}

5. 归并排序（Merge Sort）

归并排序也是一种分治算法，它将数组划分为更小的子数组，然后将这些子数组合并以得到排序的结果。归并排序的关键在于”分”和”合”两个操作。”分”操作将数组分为两个子数组，然后递归地对这两个子数组进行排序。”合”操作将两个有序的子数组合并成一个有序的数组。归并排序是稳定的排序算法。

package main

import "fmt"

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

    middle := len(arr) / 2
    left := mergeSort(arr[:middle])
    right := mergeSort(arr[middle:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0)
    for len(left) > 0 || len(right) > 0 {
        if 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:]
            }
        } else if len(left) > 0 {
            result = append(result, left[0])
            left = left[1:]
        } else {
            result = append(result, right[0])
            right = right[1:]
        }
    }
    return result
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("Unsorted array:", arr)
    arr = mergeSort(arr)
    fmt.Println("Sorted array:", arr)
}

6. 堆排序（Heap Sort）

堆排序是一种基于二叉堆数据结构的排序算法。首先，将待排序的数组构建成一个最大堆（或最小堆），堆中的根节点是数组中的最大（或最小）元素。然后，将根节点与最后一个元素交换，将最大元素移动到已排序的末尾。接着，对剩余的元素进行堆重建，再次将最大元素移动到已排序的末尾。重复这个过程，直到整个数组排序完成。堆排序具有良好的性能，并且不需要额外的空间。

package main

import "fmt"

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{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("Unsorted array:", arr)
    heapSort(arr)
    fmt.Println("Sorted array:", arr)
}

作者: 东南dnf

链接: https://dnf.doyi.online/posts/3963924866.html

声明: 本博客所有文章除特别声明外，均采用许可协议 CC-BY-NC-4.0 转载请注明出处！

Golang 排序

目录