插入排序算法 Java 附有程序范例

由： 编辑团队 编辑团队
Hours 更新

⚡ 智能摘要

插入排序 Java 它逐个元素地构建数组的排序部分，将较大的值向右移动，直到每个键都到达其正确的位置，这使得它非常适合小型数据集。

  • 🔘 定义： 插入排序会移除一个元素，并将其插入到已排序部分中的正确位置。
  • ☑️ 过程： 每次遍历都会将键与之前的值进行比较，并将较大的值向右移动一位。
  • ✅ 程序： 此 Java 例如，对 {860, 8, 200, 9} 进行排序，并打印每次比较和交换。
  • 🧪 复杂： 最佳情况下运行时间为 O(n)，而平均情况和最坏情况达到 O(n²)。
  • 🛠️ 记忆： 排序是原地进行的，因此对于任何数组大小，辅助空间始终保持 O(1)。
  • 📊 行为： 该算法稳定且具有自适应性，因此几乎有序的数组只需很少的移动即可完成。
阅读更多

插入排序算法 Java

什么是插入排序算法？

插入排序是一种适用于小数据集的简单排序算法。在每次迭代中，算法：

  • 从数组中删除一个元素。
  • 将其与 排列.
  • 将元素移动到正确的位置。

这种行为类似于玩家整理牌局的方式：每拿起一张新牌，都会将其向左推过所有较大的牌，直到到达正确的位置。由于所有移动操作都在原始数组内部进行，因此插入排序既是原地排序又是稳定的。

它属于同一类适合初学者的书籍。 Java 排序例程 气泡排序然而，对于已经部分有序的数据，它通常执行的写入操作要少得多。

插入排序算法过程

插入排序算法的工作流程如下：

动画 trac插入排序算法对无序列表进行重新排序
插入排序算法过程

动画重复了相同的三个步骤。 Java 以下程序将执行。试运行表 trac按照程序在运行时打印的方式，对示例数组 {860, 8, 200, 9} 执行这些步骤。

通过 关键要素 所做的比较 传递后的数组
1 8 8对860 8 860 200 9
2 200 200对860 8 200 860 9
3 9 9 对 860，然后 9 对 200 8 9 200 860

请注意，第三次遍历需要两次比较，因为键 9 必须经过两个更大的值。因此，比较次数会随着每个元素起始顺序的偏差而增加。

Java 使用插入排序算法对数组进行排序的程序示例：

以下程序对数组 {860, 8, 200, 9} 进行排序，并打印运行注释，因此每次比较和每次移位都清晰可见。将其保存为 InsertionSortExample.java 并使用 JDK 8 或更高版本进行编译。

package com.guru99;
 
public class InsertionSortExample {
 
	
    public static void main(String a[])
    {    
        int[] myArray  = {860,8,200,9};  
        
        System.out.println("Before Insertion Sort");  
        
        printArray(myArray);
            
        insertionSort(myArray);//sorting array using insertion sort    
           
        System.out.println("After Insertion Sort");  
        
        printArray(myArray);   
    }    
 public static void insertionSort(int arr[]) 
	{  
        int n = arr.length;  
        
        for (int i = 1; i < n; i++)
        {   System.out.println("Sort Pass Number "+(i));
            int key = arr[i];  
            int j = i-1;  
            
            while ( (j > -1) && ( arr [j] > key ) ) 
            {  
            System.out.println("Comparing "+ key  + " and " + arr [j]); 
                arr [j+1] = arr [j];  
                j--;  
            }  
            arr[j+1] = key; 
            System.out.println("Swapping Elements: New Array After Swap");
            printArray(arr);
        }  
    }
 static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
}

运行该类会产生以下结果 trac此处所示。每个 排序通行号 行标记外层循环的一次迭代，每次交换后打印的行显示数组在该时刻的状态。

Code 输出：

Before Insertion Sort
860 8 200 9 
Sort Pass Number 1
Comparing 8 and 860
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 200 860 9 
Sort Pass Number 3
Comparing 9 and 860
Comparing 9 and 200
Swapping Elements: New Array After Swap
8 9 200 860 
After Insertion Sort
8 9 200 860
不要错过：

插入排序的时间复杂度和空间复杂度

插入排序的性能很大程度上取决于输入数据的有序程度，这就是为什么最佳情况和最差情况相差一个数量级的原因。

