Java实现插入排序程序

"这是一个使用Java实现的插入排序程序，作者编写并验证了其可以成功运行。这个程序的主要目的是对用户输入的一组整数进行插入排序，并打印出排序后的结果。" 在Java编程中，插入排序是一种简单直观的排序算法，它的工作原理类似于人们整理扑克牌。在这个程序中，插入排序的实现主要分为以下几个步骤： 1. **数据输入**：程序首先通过`Scanner`类从`System.in`获取用户输入。用户输入一串由空格分隔的整数，例如"5 3 8 1 9"。`String str = input.nextLine();`读取这一行输入，然后使用`split("\\s")`方法将字符串按空格分割成一个字符串数组。 2. **类型转换**：将字符串数组转换为整数数组。遍历字符串数组`a`，用`Integer.parseInt(a[i])`将每个元素转为整数并存储到新的整数数组`b`中。 3. **插入排序**： - 外层循环（`for(int i=1; i<b.length; i++)`）控制遍历整个数组，从第二个元素（下标为1）开始，因为第一个元素默认已经排序好了。 - 内层循环（`while((j>=0)&&(t<b[j]))`）用于找到正确的位置将当前元素`t`插入已排序部分。`t`是当前待插入的元素，`j`是已排序部分的最后一个元素的下标。 - 当找到正确位置时，通过`b[j+1] = b[j];`将已排序部分的元素逐个后移，最后将`t`插入到正确的位置`b[j+1] = t;`。 4. **输出结果**：排序完成后，使用一个简单的`for`循环（`for(int i=0; i<b.length; i++)`）打印出排序后的数组元素。 这个程序展示了插入排序的基本思想和Java实现方式。插入排序的时间复杂度在最好情况下（输入已排序）为O(n)，最坏情况（输入逆序）为O(n^2)，平均情况为O(n^2)。虽然对于大数据集效率较低，但对于小规模或部分有序的数据，插入排序具有较好的性能。