0%

排序-插入排序

发表于 更新于 分类于

概念

插入排序是插入类的排序算法，基本原理：将一个记录插入到已经排好序的有序表中，从而得到一个新的记录数增加1的有序表。

具体算法：
整个序列分为两部分，左边部分为已排序的子序列，右边部分为未排序的子序列，取出第1个未排序元素存放在临时变量tmp中，在已经排序的元素序列中从后往前遍历，逐一比较，如果遍历到的元素大于tmp，则将该元素替换下一个位置的元素，直至遍历到的元素小于或等于tmp为止。相当于将未排序的第一个元素插入到已排序的数组中，故以插入排序为名。

演示

比如我们待排序的数组是 {0, 5, 3, 4, 6, 2}
第1趟排序，5大于0，无需插入： 0 5 3 4 6 2
第2趟排序，3小于5，需要插入： 0 3 5 4 6 2
第3趟排序，4小于5，需要插入： 0 3 4 5 6 2
第4趟排序，6大于5，无需插入： 0 3 4 5 6 2
第5趟排序，2小于6，需要插入： 0 2 3 4 5 6

Java实现

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
38
39
40
41
// 定义接口
interface Sorter {
	/**
	 * 将数组按升序排序
	 */
	int[] sort(int[] arr);

	/**
	 * 交换数组arr中的第i个位置和第j个位置的关键字
	 */
	default void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}
//插入排序
class InsertSorter implements Sorter {

	@Override
	public int[] sort(int[] arr) {
		insertSort(arr);
		return arr;
	}

	private void insertSort(int[] arr) {
		int len = arr.length;
		int i, j;
		int tmp;
		for (i = 1; i < len; i++) { // 从下标1开始遍历,因为下标0的已经排好序
			if (arr[i] < arr[i - 1]) {
				// 如果当前下标对应的记录小于前一位记录,则需要插入,否则不需要插入，直接将记录数增加1
				tmp = arr[i]; // 记录下标i对应的元素
				for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
					arr[j + 1] = arr[j]; // 记录后移
				}
				arr[j + 1] = tmp; // 插入正确位置
			}
		}
	}
}

复杂度

时间复杂度：
最好情况：当待排序的序列为顺序表时，会进行n-1次比较，0次替换，复杂度为O(n)；
最坏情况：当待排序的序列为逆序表时，会进行2+3+…+n=(n+2)*(n-1)/2次比较，2+3+…+n = (n+2)*(n-1)/2次替换，复杂度为O(n^2)；
平均情况：平均比较次数约为n^2/2, 平均移动次数为n^2/2，复杂度为O(n^2)。

空间复杂度：
最好情况=最坏情况=平均情况=O(1)