算法---1.插入排序

1.1直接插入排序
类似于扑克牌，假设前面的数据都是己排好序的，当下一个数据到来时，
先扫描要插入的位置，然后把数据插入。
1.2 代码

#include <stdio.h>
#include <stdlib.h>
#define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)

int dump_arry(int* arr, int len)
{
    int i;
    for(i=0; i<len; i++)
    {
        //printf("%d=%d ", i, arr[i]);
        printf("%d  ", arr[i]);
    }
    printf("\n");
    return 0;
}
//b.1顺序是不对的，先找到要插入的位置
int get_insert_position(int* arr, int end_pos, int key)
{
    int i;                  //end_pos当前要插入数据的位置
    int start_pos;          //start_pos数据要插入的位置
    //printf("end_pos=%d\n",end_pos);
    for(i=end_pos; i>=0; i--)
    {
        if(arr[i]<key)
            break;
    }

    start_pos = i+1;
    if(i<0)
        start_pos = 0;
    return start_pos;
}
//b.2顺序是不对的，把数据插入到这个位置处
int insert_to_position(int* arr, int start_pos, int end_pos, int key)
{
    int i; //start_pos数据要插入的位置，end_pos当前要插入数据的位置
    for(i=end_pos; i>start_pos; i--)
    {
        arr[i] = arr[i-1];
    }
    arr[start_pos] = key;
    return 0;
}

//按从小到大进行插入排序
int insert_sort(int* arr, int len)
{
    int i;
    int key;
    int pos;
    for(i=1; i<len; i++)
    {
        dump_arry(arr, len);
        if(arr[i] >= arr[i-1])                  //a.顺序是对的，直接跳过
            continue;
        key = arr[i];
        pos = get_insert_position(arr, i-1, key);   //b.1顺序是不对的，先找到要插入的位置
        insert_to_position(arr, pos, i, key);       //b.2顺序是不对的，把数据插入到这个位置处
    }
    return 0;
}

int main ( int argc, char *argv[] )
{
    //int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
    //int arr[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int len = sizeof(arr)/sizeof(int);
    dbmsg("len=%d", len);
    insert_sort(arr, len);  //按从小到大进行插入排序
    dump_arry(arr, len);
    return EXIT_SUCCESS;
}

1.3 运行结果
49  38  65  97  76  13  27  49     -->原始数据 
38  49  65  97  76  13  27  49     -->插入38后,38<49,只需将38与49交换即可
38  49  65  97  76  13  27  49     -->插入65后，不需要移动数据
38  49  65  97  76  13  27  49     -->插入97后  
38  49  65  76  97  13  27  49     -->插入76后,76<97,只需将76与97交换即可  
13  38  49  65  76  97  27  49     -->插入13后,插入13移动的数据比较多  
13  27  38  49  65  76  97  49     -->插入27后 
13  27  38  49  49  65  76  97     -->插入49后
1.4 性能分析
O(n2)