了解插入排序算法（附Java示例）

插入排序算法详解及代码实现

插入排序是一种简洁高效的排序算法，其核心思想是将未排序序列中的每个元素依次插入到已排序序列中的适当位置。 这种算法类似于我们整理扑克牌的过程：假设手中第一张牌已排序，然后依次取下一张牌，将其与已排序的牌进行比较，找到合适的位置插入。

插入排序工作原理图解：

迭代过程：

假设我们按升序排列数组。

第一次迭代：比较元素2和已排序部分的元素8。由于2<8，将8右移，2左移。

第二次迭代：比较元素6与已排序部分的2和8。6<8，将8右移，6左移；6>2，6已处于正确位置。

重复此过程，直到数组完全排序。

插入排序代码实现：

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("未排序数组: " + java.util.Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("已排序数组: " + java.util.Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

代码详解：

外层循环遍历数组，内层循环将当前元素与已排序部分进行比较并移动元素，直到找到合适位置插入。

运行结果：

未排序数组: [8, 2, 6, 4, 9, 1]
已排序数组: [1, 2, 4, 6, 8, 9]

算法复杂度分析：

• 时间复杂度: 最佳情况O(n)（数组已排序），平均情况O(n²)，最坏情况O(n²)(数组逆序)。
• 空间复杂度: O(1) (就地排序)

结论：

插入排序算法简单易懂，适合小规模数据的排序，但对于大型数据集效率较低。 其优势在于简单实现和对近乎有序数据的处理效率高。