插入排序 - Hello Golang

插入排序（Insertion Sort）

插入排序是一种简单的排序算法，其核心思想是通过将元素逐个插入到已经排序的部分中，逐步实现整个列表的排序。它类似于我们在手动排序扑克牌时的操作：每次取一张新牌，插入到已排序的牌中，保持整个扑克牌的有序状态。

1. 插入排序的基本概念

插入排序的过程如下：

将元素插入已排序部分:
- 从列表的第二个元素开始，将其与已排序部分的元素进行比较。
- 将当前元素插入到已排序部分的正确位置。
逐步扩展排序范围:
- 每次将一个新的元素插入到已排序部分中，逐步扩展已排序部分的范围。
保持排序状态:
- 确保插入操作不会打乱已排序部分的顺序。

2. 插入排序的算法步骤

以下是插入排序的详细步骤：

外层循环: 从列表的第二个元素开始。
- 当前元素 key 是要插入到已排序部分中的元素。
内层循环: 从已排序部分的末尾向前遍历，找到 key 应插入的位置。
- 将比 key 大的元素向后移动。
插入操作:
- 将 key 插入到找到的位置，保持已排序部分的顺序。

3. 插入排序的时间复杂度和空间复杂度

时间复杂度:
- 最坏情况: $O (n^{2})$ ，当数组完全逆序时，每次插入都需要遍历整个已排序部分。
- 最佳情况: $O (n)$ ，当数组已经排序好时，仅需进行一次遍历，插入操作为线性时间。
- 平均情况: $O (n^{2})$ ，对随机排序的数组进行排序时，平均时间复杂度为 $O (n^{2})$ 。
空间复杂度:
- 空间复杂度: $O (1)$ ，插入排序是就地排序算法，不需要额外的存储空间，除了用于插入的变量。

4. 插入排序的代码示例

以下是使用 Go 语言实现的插入排序算法：

package main

import "fmt"

// InsertionSort 对整数切片进行插入排序
func InsertionSort(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        key := arr[i]
        j := i - 1
        // 将比 key 大的元素向后移动
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        // 将 key 插入到正确的位置
        arr[j+1] = key
    }
}

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

5. 插入排序的优缺点

优点:

实现简单，易于理解和编写。
对于小规模数据集或近乎有序的数据表现良好。
稳定排序算法（相同值的元素保持相对位置不变）。

缺点:

时间复杂度为 $O (n^{2})$ ，对大规模数据集效率较低。
不适合处理大量数据或数据不按顺序排列的情况。

总结

插入排序是一种基础的排序算法，通过将每个新元素插入到已排序部分的正确位置，实现整个列表的排序。尽管它在处理大规模数据时效率较低，但其简单的实现和对小规模数据的良好表现，使其成为学习排序算法和理解排序基本概念的有效工具。