常用的排序算法(二)——插入排序

插入排序的平均时间复杂度为O(nn),最好的情况下为O(n),最坏情况为O(nn)。

其基本机理与我们平时打牌时整理手中的牌的做法差不多。把小的牌插到左边,大的牌往右边移。

用C语言实现如下:

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
#include <stdio.h>
void print_list(int *list, int n)
{
int i;
printf("[ ");
for (i=0; i<n; i++) {
printf("%d ", list[i]);
}
printf("]\n");
}
void insertion_sort(int *base, int len)
{
int i, j, n;
int value;
for (j=1; j<len; j++) {
i = j - 1;
value = base[j];
while (i>=0 && base[i] > value) {
base[i+1] = base[i];
i--;
}
base[i+1] = value;
printf("step %d:", j);
print_list(base, len);
}
}
int main(int argc, char *argv[])
{
int a[] = {5, 2, 4, 6, 1, 3};
int len = sizeof(a) / sizeof(int);
insertion_sort(a, len);
return 0;
}