插入排序（Insertion Sort）

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

1. 插入排序的基本概念

从列表的第二个元素开始，把它与前面已排序的部分逐个比较，插到正确的位置。每插入一个元素，已排序的部分就多一个，直到所有元素都排好。

2. 插入排序的算法步骤

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

1. 外层循环: 从列表的第二个元素开始。

   • 当前元素 key 是要插入到已排序部分中的元素。

2. 内层循环: 从已排序部分的末尾向前遍历，找到 key 应插入的位置。

   • 将比 key 大的元素向后移动。

3. 插入操作:

   • 将 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)$，对大规模数据集效率较低。
• 不适合处理大量数据或数据不按顺序排列的情况。

总结

插入排序把每个新元素插到已排序部分的正确位置。数组已有序时是 $O(n)$，完全逆序时是 $O(n^2)$，原地排序不占额外空间。它实现简单，小规模或近乎有序的数据上够用，数据一多就不合适了。

参考资料

• 插入排序 · Wikipedia

同层页面

• BubbleSort
• BucketSort
• CocktailSort
• HeapSort
• MergeSort

相关页面

• HeapSort
• MergeSort