算法导论 第二章插入排序实现
插入排序算法是时间复杂度为 $O(n)$，输入规模$n$较小时，插入排序往往能有较好的效果。
最优情况：数据整体有序，无需须交换元素，时间复杂度$O(n)$
最坏情况：数据整体逆序，每个元素要 $1~n-1$次，时间复杂度为 $O(n^2)$。
插入排序中的常数因子较小使得在$n$在较小的时候，在很多情况能够运行更快。作为归并排序，快速排序等算法在小规模时处理的问题时的子程序。
书中的伪代码1
2
3
4
5
6
7
8
9INSERTION-SORT(A)
1 for j = 2 to A.length
2 key = A[j]
3 //Insert A[j] into the sorted sequence[1..j-1]
4 i = j-1
5 while i > 0 and A[i] > key
6 A[i+1] = A[i]
7 i = i+1
8 A[i+1] = key
具体实现：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/*
数组存放位置为[0,len-1]
*/
class InsertSort{
public:
//升序
static void InsertSortInc(int A[],int len){
for(int j=1;j<len;++j){
int i=j-1;
int key=A[j];
while(i>=0&&A[i]>key){
A[i+1]=A[i];
--i;
}
A[i+1]=key;
}
}
//降序
static void InsertSortDec(int A[],int len){
for(int j=1;j<len;j++){
int i=j-1;
int key=A[j];
while(i>=0&&A[i]<key){
A[i+1]=A[i];
--i;
}
A[i+1]=key;
}
}
};