|
|
Posted on 2007-05-12 23:49 花之剑 阅读(2738) 评论(0) 编辑 收藏 所属分类: c/c++ & algorithm
1 #include<iostream>
2#include<stdlib.h>
3#include<time.h>
4const int N = 8;
5  /**//////////
6 ///This function is to output the array
7 //////// 8void outArray(int *a)
9 {
10 for(int j = 0;j < N;j++)
11  {
12 printf("%d ",a[j]);
13 }
14 printf("\n");
15}
16/**///////////
17////This can merge a array which is devided by the middle one,
18////and either side is ordered
19/////////
27
void Merge(int *a,int p,int q,int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int *L = new int[n1];
int *R = new int[n2];
int i = 0;int j = 0;
28 for(int m = 0;m < n1;m++)
29 {
30 L[m] = a[p + m];
31 }
32 for(int n = 0;n < n2;n++)
33 {
34 R[n] = a[q + n + 1];
35 }
36 int k = p;
37 for(k;k <= r;k++)
38 {
39 if(L[i] <= R[j])
40 {
41 a[k] = L[i++];
42 }
43 else
44 {
45 a[k] = R[j++];
46 }
47 if((i >= n1) || (j >= n2))
48 break;
49 }
50 while(i >= n1 && j < n2) //when one side is over,
51 { //then there is no need to compare
52 a[++k] = R[j++];
53 }
54 while(i < n1 && j >= n2)
55 {
56 a[++k] = L[i++];
57 }
58}
59/**/////////
60////This is the function which is to call the Merge
61//////// 62void Merge_Sort(int *a,int p,int r)
63{
64 int q;
65 if(p < r)
66 {
67 q = (p + r) / 2;
68 Merge_Sort(a,p,q);
69 Merge_Sort(a,q + 1,r);
70 Merge(a,p,q,r);
71 }
72}
73/**////////
74///This can output the array befor merge and merged one
75////// 76void test(int *a)
77{
78 outArray(a);
79 Merge_Sort(a,0,7);
80 outArray(a);
81}
82/**/////////
83///This can produce a array in random
84/////// 85void pro_Array(int *a)
86{
87 time_t t;
88 srand((unsigned)time(&t));
89 for(int i = 0;i < N;i++)
90 a[i] = rand() % 100;
91}
92int main()
93{
94 int a[N] = {2,4,5,7,1,2,3,6};
95 int b[N] = {3,41,52,26,38,57,9,15};
96 int c[N] = {45,3,12,67,8,6,2,9};
97 int d[N];
98 pro_Array(d);
99 printf("First one:\n");
100 test(a);
101 printf("Second one:\n");
102 test(b);
103 printf("Third one:\n");
104 test(c);
105 printf("Fourth one:\n");
106 test(d);
107 return 0;
108}
插入排序和合并排序的算法复杂度分别为n*n 和nlgn 这是在最坏情况下的定义 在输入规模大的时候.建议采用合并排序,速度比插入排序.
|