​ 每次将一个待排序的记录,按其大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。时间复杂度 T(n) = Θ(n²)。

原理及实现

基本原理:对待排序数组a[n],假设第i(i∈[1,n])个元素左侧已排序,右侧未排序。

  • ① 从i位置左侧已排序数组位置中,逆序遍历,查找元素a[i]的目标位置,即第一个比a[i]小的元素后边targetPos(或者第一个位置)。
  • ② 移动元素:将数组元素[targetPos + 1 .. i - 1] 整体向后移动一位。
  • ③ 将第i(i∈[1,n])个元素a[i]放置到[targetPos + 1]位置。
  • ④ 遍历执行①、②、③操作,直到最后一个元素a[n]。

使用Swift进行功能实现,如下:

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
/**
* 插入排序 - 算法思想
* 对待排序数组a[n],假设第i(i∈[1,n])个元素左侧已排序,右侧未排序。
* ① 从i位置左侧已排序数组位置中,逆序遍历,查找元素a[i]的目标位置,即第一个比a[i]小的元素后边targetPos(或者第一个位置)。
* ② 移动元素:将数组元素[targetPos + 1 .. i - 1] 整体向后移动一位。
* ③ 将第i(i∈[1,n])个元素a[i]放置到[targetPos + 1]位置。
* ④ 遍历执行①、②、③操作,直到最后一个元素a[n]。
*
**/
func insertSort<T: Comparable>(array: inout Array<T>){
let count = array.count;
if count > 1 {
//第i个元素的左侧为有序,右侧为无序。遍历执行操作④
for i in 1 ..< count {
let ai = array[i];

var targetPos = i - 1;
var aj = array[targetPos];
//如果当前元素不小于前一个元素,表明数据已经是有序的,无需后续操作
if ai < aj {
//操作①,查找第一个比a[i]小的元素位置targetPos
while ai < aj && targetPos >= 0 {
targetPos = targetPos - 1;
if targetPos >= 0 {
aj = array[targetPos];
}
}
//操作②,移动元素
for index in (targetPos + 1 ..< i).reversed() {
array[index + 1] = array[index];
}
//操作③,赋值
array[targetPos + 1] = ai;
}
print("第\(i)次处理结果: \(array)")
}
}
}

测试用例及结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//测试用例
var intArray = [16,4,7,9,8,11,11,15,24,1];
print("待排序整形数组:\(intArray)");
insertSort(array: &intArray);

//程序输出
待排序整形数组:[16, 4, 7, 9, 8, 11, 11, 15, 24, 1]
1次处理结果: [4, 16, 7, 9, 8, 11, 11, 15, 24, 1]
2次处理结果: [4, 7, 16, 9, 8, 11, 11, 15, 24, 1]
3次处理结果: [4, 7, 9, 16, 8, 11, 11, 15, 24, 1]
4次处理结果: [4, 7, 8, 9, 16, 11, 11, 15, 24, 1]
5次处理结果: [4, 7, 8, 9, 11, 16, 11, 15, 24, 1]
6次处理结果: [4, 7, 8, 9, 11, 11, 16, 15, 24, 1]
7次处理结果: [4, 7, 8, 9, 11, 11, 15, 16, 24, 1]
8次处理结果: [4, 7, 8, 9, 11, 11, 15, 16, 24, 1]
9次处理结果: [1, 4, 7, 8, 9, 11, 11, 15, 16, 24]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//测试用例
var stringArray = ["Java","C#","Python","Objective-C","Swift","PHP","BASIC","Pasical","Assembly"];
print("待排序字符串数组:\(stringArray)");
insertSort(array: &stringArray);

//程序输出
待排序字符串数组:["Java", "C#", "Python", "Objective-C", "Swift", "PHP", "BASIC", "Pasical", "Assembly"]
1次处理结果: ["C#", "Java", "Python", "Objective-C", "Swift", "PHP", "BASIC", "Pasical", "Assembly"]
2次处理结果: ["C#", "Java", "Python", "Objective-C", "Swift", "PHP", "BASIC", "Pasical", "Assembly"]
3次处理结果: ["C#", "Java", "Objective-C", "Python", "Swift", "PHP", "BASIC", "Pasical", "Assembly"]
4次处理结果: ["C#", "Java", "Objective-C", "Python", "Swift", "PHP", "BASIC", "Pasical", "Assembly"]
5次处理结果: ["C#", "Java", "Objective-C", "PHP", "Python", "Swift", "BASIC", "Pasical", "Assembly"]
6次处理结果: ["BASIC", "C#", "Java", "Objective-C", "PHP", "Python", "Swift", "Pasical", "Assembly"]
7次处理结果: ["BASIC", "C#", "Java", "Objective-C", "PHP", "Pasical", "Python", "Swift", "Assembly"]
8次处理结果: ["Assembly", "BASIC", "C#", "Java", "Objective-C", "PHP", "Pasical", "Python", "Swift"]