插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，适合初学者理解排序的基本概念。它通过逐个将元素插入到已排序部分的正确位置来构建有序序列。本文将详细讲解插入排序的原理、步骤，并提供C语言和Go语言的代码示例，帮助初学者快速上手。

原理

插入排序的核心思想是：

1. 从数组的第二个元素开始，假设第一个元素是已排序部分。
2. 将当前元素与已排序部分的元素从后向前比较，找到其正确插入位置。
3. 将比当前元素大的元素后移，为当前元素腾出插入位置。
4. 将当前元素插入到正确位置。
5. 重复上述步骤，直到整个数组排序完成。

它的时间复杂度是 O(n²)，其中 n 是数组的长度。虽然在实际应用中效率不如快速排序或归并排序，但它的简单性和对小规模数据的效率使其成为学习算法的理想选择。

步骤

假设我们要对一个整数数组进行升序排序，以下是插入排序的详细步骤：

1. 初始化：将数组的第一个元素视为已排序部分，从第二个元素开始处理。
2. 选取元素：取未排序部分的第一个元素作为当前元素。
3. 比较与移动：将当前元素与已排序部分的元素从后向前比较，如果已排序部分的元素大于当前元素，则将其后移一位。
4. 插入：将当前元素插入到正确位置。
5. 重复：对剩余的未排序元素重复步骤2-4，直到整个数组排序完成。

实现

C

下面是用C语言实现插入排序的代码，包含详细注释以帮助理解。

main.c

#include <stdio.h>

// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, j, key;
    
    // 从第二个元素开始
    for (i = 1; i < n; i++) {
        key = arr[i]; // 选取当前元素
        j = i - 1;   // 已排序部分的最后一个元素索引
        
        // 将大于key的元素后移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        // 将key插入到正确位置
        arr[j + 1] = key;
    }
}

// 打印数组的辅助函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数：测试插入排序
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组：");
    printArray(arr, n);
    
    insertionSort(arr, n);
    
    printf("排序后的数组：");
    printArray(arr, n);
    
    return 0;
}

编译 & 运行

$ gcc -o bin/insertion-sort main.c
$ bin/insertion-sort 
原始数组：64 34 25 12 22 11 90 
排序后的数组：11 12 22 25 34 64 90 
$ 

Go

下面是用Go语言实现插入排序的代码，包含详细注释以帮助理解。

main.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
    }
}

// printArray 打印数组内容
func printArray(arr []int) {
    for _, val := range arr {
        fmt.Printf("%d ", val)
    }
    fmt.Println()
}

func main() {
    // 示例数组
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    
    fmt.Print("原始数组：")
    printArray(arr)
    
    insertionSort(arr)
    
    fmt.Print("排序后的数组：")
    printArray(arr)
}

$ gsk build -v
create insertion-sort/bin/insertion-sort-linux-amd64
$ ./bin/insertion-sort-linux-amd64 
原始数组：64 34 25 12 22 11 90 
排序后的数组：11 12 22 25 34 64 90

总结

插入排序的核心是通过将未排序部分的元素逐个插入到已排序部分的正确位置来实现排序。

---

版权声明：自由转载-非商用-非衍生-保持署名-保持来源

作者：afxcn

来源：https://zh.gostartkit.com/docs/algo/insertion-sort

发表日期：2025年6月28日