插入排序 insertsort的C实现

    插入排序是一种比较适合人类思维的排序方法。平时打扑克的时候，大家都是习惯把当前的摸到的扑克插入到已经排好的扑克之中，本质就是一种插入排序。

    插入排序的思想就是，新的元素插入之前，我的数组是已序的，这需要把新元素插入到已序数组的合适位置即可。

    当然插入排序效率不高，对于大规模的随机数据，不能采用这种方法，但是这也不是说插入排序一无是处，下面两种情况完全可以采用插入排序。

     1 小规模的排序，比如数组只有十几个元素，或者几十个元素。，所以很多复杂排序算法，递归到数组个数比较小的时候，停止递归，采用插入排序，能够减少函数调用，同时提高效率。参见前文提到的归并排序mergesort的C实现

     2 如果数组几乎排好序了，采用插入排序性能也不错，哪怕数组规模很大。下一篇博文三者取中快速排序会提到。

     下面的代码首先遍历一遍数组，选择最小的元素放在最左边left，作为一个观察哨。

     如果没有这个观察哨，我们总要判断 j 是否大于left，每次都要判断，影响性能。有个观察哨，我们不需要关心j 是否大于left，因为当前要插的元素，不会比left位置上的更小 。

   

 参考文献：

 1算法：C语言实现  Robert Sedgewick著，霍红卫译

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

 void swap(int *a,int *b)
{
    int   t = *a;
     *a = *b;
     *b = t;
}

int insertsort(int array[],int left,int right)
{
    int i;
    int j;
    int cur;

    /*find the min element ,put it in the leftest position, use it as a guard*/
    for(i = right;i>left;i--)
    {
      if(array[i] < array[i-1])
         swap(&array[i],&array[i-1]);
    }

    for( i = left + 2; i <= right;i++)
    {
        cur = array[i];
        j = i;

        while(cur < array[j-1])
        {
           array[j] = array[j-1]; /*比当前元素大的，往右移，给当前元素腾位置*/
           j--;
        }
        array[j] = cur;
    }
}


int test_insertsort(int number)
{
    int i;

    int *array = malloc(number*sizeof(int));
    if(array == NULL)
    {
          printf("malloc failed\n");
          return -1;
    }


    printf("----------------------------------------before insert sort----------\n");
    srand(time(NULL));
    for(i = 0;i<number;i++)
    {
        if(number < 100)
            array[i] = rand()%1000;
        else
            array[i] = rand();
        printf("\tarray[%-6d] = %-6d\n",i,array[i]);
    }

    printf("----------------------------------------after insert sort-----------\n");

    insertsort(array,0,number-1);

    if(number < 25)
    {
        for(i = 0;i<number;i++)
        {
            printf("\tarray[%-6d] = %-6d\n",i,array[i]);
        }
    }

    for( i = 0 ; i < number-1;i++)
    {
         if(array[i] > array[i+1])
         {
             printf("insert sort failed \n");
             break;
         }
    }

    free(array);
    return 0;

}

int main(int argc,char *argv[])
{
    if(argc != 2)
    {
        printf("usage : ./test  number\n");
        return -1;
    }

    int number = atoi(argv[1]);
    if(number <= 0)
    {
         printf("number is 0,please input a big number \n");
         return -2;
    }

    test_insertsort(number);
}