基于Go手把手教你实现经典排序算法：冒泡、插入、选择

前言

排序算法是计算机科学中一种基本的算法，它可以对输入数据进行排序，使得数据按照一定的顺序排列。冒泡排序、插入排序和选择排序是三种简单但实用的排序算法。它们都是比较排序算法，即通过比较两个元素的大小来确定它们的顺序。

这三种排序算法都是简单易懂的，但它们在实际应用中可能会比较慢，因为它们的复杂度都是O(n^2)。在实际应用中，我们通常会使用更高效的排序算法，如归并排序、快速排序等。但是，对于小规模的数据或者初学者来说，这三种排序算法是很好的入门选择。那么我们来一探究竟吧~

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

代码语言：go复制

package main

import "fmt"

func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n; 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("排序前:", arr)
    bubbleSort(arr)
    fmt.Println("排序后:", arr)

}

解释一下：

首先，我们获取输入数组的长度n，这将用于遍历数组。
然后，我们使用一个外部循环for i := 0; i < n; i 来遍历数组中的每个元素，从第一个元素开始，直到最后一个元素。
在外部循环中，我们使用一个内部循环for j := 0; j < n-i-1; j 来遍历当前未排序部分的每个相邻的两个元素，从第一个元素开始，直到倒数第二个元素。
在内部循环中，我们使用if语句来比较当前元素arrj和下一个元素arrj 1的大小。如果当前元素大于下一个元素，我们将它们交换位置，即将arrj赋值为arrj 1，将arrj 1赋值为arrj。
内部循环结束后，最大的元素将被移动到数组的末尾。
外部循环结束后，整个数组就已经排好序了。

插入排序

插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码语言：go复制

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 = j - 1
        }
        arr[j 1] = key
    }
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("插入排序前:", arr)
    insertionSort(arr)
    fmt.Println("插入排序后:", arr)
}

解释一下：

首先，我们获取输入数组的长度n，这将用于遍历数组。
然后，我们使用一个外部循环for i := 1; i < n; i 来遍历数组中的每个元素，从第二个元素开始，直到最后一个元素。
在外部循环中，我们将当前元素arri存储在变量key中，这将用于与前面的元素进行比较。
接下来，我们使用一个内部循环for j := i - 1; j >= 0 && arrj > key; j--来遍历当前元素之前的已排序部分，从当前元素的前一个元素开始，直到第一个元素。
在内部循环中，我们使用if语句来比较当前元素key和前面的元素arrj的大小。如果前面的元素大于当前元素，我们将前面的元素向右移动一位，即将arrj 1赋值为arrj。
内部循环结束后，我们已经将当前元素key插入到正确的位置，即arrj 1。
外部循环结束后，整个数组就已经排好序了。

选择排序

选择排序（Selection sort）是一种简单直观的排序算法，它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

代码语言：go复制

package main

import "fmt"

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

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("选择排序前:", arr)
    selectionSort(arr)
    fmt.Println("选择排序后:", arr)
}

解释一下：

首先，我们获取输入数组的长度n，这将用于遍历数组。
然后，我们使用一个外部循环for i := 0; i < n-1; i 来遍历数组中的每个元素，从第一个元素开始，直到倒数第二个元素。
在外部循环中，我们初始化一个变量minIndex，它将用于存储当前未排序部分的最小元素的索引。我们将其初始化为当前外部循环的索引i。
接下来，我们使用一个内部循环for j := i 1; j < n; j 来遍历当前未排序部分的每个元素，从下一个元素开始，直到最后一个元素。
在内部循环中，我们使用if语句来比较当前元素arrj和当前最小元素arrminIndex的大小。如果当前元素小于当前最小元素，我们将minIndex更新为当前元素的索引j。
内部循环结束后，我们已经找到了当前未排序部分的最小元素，并将其索引存储在minIndex中。
接下来，我们使用arri, arrminIndex = arrminIndex, arri来交换当前元素arri和最小元素arrminIndex的位置。这样，当前元素就被放在了正确的位置上。
外部循环结束后，整个数组就已经排好序了。

End

如果你有任何问题或建议，欢迎在下方留言，我会尽快回复
如果你觉得本文对你有帮助，欢迎点赞、收藏，你的支持是我写作的最大动力

0 人点赞