Java实现插入排序算法详解：图解原理与代码

一、基本思想

插入排序（Insertion Sort）的工作原理类似于整理手中的扑克牌。它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并将其插入。这种算法在数据量较小或部分数据已经有序时表现良好。

二、算法分析

第1步：初始化已排序序列

目的：确立排序的起始基准。
操作：假设数组的第一个元素 (索引0) 已经是有序的。
状态：此时已排序区间包含第一个元素。

第2步：取出下一个待处理元素

目的：准备将新元素纳入有序序列。
操作：提取当前未排序部分的第一个元素（即当前遍历到的元素）。
参数：通常从索引 i=1 开始遍历。

第3步：从后向前扫描比较

目的：寻找新元素的正确插入位置。
操作：将取出的新元素与已排序序列中最后一个元素进行比较。
判断：如果已排序元素大于新元素，说明新元素应插在该元素之前或更前位置。

第4步：确定插入位置（无需移动情况）

目的：若新元素比已排序序列末尾元素大，则无需移动。
操作：比较发现 1 < 28（假设场景），条件不成立，直接在当前位置插入或认为位置已对。
完成状态：序列保持相对有序。

第5步：处理需要移动的情况

目的：为新元素腾出空间。
操作：当已排序元素大于新元素时，将该已排序元素向右移动一位（复制到下一个位置），为新元素让出空位，并继续向前比较前一个元素。

第6步：执行元素右移

目的：物理上移动数据以创建插入槽。
操作：检测到 28 > 3 成立，将值 28 移至当前位置，形成空缺，指针 preIndex 前移。

第7步：继续向前比较

目的：检查是否还有更大的已排序元素。
操作：新指针指向的元素 1 与新元素 3 进行比较。

第8步：最终插入

目的：将新元素放入确定的位置。
操作：因为 1 < 3，不再发生移动。将新元素 3 插入到当前空位（preIndex + 1）处。
结果：[1, 3, 28] 构成新的有序子序列。

第9步：重复迭代

目的：处理剩余所有未排序元素。
操作：重复步骤2至步骤8，直到遍历完整个数组，此时整个数组变为有序。

三、算法实现

以下是基于 Java 语言的插入排序标准实现。代码采用 in-place（原地）排序，时间复杂度为 O(n²)，空间复杂度为 O(1)。

package com.algorithm.tenSortingAlgorithm;

import java.util.Arrays;

public class InsertionSort {
    private static void insertionSort(int[] arr) {
        int preIndex, current;
        // 从第二个元素开始遍历（索引1）
        for (int i = 1; i < arr.length; i++) {
            preIndex = i - 1;
            current = arr[i]; // 保存当前待插入元素
            
            // 从后向前扫描，若已排序元素大于当前元素，则后移
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            // 插入元素到正确位置
            arr[preIndex + 1] = current;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 28, 3, 21, 11, 7, 6, 18};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

以上就是Java中插入排序算法的原理与实现的详细内容，更多关于Java插入排序的资料请关注本站其它相关文章！