将第一个数当做有序序列（从小到大排列），将之后的数挨个插入到此有序序列里边。
插入排序
平均时间复杂度：O(n²)；最好情况：O(n)；最坏情况：O(n²)；
空间复杂度：O(1)
排序方式：In-place
稳定性：稳定
Implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| /**
* 插入排序 从小到大
*
* @author hxr
* @see https://github.com/MisterBooo/LeetCodeAnimation
* 核心：将第一个数当做有序序列（从小到大排列），将之后的数挨个插入到此有序序列里边。
* 每次取有序序列右边的第一个数（记为操作数）插入到有序序列，插入时，从右往左遍历有序序列，并判断操作数与遍历数的大小(1.操作数大，有序序列+操作数依然有序，不再遍历。2.操作数小，遍历数右移，接着遍历)。遍历完成后，将操作数插入到有序序列的准确位置。
* 优点：减少了交换次数
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = { 8, 5, 3, 9, 1, 2, 4 };
for (int i = 1; i < arr.length; i++) {
// 记录有序序列右边的第一个数的数值，此后每趟排序右移一位。
int temp = arr[i];
int j = i;
while(j > 0){
if (temp < arr[j - 1]) {
arr[j] = arr[j - 1];
} else {//比有序序列右边的数大，即比整个有序序列大。不需要再比较。
break;
}
j--;
}
// 下标j以后的数比temp更大,插入到j位置
if (j != i) {
arr[j] = temp;
}
}
// 打印
System.out.println(Arrays.toString(arr));
}
}
|