案例 输入条件 时间复杂度
最棒的 数组已经排序，因此内部的 while 循环永远不会执行。 O（N）
一般 元素以随机顺序到达 O(n²)
最差 数组按逆序排列，因此每个键都会移动到数组的前面。 O(n²)

空间利用方式要简单得多。只有柜台。 i, j, n 和 key 创建数组时，数组会就地重新排列，因此无论输入增长到多大，辅助空间都是 O(1)。

由于内循环一旦遇到较小的值就会停止，因此插入排序被描述为自适应的：输入越接近有序顺序，运行时间就越接近线性。

插入排序的优点和缺点

尽管插入排序的常数因子很小，且其行为可预测，但它仍然在生产库中保留了下来，即使其平均时间为二次方。

优势

  • 编写简单，易于操作 trac手工绘制，适合教学和面试。
  • 稳定，因此共享同一键的记录将保持其原始相对顺序。
  • 就地操作，除了输入数组之外，只需要 O(1) 额外的内存。
  • 自适应，对于已经基本排序的数据，时间复杂度可达 O(n)。
  • 在线，意味着它可以在新元素不断到达时对列表进行排序。

缺点

  • 对于随机或逆序输入，二次时间复杂度使得它不适用于大型数组。
  • 每次移位都会向数组写入数据，因此它移动的数据比选择排序要多。
  • 当输入元素超过几十个时，归并排序和快速排序的性能就明显优于它。

一个实用的规则是，当数组较小、数据几乎有序，或者分治排序将一个分区减少到少数几个元素时，应该使用插入排序。

插入排序与 Bubble排序与选择排序

这三种算法都是二次比较排序，但它们在稳定性、对有序输入的反应以及执行的写入次数方面有所不同。

标准 插入排序 Bubbl电子排序 选择排序
最好的情况 O（N） O(n) 时间复杂度，带有提前退出标志 O(n²)
平均情况和最坏情况 O(n²) O(n²) O(n²)
额外空间 O（1） O（1） O（1）
稳定 是 是 不，在标准数组版本中
自适应 是 是的，当使用标志优化时。 没有
写入数组 班次很多，但有序数据很少 多次交换 恰好 n-1 次交换

当写入操作成本很高时，选择排序胜出，因为它执行的交换操作最少。插入排序在几乎所有其他情况下都胜出，尤其是在处理部分有序数据时，这也是为什么像后面提到的那种库排序算法如此受欢迎的原因。 常见 Java 演习 JDK 内部机制会在分区非常小时切换到这种模式。

常见问题

第一个元素本身就是一个长度为 1 的已排序子数组。从索引 1 开始循环意味着循环始终有对象可以比较，因此位置 i 处的键会被插入到它左侧的已排序块中。

AI助手可以逐行讲解试运行过程，生成额外的测试数组，并根据源代码估算大O复杂度。请将讲解内容作为学习辅助工具，并在引用之前对照教科书验证其复杂度声明。

是的。 GitHub 副驾驶 根据方法签名或注释完成标准插入排序。 Rev请自行查看边界条件，因为生成的循环有时会使用 j >= 0 或 j > -1，这与周围的代码不一致。

二分插入排序使用二分查找而非线性扫描来定位插入点，将每个元素的比较次数从 O(n) 减少到 O(log n)。移位操作保持不变，因此整体时间复杂度仍然是 O(n²)。

是的。递归版本会先对前 n-1 个元素进行排序，然后将最后一个元素插入到已排序的前缀中。它的时间复杂度与迭代版本相同，但会增加 O(n) 的栈空间，因此在实践中更倾向于使用循环版本。

部分如此。用于基本类型的双枢轴快速排序在非常小的分区上会退而求其次，采用插入式排序；而用于对象的 TimSort 则先用二分插入排序对短序列进行排序，然后再合并它们。

常见的错误是：外层循环从 0 开始，写成 arr[j] = key 而不是 arr[j+1] = key，以及省略 j > -1 保护，当 key 属于位置 0 时会抛出 ArrayIndexOutOfBoundsException 异常。

是的。对于 Comparable 类型，将大于号判断替换为 compareTo 方法；对于 Comparable 类型，则替换为 Comparator 调用。排序逻辑保持不变，稳定性也得以保证，这在对象共享相同排序键时至关重要。

总结一下这篇文章：