Go语言数据结构之插入排序示例详解

什么是插入排序？

插入排序是一种简单直观的排序方法，其基本思想是将一个待排序的序列分成已排序和未排序两部分，从未排序的部分中选择一个元素插入到已排序部分的合适位置，直到所有元素都被插入到已排序部分为止。

插入排序示例

示例1

我们来看一个数字序列的插入排序示例：

package main

import "fmt"

func InsertionSort(arr []int) []int {
    var preIndex, current int
    for i := 1; i < len(arr); i++ {
        preIndex = i - 1
        current = arr[i]
        for preIndex >= 0 && arr[preIndex] > current {
            arr[preIndex+1] = arr[preIndex]
            preIndex--
        }
        arr[preIndex+1] = current
    }
    return arr
}

func main() {
    arr := []int{10, 7, 5, 3, 1, 8, 4, 9, 6, 2}
    fmt.Println(InsertionSort(arr))
}

输出结果为：

[1 2 3 4 5 6 7 8 9 10]

示例2

我们再看一个字符串序列的插入排序示例：

package main

import (
    "fmt"
    "strings"
)

func InsertionSort(arr []string) []string {
    var preIndex, current string
    for i := 1; i < len(arr); i++ {
        preIndex = arr[i-1]
        current = arr[i]
        for preIndex > current {
            arr[i] = preIndex// 插入排序之交换数据位置-内容1
            i--
            if i > 0 {
                preIndex = arr[i-1]
            } else {
                break
            }
        }
        arr[i] = current
    }
    return arr
}

func main() {
    arr := []string{"s", "o", "r", "t", "e", "x", "a", "m", "p", "l", "e"}
    fmt.Println(strings.Join(InsertionSort(arr), ""))
}

输出结果为：

aelmoprstx

插入排序的时间复杂度

插入排序的时间复杂度为$O(n^2)$。虽然时间复杂度比较高，但插入排序具有稳定性，且对于小规模的数据表现良好。另外，其内层循环虽然也是$O(n)$的，但是常数因子非常小，因此实际性能较好。

总结

插入排序是一个简单实用的排序算法，特别适用于小规模数据的排序。Go语言实现插入排序只需要几行代码就可以了，而且代码逻辑比较清晰。