排序与算法：插入排序

执行效果
插入排序的执行效果是这样的：

呃……看不懂吗？没关系，接着往下看介绍 

算法介绍
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用原地排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
如果对插入排序的效率不是很满意，还可以看下它的改进版：希尔排序。

算法档案
时间复杂度：O(n2)
最优时间复杂度：O(n)
平均时间复杂度：O(n2)
空间复杂度：总共 O(n)，需要辅助空间 O(1)
稳定性：稳定

算法步骤
从第一个元素开始，该元素可以认为已经被排序

• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果该元素（已排序）大于新元素，将该元素移到下一位置
• 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
• 将新元素插入到该位置后
• 重复步骤 2~5，直到所有元素排序完毕

算法实现

#include <stdio.h>void insertion_sort(int array[], int length);void insertion_sort(int array[], int length){int i, j, temp;for (i = 1; i < length; i++){temp = array[zxsq-anti-bbcode-i];j = i - 1;for ( ; j >= 0 && array[zxsq-anti-bbcode-j] > temp; j--){array[j+1] = array[zxsq-anti-bbcode-j];}array[j+1] = temp;}
}int main(void)
{int array[] = {73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109};int i, length;length = sizeof(array) / sizeof(array[zxsq-anti-bbcode-0]);insertion_sort(array, length);printf("排序后的结果是：");for (i = 0; i < length; i++){printf("%d ", array[zxsq-anti-bbcode-i]);}putchar('\n');return 0;
}

程序实现如下：