基于Go语言实现插入排序算法及优化

基于Go语言实现插入排序算法及优化攻略

插入排序算法

插入排序是一种简单直观的排序方法，主要思路是将未排序部分的第一个元素插入到已排序部分合适的位置。具体实现方式如下：

func InsertionSort(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        // 寻找arr[i]合适的插入位置
        for j := i; j > 0 && arr[j] < arr[j-1]; j-- {
            // 交换arr[j]和arr[j-1]
            arr[j], arr[j-1] = arr[j-1], arr[j]
        }
    }
}

其中，循环内的 for 语句用于寻找当前元素在已排序列表中合适的位置，并将元素插入该位置。如此迭代，最终得到一个有序的数组。值得注意的是，该算法最坏时间复杂度为 $O(n^2)$，因为每个元素都需要与已排序列表中的元素进行比较，并且可能需要不断交换位置。

插入排序算法优化

在实践中，插入排序可以针对特定数据集进行一些优化，以提高性能。以下是三种常见的优化方法：

1. 减少赋值操作

对于优化过的算法，我们常常尽可能减少比较和交换操作，因为对于大规模的数据，这些操作所耗费的时间是惊人的。因此，我们可以将需要比较和交换的元素复制一份，这样每次交换操作就会少半，从而提高算法的效率。

func InsertionSort2(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        temp := arr[i]
        j := i
        // 寻找temp合适的插入位置
        for ; j > 0 && temp < arr[j-1]; j-- {
            // 将较大的元素后移一位
            arr[j] = arr[j-1]
        }
        // 插入temp
        arr[j] = temp
    }
}

2. 二分查找插入位置

由于插入排序算法的主要瓶颈在于需要不断比较和移动元素，我们可以考虑将寻找插入位置的方式从顺序查找改为二分查找。这样一来，每次寻找插入位置的时间复杂度可以降为 $O(\log n)$。

func binarySearch(arr []int, value int, left, right int) int {
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == value {
            return mid
        } else if arr[mid] > value {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return left
}

func InsertionSort3(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        // 寻找arr[i]合适的插入位置
        index := binarySearch(arr, arr[i], 0, i-1)
        // 将arr[i]插入index处，并后移后面的元素
        for j := i; j > index; j-- {
            arr[j], arr[j-1] = arr[j-1], arr[j]
        }
    }
}

3. 序列分组

对于近乎有序的数据集合，可以考虑将序列分为多个子序列进行排序，以减少插入操作所涉及的元素数量。例如，下面的代码中，我们将数组按照一定的步长分为若干小组，然后对每个小组进行排序，最后合并为一个有序的数组。

func ShellSort(arr []int) {
    n := len(arr)
    for gap := n / 2; gap >= 1; gap /= 2 {
        // 对每个小组进行插入排序
        for i := gap; i < n; i++ {
            temp := arr[i]
            j := i - gap
            for ; j >= 0 && temp < arr[j]; j -= gap {
                arr[j+gap] = arr[j]
            }
            arr[j+gap] = temp
        }
    }
}

示例说明

示例1：优化二分查找插入位置

package main

import (
    "fmt"
)

// 二分查找arr数组中第一个大于等于value的数的下标
func binarySearch(arr []int, value int, left, right int) int {
    for left <= right {
        mid := left + (right - left) / 2
        if arr[mid] >= value {
            if mid == 0 || arr[mid - 1] < value {
                return mid
            } else {
                right = mid - 1
            }
        } else {
            left = mid + 1
        }
    }
    return left
}

func InsertionSort2(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        temp := arr[i]
        j := i
        // 寻找temp合适的插入位置
        index := binarySearch(arr, temp, 0, i-1)
        // 将较大的元素后移一位
        for ; j > index; j-- {
            arr[j] = arr[j - 1]
        }
        // 插入temp
        arr[index] = temp
    }
}

func main() {
    arr := []int{5, 2, 4, 6, 1, 3}
    InsertionSort2(arr)
    fmt.Println(arr)
}

输出结果：

[1 2 3 4 5 6]

上面的代码中，我们将插入算法优化为二分查找插入位置的方式，并且对原始的 InsertionSort 函数进行了一定的重构。运行该示例后，输出结果表明排序成功。

示例2：优化序列分组

package main

import (
    "fmt"
)

func InsertionSortWithStep(arr []int, step int) {
    n := len(arr)
    for i := step; i < n; i++ {
        temp := arr[i]
        j := i - step
        for ; j >= 0 && temp < arr[j]; j -= step {
            arr[j+step] = arr[j]
        }
        arr[j+step] = temp
    }
}

func ShellSort(arr []int) {
    n := len(arr)
    step := n / 2 // 初始步长
    for step > 0 {
        for i := 0; i < step; i++ {
            InsertionSortWithStep(arr[i:n], step) // 对每个小组进行插入排序
        }
        step /= 2 // 步长缩小一半
    }
}

func main() {
    arr := []int{3, 6, 1, 8, 2, 9, 0}
    ShellSort(arr)
    fmt.Println(arr)
}