经典算法之插入排序(Insertion Sort)

发表于 | 分类于

原理

设有一组关键字 {K1, K2, …, Kn}; 排序开始就认为K1是一个有序的序列，使之成为一个表厂为2的有序序列；然后让K3插入上述表长为2的有序序列，使之成为一个表长为3的有序序列，以此类推，最后让Kn插入上述表长为n-1的有序序列，得一个表长为n的有序序列。

具体可以表述为下：

  1. 从第一个元素开始，该元素可以认为已经排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素，将该元素移到下一个位置
  4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置
  5. 将新元素插入该位置后
  6. 重复步骤2～5

举例说明：要排序数组：int[] arr = {6, 3, 8, 2, 9, 1};

第一趟排序：原始数据： 6 3 8 2 9 1 i=0
从第一个元素开始，该元素可以认为已经排序
排序结果： 6 3 8 2 9 1

第二趟排序： 6 3 8 2 9 1 i=1
排序结果：3 6 8 2 9 1

第三趟排序：3 6 8 2 9 1 i=2
排序结果：3 6 8 2 9 1

第四趟排序：3 6 8 2 9 1 i=3
排序结果：2 3 6 8 9 1

第五趟排序：2 3 6 8 9 1 i=4
排序结果：2 3 6 8 9 1

第六趟排序：2 3 6 8 9 1 i=5
排序结果：1 2 3 6 8 9

最终结果：1 2 3 6 8 9

注：(红色代表此轮要插入的元素，红色左边是已经排好序的，右边是待排序的)

时间复杂度

在最坏情况下，数组完全逆序，插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，……，插入第n个元素，要考虑前 n - 1 个元素。因此，最坏情况下的比较次数是 1 + 2 + 3 + … + (n - 1)，等差数列求和，结果为 n2 / 2，所以最坏情况下的复杂度为 O(n2)

最好情况下，数组已经是有序的，每插入一个元素，只需要考查前一个元素，因此最好情况下，插入排序的时间复杂度为O(n)

平均时间复杂度为：O(n2)

所以，综上，插入排序的时间复杂度为 O(n2)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static void InsertionSortTest(int[] nums) {
	if (nums.length < 1) {
		return;
	}
	for (int i = 1; i < nums.length; i++) {
		for (int j = i; j > 0; j--) {
			if (nums[j] < nums[j - 1]) {
				swapNums(nums, j, j - 1);
			}
		}
	}
}

private static int[] swapNums(int[] nums, int i, int j) {
//		int tmp = nums[i];
//		nums[i] = nums[j];
//		nums[j] = tmp;

	nums[i] = nums[i] ^ nums[j];
	nums[j] = nums[i] ^ nums[j];
	nums[i] = nums[i] ^ nums[j];
	return nums;
}