详解直接插入排序算法与相关的Java版代码实现

直接插入排序的核心思路

直接插入排序（Insertion Sort）是一种简单直观的排序方法。其基本思想是将待排序的元素逐个插入到已排好的序列中，从而形成一个越来越长的有序子集。具体执行流程如下：

1. 初始化有序区：默认将数组的第一个元素视为已排好序的初始状态。
2. 迭代处理未排序区：从第二个元素开始，依次取出未排序区的第一个元素。
3. 定位与插入：在已排序的子数组中，从后向前寻找该元素的合适位置。一旦找到比当前元素大的值，则将其向后移动一位，腾出空位，直到找到不大于该元素的节点或到达数组头部，此时空出的位置即为目标插入点。
4. 循环结束：重复上述过程，直至所有元素均被处理完毕。

Java代码实现细节

虽然算法逻辑直观，但在具体的编程语言实现中（尤其是Java），需要仔细处理边界条件和数组移动的逻辑。相比于冒泡排序，插入排序的优势在于减少不必要的交换操作。

1. 数据结构定义
为了演示清晰，我们使用一个包装类 InsertArray 来封装数组操作。该类包含一个固定容量的数组和一个记录有效元素数量的变量 elems。

public class InsertArray {
  // 存储数据的数组
  private long[] arr;
  // 数组中有效数据的大小
  private int elems;

  // 默认构造函数
  public InsertArray() {
    arr = new long[50];
  }

  public InsertArray(int max) {
    arr = new long[max];
  }

  // 向数组末尾插入新数据
  public void insert(long value) {
    arr[elems] = value;
    elems++;
  }

  // 打印当前数组内容
  public void display() {
    for (int i = 0; i < elems; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

2. 核心排序逻辑
这是算法的关键部分。我们没有采用从前往后遍历查找位置的笨拙方法，而是采用了逆向比较并后移的策略：

• 外层循环：i 从第二个元素开始，代表当前需要插入到前面有序区的元素索引。
• 保存目标：select = arr[i]，先将当前待插入的值暂存，避免后续前移时被覆盖。
• 内层循环：从 j = i 开始，只要 j > 0 且前一个元素 arr[j - 1] 大于 select，就将 arr[j - 1] 的值复制到 arr[j]，从而实现元素向后移动一步。
• 完成插入：当内层循环结束时，j 指向的就是 select 应该存放的最终位置。

  // 插入排序核心算法
  public void insertSort() {
    long select = 0L;
    for(int i = 1; i < elems; i++) {
      select = arr[i];
      int j = 0;
      // 从右向左比较，如果左边元素大，则向右移动一位
      for(j = i;j > 0 && arr[j - 1] >= select; j--) {
        arr[j] = arr[j - 1];
      }
      // 将暂存的数值放入找到的正确位置
      arr[j] = select;
    }
  }
}

3. 测试验证
创建测试类实例化对象并插入一组无序数据，观察排序前后的变化。

public class TestInsertArray {
  public static void main(String[] args) {
    InsertArray iArr = new InsertArray();
    iArr.insert(85);
    iArr.insert(7856);
    iArr.insert(12);
    iArr.insert(8);
    iArr.insert(5);
    iArr.insert(56);

    System.out.println("排序前:");
    iArr.display();
    
    iArr.insertSort();
    
    System.out.println("排序后:");
    iArr.display();
  }
}

算法性能与复杂度分析

理解直接插入排序的性能表现，需从输入数据的分布情况进行分类讨论：

1. 时间复杂度

• 最佳情况 O(n)：
  当输入数组本身就是正序（升序）时，内层循环条件 arr[j - 1] >= select 永远不成立，不进行任何移动操作，仅比较一次。因此只需线性扫描一遍，时间复杂度为 O(n)。
• 最坏情况 O(n²)：
  当输入数组为逆序时，每个元素都需要与前面的所有元素比较并发生移动。第 i 轮操作大约需要进行 i 次比较和赋值。总的操作次数约为 n²/2，时间复杂度退化至 O(n²)。
• 平均情况 O(n²)：
  即便随机分布，平均每对元素需要比较一半的次数，运算次数依然约为 n²/4，宏观上仍属于二次方级别 O(n²)。

2. 空间复杂度 O(1)

直接插入排序是在原数组内部进行的排序（In-place sort）。除了需要一个临时变量 select 来暂存当前要插入的元素外，不需要额外的存储空间辅助，因此空间复杂度为 O(1)。

3. 算法稳定性

直接插入排序是稳定的。因为在查找插入位置时，只有遇到严格大于目标值的元素才进行后移；如果遇到相等值的元素，会停止移动并放在其后，这保证了相同元素的相对顺序不会改变。

进阶应用与变种

适用场景

由于存在 O(n²) 的复杂度上限，直接插入排序在面对大规模随机数据时表现不佳。然而，它具有两个鲜明的优点：
1. 算法简单，常数因子小。
2. 对近乎有序的数据极度高效（接近 O(n)）。
因此，它通常不作为独立的主排序算法用于大数据量排序，而是作为高级混合排序算法的一部分，专门用于处理小规模子问题。例如，JDK 7 中 Arrays.sort() 的实现里，当待排子数组长度小于 47 时，就会切换使用插入排序来提升效率。

二分插入排序优化

如果在数据量较大的情况下，我们可以结合二分查找（Binary Search）技术。既然已经知道前半部分是有序的，就可以利用二分查找快速确定插入位置，将“寻找插入点”的时间复杂度从 O(n) 降低到 O(log n)。需要注意的是，尽管查找快了，但元素的后移操作依然无法避免，总体的时间复杂度仍然维持在 O(n²)，但在特定硬件架构下可以减少比较次数。

其他变种

除折半插入排序外，还有针对链表的表插入排序等结构，它们通过改变存储介质来规避数组内存搬移的开销，但核心的渐进时间复杂度并未发生本质突破。