算法---2.希尔排序

1.1 希尔排序
希尔排序也是一个插入排序，
1  6   进行插入排序
2  7   进行插入排序
3  8   进行插入排序
4  9   进行插入排序
5   10   进行插入排序

1   4  7  10   进行插入排序
2   5   8        进行插入排序
3   6   9        进行插入排序

1 2 3 4 5 6 7 8 9 10   进行插入排序

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;
}

int get_insert_position(int* arr, int end_pos, int key, int dlta)
{
    int i;
    int start_pos;
    //dbmsg("end_pos=%d\n",end_pos);
    for(i=end_pos; i>=0; i-=dlta)
    {
        if(arr[i]<key)
            break;
    }

    start_pos = (i+1)*dlta;
    if(i<0)
        start_pos = end_pos;
    return start_pos;
}

int insert_to_position(int* arr, int start_pos, int end_pos, int key, int dlta)
{
    int i;
    //dbmsg("start=%d,end=%d,key=%d,dlta=%d", start_pos, end_pos, key, dlta);
    for(i=end_pos; i>start_pos; i-=dlta)
    {
        arr[i] = arr[i-dlta];
    }
    arr[start_pos] = key;
    return 0;
}

int shell_insert(int* arr, int len, int dlta)
{
    int i,j;
    int key;
    int pos;
    for(i=0; i<dlta; i++)
    for(j=i+dlta; j<len; j+=dlta)
    {
        if(arr[j] >= arr[j-dlta])
            continue;
        //dbmsg("arr[%d]=%d, arr[%d]=%d", j-dlta, arr[j-dlta], j, arr[j]);
        key = arr[j];
        pos = get_insert_position(arr, j-dlta, key, dlta);
        //dbmsg("j=%d, key=%d, pos=%d", j, key, pos);
        insert_to_position(arr, pos, j, key, dlta);
        dump_arry(arr, len);
    }
    return 0;
}

//small --> big
int shell_sort(int* arr, int len)
{
    int dlta;
    //for(dlta=len/2; dlta>0; dlta/=2)
    for(dlta=5; dlta>0; dlta-=2)   //delta这儿默认取5,3,1
    {
        dbmsg("----------------------->dlta=%d", dlta);
        dump_arry(arr, len);
        shell_insert(arr, len, dlta);
    }
    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 len = sizeof(arr)/sizeof(int);
    dbmsg("len=%d", len);
    shell_sort(arr, len);
    dump_arry(arr, len);
    return EXIT_SUCCESS;
}

1.3 运行结果

shell.c:main[85]: len=10
shell.c:shell_sort[73]: ----------------------->dlta=5
49 38  65  97  76 13 27  49  55  4
13  38  65  97  76  49  27  49  55  4
13  27  65  97  76  49  38  49  55  4
13  27  49  97  76  49  38  65  55  4
13  27  49  55  76  49  38  65  97  4
13  27  49  55  4  49  38  65  97  76
shell.c:shell_sort[73]: ----------------------->dlta=3
13  27  49  55  4  49  38  65  97  76
13  27  49  38  4  49  55  65  97  76
13  4  49  38  27  49  55  65  97  76
shell.c:shell_sort[73]: ----------------------->dlta=1
13  4  49  38  27  49  55  65  97  76
4  13  49  38  27  49  55  65  97  76
4  13  38  49  27  49  55  65  97  76
4  13  27  38  49  49  55  65  97  76
4  13  27  38  49  49  55  65  76  97
4  13  27  38  49  49  55  65  76  97

1.4性能分析
不能分析的原因见《数据结构 c语言版》 严蔚敏 P272
1.5 代码下载
最近cu插入代码会丢数据，直接下载代码了。
shell.rar(下载后改名为shell.tar.gz)