重温经典算法——插入排序

版权声明

• 本文原创作者：谷哥的小弟
• 作者博客地址：http://blog.csdn.net/lfdfhl

基本原理

插入排序是一种基于元素逐步插入的简单排序算法，其核心思想是将待排序序列分为已排序和未排序两部分，每次从未排序部分取出第一个元素，反向遍历已排序部分，找到合适位置插入。时间复杂度为平均和最差 O(n²)，最好 O(n)（已有序时），空间复杂度 O(1)，属于原地、稳定排序，适用于小规模数据或部分有序数据的场景。

代码实现

import java.util.Arrays;public class InsertionSort {public static void insertionSort(int[] arr) {int n = arr.length;// 从第二个元素开始遍历（索引1到n-1）for (int i = 1; i < n; i++) { int current = arr[i]; // 当前待插入元素int j = i - 1;        // 已排序部分的末尾索引// 反向遍历已排序部分，找到插入位置while (j >= 0 && arr[j] > current) { arr[j + 1] = arr[j]; // 将大于current的元素后移j--;}arr[j + 1] = current; // 插入当前元素到正确位置}}public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6};insertionSort(arr);System.out.println("Sorted array: " + Arrays.toString(arr));// 输出：Sorted array: [5, 6, 11, 12, 13]}
}