算法2.5 Shell排序(ShellSort)

Shell排序把list划分成了M个子序列，不再基于相邻元素之间的比较和交换， 而是每隔几个数字进行比较和交换，当然，当划分的distance为1的时候，就成了insertsort了。这样的好处在于，每一次交换和移动，可能减少M个逆序。

 

#include
#include
#include
#include
#include

#define MAX_LENGTH 100

/*Show usage*/
void usage(char * prog)
{
        printf("%s Usage:\n", prog);
        printf("%s \n", prog);
}

/*Generate and initialize the list*/
int * generate_list(int count)
{

        int i;
        int * list;
        list = (int *)malloc(count*sizeof(int));
        if(list == NULL)
        {
                perror("malloc");
                return NULL;
        }

        /*Initialize the list with integers less than 100*/
        srandom((unsigned int)time(NULL));
        for (i  = 0; i < count ; i ++)
                list[i] = random()%100;

        return list;
}

/*Show the list*/
void show_list(int * list, int length)
{
        int i;
        for(i = 0; i < length; i ++)
                printf("%d      ", list[i]);

        printf("\n");
}

/*algorithm*/
void shell_sort(int * list, int length, int tag, int * distance)
{
        int d, s;
        int i, k, j, temp;
        for(d = distance[tag-1], s = tag -1; s >= 0; s --, d = distance[s])
        {
                for(k = 1; k <= d ; k ++)
                {
                        for(i = d + k -1; i < length; i += d)
                        {
                                temp = list[i];
                                j = i - d;
                                while((list[j] > temp) && (j >= 0))
                                {
                                        list[j + d] = list[j];
                                        j -= d;
                                }
                                list[j + d] = temp;
                        }
                }
        }

        printf("Ordered list:\n");
        show_list(list, length);
}

int main(int argc, char * argv[])
{
        int length, i;
        int * list = NULL;
        struct timeval tpstart,tpend;
        float timeuse;
        int * distance =NULL;
        int tag;

        /*Deal with the arguments*/
        if(argc != 2)
        {
                usage(argv[0]);
                exit(127);
        }

        length = atoi(argv[1]);
        if(!length || length > MAX_LENGTH)
        {
                usage(argv[0]);
                exit(129);
        }

        list = generate_list(length);
        if(list == NULL)
                exit(128);
        else
        {
                tag = (int)sqrt(length);
                if(tag * tag < length)
                        tag ++;

                distance = (int *)malloc(tag * sizeof(int));
                for(i = 0; i < tag; i ++)
                        distance[i] = i + 1;
                printf("Soruce list:\n");
                show_list(list, length);

                gettimeofday(&tpstart,NULL);
                shell_sort(list, length, tag, distance);
                gettimeofday(&tpend,NULL);
                timeuse=1000000*(tpend.tv_sec-tpstart.tv_sec)+ tpend.tv_usec-tpstart.tv_usec;
                timeuse/=1000;
                printf("time used: %f msec\n", timeuse);
        }

        free(list);

        free(distance);
        return 1;

}