/**/
/*
合并排序
*/
#include
<
iostream
>
using
namespace
std;
template
<
class
T
>
void
Merge(T c[], T d[],
int
l,
int
m,
int
r)
{
int
i
=
l, j
=
m
+
1
, k
=
l;
while
(i
<=
m
&&
j
<=
r)
{
if
(c[i]
<=
c[j])
{
d[k
++
]
=
c[i
++
];
}
else
{
d[k
++
]
=
c[j
++
];
}
}
if
(i
>
m)
{
for
(; j
<=
r; j
++
)
{
d[k
++
]
=
c[j];
}
}
else
{
for
(; i
<=
m; i
++
)
{
d[k
++
]
=
c[i];
}
}
}
template
<
class
T
>
void
Copy(T c[], T d[],
int
l,
int
r)
{
int
i;
for
(i
=
l; i
<=
r; i
++
)
{
c[i]
=
d[i];
}
}
template
<
class
T
>
void
MergePass(T a[], T b[],
int
l,
int
r)
{
int
m;
if
(l
<
r)
{
m
=
(l
+
r)
/
2
;
MergePass(a, b, l, m);
MergePass(a, b, m
+
1
, r);
Merge(a, b, l, m, r);
Copy(a, b, l, r);
}
}
template
<
class
T
>
void
MergeSort(T a[],
int
n)
{
T
*
b
=
new
T[n];
MergePass(a, b,
0
, n
-
1
);
}
int
main()
{
int
i, j;
int
a[]
=
{
5
,
9
,
3
,
7
,
1
}
;
MergeSort(a,
5
);
for
(i
=
0
; i
<
5
; i
++
)
{
printf(
"
%d
"
, a[i]);
}
printf(
"
\n
"
);
system(
"
pause
"
);
}
posted on 2006-10-10 01:11
豪 阅读(1471)
评论(1) 编辑 收藏 引用 所属分类:
数据结构与算法