Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1828664
  • 博文数量: 283
  • 博客积分: 10141
  • 博客等级: 上将
  • 技术积分: 2931
  • 用 户 组: 普通用户
  • 注册时间: 2005-12-21 14:33
文章分类

全部博文(283)

文章存档

2013年(2)

2012年(2)

2011年(17)

2010年(36)

2009年(17)

2008年(18)

2007年(66)

2006年(105)

2005年(20)

分类:

2007-06-20 21:49:26

基本的思路是先从list中依次找出两个有序的子list,merge之,再继续找.scan一轮后,进行下一轮的查找,直到发现从list首到list尾为最大的有序子列(即list有序)为止.
额外的空间开销大,但是充分利用了list中的有序部分,减少了扫描次数.
BTW:据说这样的方法适合于并行计算.:)
 
#include
#include
#include
#define MAX_LENGTH 100
/*Show usage*/
void usage(char * prog)
{
        printf("%s Usage:\n", prog);
        printf("%s (should be less than 100)>\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");
}
void merge(int * srclist, int first, int mid, int last)
{
        int * ord_list = (int *)malloc((last - first + 1)* sizeof(int));
        int i = first, j = mid+1, k = 0;
        int t;
        while((i <= mid) && (j <= last))
        {
                if(srclist[i] < srclist[j])
                {
                        ord_list[k] = srclist[i];
                        i ++;
                        k ++;
                }
                else
                {
                        ord_list[k] = srclist[j];
                        j ++;
                        k ++;
                }
        }
        if(i > mid)
        {
                for(t = j; t <= last; t ++)
                {
                        ord_list[k] = srclist[t];
                        k ++;
                }
        }
        else
        {
                for(t = i; t <= mid ; t ++)
                {
                        ord_list[k] = srclist[t];
                        k ++;
                }
        }
        t = first;
        while(t <= last)
        {
                srclist[t] = ord_list[t - first];
                t ++;
        }
        free(ord_list);
}
/*algorithm*/
void merge_sort2(int * list, int length)
{
        while(length > 1)
        {
                int i = 0;
                int j, k;
                do
                {
                        for(j = i; (j < length-1)&&(list[j] <= list[j+1]); j ++);
                        if(j == length-1)
                        {
                                if(i == 0)
                                {
                                        return;
                                }
                                else
                                {
                                        break;
                                }
                        }
                        for(k = j +1; (k < length-1) && (list[k] <= list[k+1]); k ++);
                        merge(list, i, j, k);
                        i = k + 1;
                }while(i <= length-1);
        }
}
int main(int argc, char * argv[])
{
        int length;
        int * list = NULL;
        /*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);
        printf("Source List:\n");
        show_list(list, length);
        merge_sort2(list, length);
        printf("Ordered List:\n");
        show_list(list, length);
        free(list);
        return 1;
}
阅读(1884) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~