基础排序算法之插入排序

一、直接插入排序

算法描述：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置中
6. 重复步骤2

void insert_sort(int *ar, int ilen)

{

    int i,j,guard = 0;

    for(i=0; i < ilen; i++) {

            guard  = ar[i];

            for (j= i; j > 0 && guard < ar[j-1]; j--)

                ar[j] = ar[j-1];

            ar[j] = guard;

    }

}

时间复杂度 ：O(n2) 

空间复杂度：O(1)

稳定性排序

二、希尔排序

插入排序的改进，又叫缩小增量排序。它的主要思想是把待排序列划分为各个子序列，子序列的元素都是由待排序列中相互隔“某一增量”的元素组成。给子序列做插入排序。然后缩小增量再排序，直到增量为1。当增量为1的情况，就是给这个待排序列做直接插入排序。但是这时候序列基本有序，所以排序很快。

void shell_sort(int *ar, int ilen)

{

    int d = ilen / 2 + 1;

    int i, j, itemp;

    while(d) {

        for(i = d; i < ilen; i++) {

            itemp = ar[i];

            for(j = i; j >= d && itemp < ar[j-d]; j-=d){

                ar[j] = ar[j-d];

            }

            ar[j] = itemp;

        }

        if(1 == d)

            break;

        if(2 == d)

            d = 1;

        d = d/2 + 1;

    }

}

时间复杂度： O(n log² n)

空间复杂度：O(1)

非稳定性排序