Java插入排序
public class InsertionSort {
public static void insertionSort(int[] arr) {
//默认索引0的元素已排序，从索引1开始
for (int low = 1; low < arr.length; low++) {
int temp = arr[low];
int i = low - 1;
// 自右向左找插入位置，如果比待插入元素大，则不断右移，空出插入位置
while (i >= 0 && temp < arr[i]) {
arr[i + 1] = arr[i];
i--;
}
// 找到插入位置, 此处不加判断也可
if (i != low - 1) {
arr[i + 1] = temp;
}
}
}
// 相比较第一种方法的缺点: 赋值次数较多
public static void insertionSort2(int[] arr) {
for (int low = 1; low < arr.length; low++) {
int i = low - 1;
while (i >= 0 && arr[i] > arr[i + 1]) {
//交换位置
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
i--;
}
}
}
// 和上述两种相比，先找到已排序的区间
public static void insertionSort3(int[] arr) {
//1.找到第一个无序是从哪个索引开始的
int startIndex = -1;
for (int i = 0; i < arr.length; i++) {
if(arr[i] > arr[i + 1]){
startIndex = i + 1;
break;
}
}
//2.从无序的startIndex开始遍历
for (int i = startIndex; i < arr.length; i++) {
//记录当前要插入数据的索引
int j = i;
while(j > 0 && arr[j] < arr[j - 1]){
//交换位置
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
}
public static void main(String[] args) {
int[] arr1 = {8, 6, 7, 5, 3, 1, 2, 4};
System.out.println("原始数组: " + Arrays.toString(arr1));
// 调用插入排序方法
insertionSort(arr1);
System.out.println("排序后数组: " + Arrays.toString(arr1) + "\n");
int[] arr2 = {8, 6, 7, 5, 3, 1, 2, 4};
System.out.println("原始数组2: " + Arrays.toString(arr2));
// 调用插入排序方法2
insertionSort2(arr2);
System.out.println("排序后数组2: " + Arrays.toString(arr2) + "\n");
int[] arr3 = {8, 6, 7, 5, 3, 1, 2, 4};
System.out.println("原始数组3: " + Arrays.toString(arr3));
// 调用插入排序方法3
insertionSort3(arr3);
System.out.println("排序后数组3: " + Arrays.toString(arr3));
}
}