排序与算法：插入排序

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

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

算法介绍
插入排序（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;
}

程序实现如下：