Go语言实现常用排序算法的示例代码

本文将详细介绍如何使用Go语言实现常用排序算法的示例代码。主要内容包括:

1. 排序算法介绍
2. 排序算法示例代码
3. 算法测试

排序算法介绍

排序算法是计算机科学基本的算法，其目的是将一组数据按照特定的规则进行排序。常用的排序算法包括冒泡排序、选择排序、插入排序、归并排序和快速排序等。以下是每种算法的简单介绍：

• 冒泡排序：重复比较相邻的两个元素，将较大的元素向后移动，最终将最大的元素移到最后。
• 选择排序：每次选择一个最小值，放在已排序好的末尾。
• 插入排序：将一个元素插入到已排序好的序列中，使插入后的序列仍保持有序。
• 归并排序：采用分而治之的思想，将数组不断划分为更小的数组，最后将小数组合并为大数组。
• 快速排序：选择一个基准（pivot）元素，将小于基准的元素放在左边，大于基准的元素放在右边，然后递归对左右两部分进行排序。

排序算法示例代码

下面是使用Go语言实现常用排序算法的示例代码。其中，每个算法都定义为独立的函数，并按照算法名称进行命名。

冒泡排序

func bubbleSort(arr []int) {
    for i := 0; i < len(arr)-1; i++ {
        for j := 0; j < len(arr)-1-i; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

选择排序

func selectionSort(arr []int) {
    for i := 0; i < len(arr)-1; i++ {
        minIdx := i
        for j := i + 1; j < len(arr); j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
}

插入排序

func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        temp := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > temp {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = temp
    }
}

归并排序

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 {
    i, j := 0, 0
    result := make([]int, 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 quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    pivot := arr[0]
    left, right := make([]int, 0), make([]int, 0)
    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)
    result := append(append(left, pivot), right...)
    return result
}

算法测试

为了测试示例代码的正确性，我们可以定义一个测试函数，输入一个未排序的数组，然后使用不同的排序算法进行排序，并输出排序结果。

func testSort() {
    arr := []int{9, 8, 7, 6, 5, 4, 3, 2, 1}
    fmt.Println("--- before sort ---")
    fmt.Println(arr)
    bubbleSort(arr)
    fmt.Println("--- after bubble sort ---")
    fmt.Println(arr)
    arr = []int{9, 8, 7, 6, 5, 4, 3, 2, 1}
    selectionSort(arr)
    fmt.Println("--- after selection sort ---")
    fmt.Println(arr)
    arr = []int{9, 8, 7, 6, 5, 4, 3, 2, 1}
    insertionSort(arr)
    fmt.Println("--- after insertion sort ---")
    fmt.Println(arr)
    arr = []int{9, 8, 7, 6, 5, 4, 3, 2, 1}
    arr = mergeSort(arr)
    fmt.Println("--- after merge sort ---")
    fmt.Println(arr)
    arr = []int{9, 8, 7, 6, 5, 4, 3, 2, 1}
    arr = quickSort(arr)
    fmt.Println("--- after quick sort ---")
    fmt.Println(arr)
}

定义完测试函数后，我们就可以运行该函数来测试排序算法的正确性了。例如：

func main() {
    testSort()
}

输出结果如下：

--- before sort ---
[9 8 7 6 5 4 3 2 1]
--- after bubble sort ---
[1 2 3 4 5 6 7 8 9]
--- after selection sort ---
[1 2 3 4 5 6 7 8 9]
--- after insertion sort ---
[1 2 3 4 5 6 7 8 9]
--- after merge sort ---
[1 2 3 4 5 6 7 8 9]
--- after quick sort ---
[1 2 3 4 5 6 7 8 9]

从结果可以看出，各种排序算法均能正确地将输入数组排序。