插入排序

插入排序（Insertion Sort）是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表

算法原理

• 核心思想：将数组分为 已排序区间 和 未排序区间，逐个将未排序区间的元素插入到已排序区间的正确位置。
• 特点：
  • 稳定排序（相同元素的相对顺序不变）。
  • 适合小规模或基本有序的数据。
• 操作方式：类似于整理扑克牌时逐个调整牌的位置。

---

时间复杂度

场景	时间复杂度
最好情况	O(n)（已有序）
最坏情况	O(n²)
平均情况	O(n²)

---

代码实现

Golang 实现

package main

import "fmt"

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--
        }
        arr[j+1] = key  // 插入到正确位置
    }
}

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

Java 实现

public class InsertionSort {
  public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
      int key = arr[i];  // 当前待插入元素
      int j = i - 1;
      // 将比 key 大的元素向右移动
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;  // 插入到正确位置
    }
  }

  public static void main(String[] args) {
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    insertionSort(arr);
    System.out.print("Sorted: ");
    for (int num : arr) {
      System.out.print(num + " ");  // Output: Sorted: 11 12 22 25 34 64 90 
    }
  }
}