原理
外层循环:确定要与已排序元素进行比较的元素,它是未排序元素中的第一个元素
内层循环:将未排序元素中要比较的元素与已排序元素以从后到前的顺序、进行相邻元素的比较,较小元素放到前面
外层循环原理图
内层循环原理图
示例
package wxw.mengyuan;
/**
* 堆代码 duidaima.com
* 插入排序
*/
public abstract class InsertSorting {
/**
* 对数组中的元素进行排序
*
* 原理
* (1) 外层循环:确定未排序元素中的第一个元素
* (2) 内层循环:将该未排序元素与已排序元素从后到前一一比较
*
* @param arr 要排序的数组
*/
public static void sort(Comparable[] arr) {
// 外层循环:确定未排序元素中的第一个元素
for (int i = 1; i < arr.length; i++) {
// 内层循环:将该未排序元素与已排序元素从后到前一一比较
for (int j = i; j > 0; j--) {
if (greater(arr[j-1], arr[j])) {
exch(arr, j-1, j);
} else {
// 当前一个元素比后一个元素小时,那么再前面的元素就不需要再比较了
break;
}
}
}
}
/**
* 校验第一个元素是否比第二个元素大
*
* @param v 第一个元素
* @param w 第二个元素
*/
private static boolean greater(Comparable v, Comparable w) {
return v.compareTo(w) > 0;
}
/**
* 将数组中索引为i、j的两个元素交换位置
*
* @param arr 数组
* @param i 索引i
* @param j 索引j
*/
private static void exch(Comparable[] arr, int i, int j) {
Comparable temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}