插入排序


插入排序

插入排序,如果你打过扑克,你就会非常熟悉:当我们摸排的时候,第一张牌是 8,第二张牌如果是 7,我们会放在 8 的前面,否则会放到后面。插入排序和这个非常类似。

我们将数组中的元素,分成“已排序区间”和“未排序区间”。

刚开始的时候,已排序区间的个数是 1. 我们从 2 开始,从右往左进行比较,如果后面的较小,就进行交换,直到后面的数字比前面的数字大,就停止比较。

如下图所示:

在第四次比较中,我们将 1 这个元素,逐步移动到了最前面。

在第五次比较中,我们将 3 这个元素,逐步移动到了下标为 1(从 0 开始) 的这个位置。

…….

image-20190731090402490

代码:

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
public class 插入排序 {
public static void main(String[] args) {
int[] arr = {5, 1, 11, 2, 0, 6, 9, 4};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int num = arr[i];
int j = i - 1;
while (j >= 0) {
// 如果该数, 已经比前面的数字大了,就停止循环(因为是升序).
if (arr[j] > num) {
arr[j + 1] = arr[j];
j--;
}
else {
break;
}
}
// + 1; 补偿最后 j--
arr[j + 1] = num;
}
}
}

排序算法三问

1. 是原地排序算法吗?

是的。

2 是稳定的排序算法吗?

只要代码实现时,不要把相等的元素进行调换,就是稳定的。

2. 时间复杂度是多少?

最好时间复杂度,数组本身有序,啥也不干,$O(n)$.

最坏时间复杂度,全部逆序,$O(n^2)$.

平均时间复杂度,我们知道,往有序数组插入一条数据时间复杂度是 $O(n)$.,如果将整个半无序数组遍历一遍进行有序插入,那就是 $O(n^2)$.

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×