當(dāng)k比較小的時(shí)候，可獲得O(n)的時(shí)間復(fù)雜度.
#include?
<
iostream
>
using?namespace?std;
const
?
int
?arrLen?
=
?
5
;
void
?countingSort(
int
?
*
a,?
int
?
*
b,?
int
?k)?
{
????
//
a數(shù)組元素在[0..k]
????
int
?i,?j;
????
int
?
*
c?
=
?
new
?
int
[k
+
1
];
????
for
?(i
=
0
;?i
<=
k;?i
++
)?c[i]?
=
?
0
;
????
for
?(i
=
0
;?i
<
arrLen;?i
++
)?c[a[i]]
++
;
????
//
包含小于或等于i的元素個(gè)數(shù)
????
for
?(i
=
1
;?i
<=
k;?i
++
)?c[i]?
+=
?c[i
-
1
];
????
for
?(j
=
arrLen
-
1
;?j
>=
0
;?j
--
)?
{
????????b[c[a[j]]
-
1
]?
=
?a[j];
????????c[a[j]]
--
;
????}
}
int
?main()?
{
????
int
?a[arrLen]?
=
?
{
4
,?
4
,?
3
,?
1
,?
1
}
;
????
int
?b[arrLen];
????countingSort(a,?b,?
5
);
????
for
?(
int
?i
=
0
;?i
<
5
;?i
++
)?
{
????????printf(
"
%d?
"
,?b[i]);
????}
????printf(
"
\n
"
);
????system(
"
pause
"
);
}
posted on 2007-02-06 20:43
豪 閱讀(695)
評(píng)論(2) 編輯 收藏 引用 所屬分類:
算法&ACM