常用的排序算法（二）——插入排序

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

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

用C语言实现如下：

#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;
}