/**/
/*
合并排序?
*/
#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
豪 閱讀(1494)
評論(1) 編輯 收藏 引用 所屬分類:
數據結構與算法