1, 直接插入法：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。由于碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

实现思路：

1,把第一个数看成有序序列，从数组第二个开始向后遍历，即i=1，外层循环标识并决定待比较的数值，内层循环为待比较数值确定其最终位置;

2,当从第i个数向前遍历时，将a[i]保存在temp中，然后令j=i，首先temp与第(j-1)个数比较

    (1)如果temp>a[j-1]，说明序列已经有序，i++进入下一个循环外；

    (2)如果temp<a[j-1], 将a[j-1]后移，j--进入下一个内循环，最终将temp存人合适位置；

    (3)进行(1)(2)步骤，直到排序完成；

原始数据：

1, i=1, temp=a[i]=10;  由于j=i , temp>a[j-1]=6, 此时(i++)-->2

2,初始 i=2, temp=a[i]=4;

 (1) 由于j=i=2, temp<a[j-1]=10, 此时a[j-1]后移，a[j]=a[j-1], (j--)-->1

(2)j=1, temp<a[j-1]=6, 此时a[j-1]后移，a[j]=a[j-1], (j--)-->0， a[j]=temp, 循环退出

代码实现：

void simple_insertSort(int array[], int n){    int i, j, temp;    for(i=1; i<n; i++)    {        temp = array[i];        for(j=i; j>0; j--)        {             if(temp < array[j-1])                 array[j] = array[j-1];             else                 break;        }        array[j] = temp;    }}

2, 希尔排序法：将无序数组分割为若干个子序列，序列按照一定间隔(d)分成子序列，并对子序列进行插入排序；然后再选择一个更小的间隔(d=d/2)，再将数组分割为多个子序列进行排序，最后选择增量为1，此时可以直接使用“直接插入排序”，使最终数组获得有序序列。

 希尔排序法过程：

5　　10　　8　　60　　3　　1　　90　　7

第一次分组：间隔为8/2=4

5------------------------3

-----10-----------------------1

------------8-----------------------90

-----------------60-----------------------7

排序后：

3　　1　　8　　7　　5　　10　　90　　60

第二次分组：间隔4/2=2

3----------8----------5-----------90

-----1----------7----------10------------60

排序后：

3　　1　　5　　7　　8　　10　　90　　60

第三次分组：间隔2/2=1，直接使用“直接插入法”

3----1----5----7----8----10----90----60

排序后：

1　　3　　5　　7　　8　　10　　60　　90　　

实现代码：

/************************************************************************************** *  Description: *   Input Args: *  Output Args: * Return Value: *************************************************************************************/int shell_sort (int* s, int len){    int d;    int i,temp,j;    d = len / 2;    while(d > 0)    {        i = d;        while(i < len)        {            j = i;            while(j > 0)            {                if(s[j-d] > s[j])                                {                    temp = s[j-d];                    s[j-d] = s[j];                    s[j] = temp;                    j = j-d;                }                else                    break;            }            i++;        }        d = d / 2;    }    return 0;} /* ----- End of shell_sort()  ----- */

参考链接：

http://blog.csdn.net/wswifth/article/details/5829156

http://blog.csdn.net/cjf_iceking/article/details/7951481

排序算法： 插入排序法（直接插入法和希尔排序法）