常用排序算法1---插入排序法

 void insertion_sort(char array[], int first, int last)
 {
        int i,j;
        int temp;
        for (i = first+1; i<=last;i++)
        {
                temp = array[i];
                j=i-1;
 
                //與已排序的數逐一比較，大於temp時，該數向後移
                while((j>=first) && (array[j] > temp))  

               //当first=0，j循环到-1时，由于[[短路求值]]，不会运算array[-1]
                {
                        array[j+1] = array[j];
                        j--;
                }
                array[j+1] = temp;      //被排序数放到正确的位置
 
        }
 }

    如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是
升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进
行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n2)。
    因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，
那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算
法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。