Windows还是Linux?

人生是无法阻止的前进! 酒醒诗残梦断,南国正清秋。把剑凄然望,无处归舟。
随笔 - 9, 文章 - 10, 评论 - 1, 引用 - 0
数据加载中……

合并排序法(转载自csdn)

合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做排序,引入一个辅助过程merger(A,p,q,r),其中A是个数组,pqr是下标, 满足p<= q < r。该过程假设A[p..q]和A[q+1..r]都已排序,并将它们合并成一个已经排好序的子数组代替当前子数组A[p..r]
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 void merger(int * A,int p,int q,int r);
 4 void mergerSort(int * A,int p,int r);
 5 int main()
 6 {
 7         int A[10= {0};
 8         int i = 0;
 9 
10         for(i = 0;i < 10;i++)
11         {
12                 scanf("%d",A + i);
13         }
14         
15         printf("输入为:\n");
16         for(i = 0;i < 10;i++)
17         {
18                
19                 printf("%d",A[i]);
20         }
21         mergerSort(A,0,9);
22         printf("\n排序后:\n");
23         for(i = 0;i < 10;i++)
24         {
25                 printf("%d",A[i]);
26         }
27         printf("\n");
28         return 0;
29 }
30 void merger(int * A,int p,int q,int r)
31 {
32         int n1 = q - p + 1;
33         int n2 = r - q ;
34         int i = 0,k = 0,j = 0;
35         int * L = (int*)malloc(sizeof(int* n1 + 1);
36         int * R = (int *)malloc(sizeof(int* n2 + 1);
37         for(i = 0;i < n1;i++)
38         {
39                 L[i] = A[p + i];
40         }
41         L[i] = 99999;
42         for(i = 0;i < n2;i++)
43         {
44                 R[i] = A[q + i + 1];
45         }
46         R[i] = 99999;
47         i = j = 0;
48         
49         for(k = p;k <= r;k++)
50         {
51                 if(L[i] < R[j])
52                 {
53                         A[k] = L[i];
54                         i++;
55                 }
56                 else
57                 {
58                         A[k] =  R[j];
59                         j++;
60                 }
61         }
62        free(R);
63        free(L);
64 }
65 void mergerSort(int * A,int p,int r)
66 {
67         int mid = 0;
68         if(p < r)
69         {
70                 mid = (r + p) / 2;
71                 mergerSort(A,p,mid);
72                 mergerSort(A,mid + 1,r); 
73                 merger(A,p,mid,r);
74         }
75 

运行结果:
chu@szcdebian:~/code/merge-sort$ gcc -o merge merge-sort.c
chu@szcdebian:~/code/merge-sort$ ./merge
9 0 6 8 7 3 4 2 5 1
输入为:
9068734251
排序后:
0123456789
chu@szcdebian:~/code/merge-sort$ 

posted on 2010-10-11 16:57 向前看勿回头 阅读(519) 评论(1)  编辑 收藏 引用

评论

# re: 合并排序法(转载自csdn)  回复  更多评论   

35、36行应该是这样吧?
int * L = (int *)malloc(sizeof(int) * (n1 + 1));
int * R = (int *)malloc(sizeof(int) * (n2 + 1));
2011-04-28 11:55 | crescents

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理