常用算法之插入排序

代码可以在此项目中找到:CommonArithmetic

插入排序,从第二个数开始,拿出当前需要插入的值,认为它之前的数组都是已经排好序的,然后往前面找位置插入,然后往后遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void insertSort(int[] array) {
final int size = array.length;
for (int i = 1; i < size; i++) {
//当前需要插入的数字
final int current = array[i];
int insertIndex = 0;
for (int j = i - 1; j >= 0; j--) {
if (array[j] > current) {
//如果后面的数字大于当前需要插入的数字,就把这个数往后挪一个
//一直挪到我当前插入数字的index上
array[j + 1] = array[j];
} else {
//一样大或者比插入数字小的话,就每次记录一下,记到最后一个的时候就是需要插入的位置的前一个
insertIndex = j + 1;
//第一次找到比要插入数字小就跳出
break;
}
}
//找到插入位置之后插入那个位置
//如果是要插入的数字是最小的,那么insertIndex就是-1(else语句一次都没执行到),如果是最大的,那么insertIndex就是i-1,就是else每次都执行到了
array[insertIndex] = current;
}
}

OK,写完收工!