Java插入排序
/**
* 插入排序
*
* @author yl
*/
public class InsertSort {
public static void main(String[] args) {
int[] ints = {7, 5, 3, 8};
System.out.println(Arrays.toString(insertSort(ints)));
}
/**
* 插入排序算法
* 类似整理扑克牌,比如有左手有一副牌1,2,4,7 ,来一张3的牌, 是不是就是手拿着这张牌从右往左插到2,4之间
* 一次插入排序的操作过程:
* 将待插元素,依次与已排序好的子数列元素从后到前进行比较,如果当前元素值比待插元素值大,则将移位到与其相邻的后一个位置
* 否则直接将待插元素插入当前元素相邻的后一位置,因为说明已经找到插入点的最终位置
*
* @param ints
* @return
*/
public static int[] insertSort(int[] ints) {
if (ints.length >= 2) {
// 默认ints[0]已经排好序
for (int i = 1; i < ints.length; i++) {
// 要排序的数
int target = ints[i];
// 排序目标前一个数的下标
int j = i - 1;
// 当排序目标比前一个数小,执行排序操作
while (j >= 0 && ints[j] > target) {
// 将排序目标的前一个数往右移动一位
ints[j + 1] = ints[j];
// 继续跟前面的数比较
j--;
}
// 将排序目标插入到目标位置,由于while循环里面j--了,所以目标位置要加1
ints[j + 1] = target;
}
}
return ints;
}
}