最后有改进版
算法思路
- 将一个要排序的序列分为"已排序"，"未排序"两部分
- 把未排序的序列的元素依次取出，插入已排序序列中
算法实现
完整代码
建议复制完整代码然后对照着后面的具体步骤
import java.util.Arrays;
public class InsertSortDemo {
private static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private static void insertSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j > 0; j--) {
if (nums[j] < nums[j - 1]) {
swap(nums, j, j - 1);
} else {
break;
}
}
}
}
public static void main(String[] args) {
int[] nums = {4, 5, 2, 3, 6, 7, 9, 8, 1, 4, 5, 1, 7, 9, 6, 5, 8};
System.out.println(Arrays.toString(nums));
insertSort(nums);
System.out.println(Arrays.toString(nums));
}
}
核心思想
- 每次从"未排序"序列中取出元素(实际上两个序列都在数组中，这里说的取出只是方便理解)，插入"已排序"序列时，假如是升序排序，如果从"已排序"序列末端往前端逐个扫描，只要取出的元素比被扫描到的元素小，就交换位置，直到取出元素比扫描到的元素大，则停下(因为这是个"已排序"的序列，所以只要比被扫描到的元素大，则比该元素往前的都大)，直接进入下一轮
- 指定数组第一个元素为初始"已排序"序列
具体步骤
-
void swap(int[] nums, int i, int j)是一个辅助方法，交换数组元素 -
void insertSort(int[] nums)是排序方法(升序排序)-
for (int i = 0; i < nums.length - 1; i++)外层循环表示过程需要"数组长度 - 1"次循环，因为默认第一个元素作为"已排序"序列，剩下元素作为"未排序"序列 -
for (int j = i + 1; j > 0; j--)表示内层每一轮循环，从"未排序"序列第一个元素开始，所以第一次是索引j = 0 + 1，j--表示每次是从"已排序"序列的后往前扫描的，由于交换元素的时候可能与第一个"已排序"序列第一个元素，所以内层循环变量j要> 0而不是>= 0 -
if (nums[j] < nums[j - 1]) { swap(nums, j, j - 1); }这个逐个往前交换的过程实际上就是插入，不满足条件时break
-
测试
排序前：[ 4, 5, 2, 3, 6, 7, 9, 8, 1, 4, 5, 1, 7, 9, 6, 5, 8 ]
排序后：[ 1, 1, 2, 3, 4, 4, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 ]
----------------------------华丽的分割线--------------------------------
上面写的插入排序使用类似冒泡的方法，把插入的数往"已排序"序列中间插入的，性能有点拉垮，改进一下，上面的方法是每次发现比插入数大的，就交换两个数，新方法用一个待插入的索引
insertIndex，用它指向可能要往后挪的数，先看完整代码吧
private static void insertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int insertValue = nums[i];
int insertIndex = i - 1;
while (insertIndex >= 0 && nums[insertIndex] > insertValue) {
nums[insertIndex + 1] = nums[insertIndex];
insertIndex--;
}
if (insertIndex != i - 1) {
nums[insertIndex + 1] = insertValue;
}
}
}
-
insertValue保存本轮要插入的数 -
insertIndex指向可能要插入的位置
演示过程
{1, 3, 4, 2}，把2插入前面时，insertIndex指向4，4 > 2，则nums[insertIndex + 1] = nums[insertIndex]，数组变成{1, 3, 4, 4}，然后insertIndex指向3，3 > 2则再次赋值，数组变成{1, 3, 3, 4}，然后insertIndex指向1，此时1 < 2，跳出循环
nums[insertIndex + 1] = insertValue赋值时索引 + 1是因为insertIndex指向了要插入的前一个位置，插入后{1, 2, 3, 4}
插入时判断insertIndex != i - 1索引是否为初始值，如果是则说明本轮不需要插入，也就是待插入的数比"已排序"的所有数都大，则排最后即可
测试的时候发现性能足足提高到原来的两倍多，啧啧啧
