当k比较小的时候，可获得O(n)的时间复杂度.
#include
<
iostream
>
using namespace std;
const
int
arrLen
=
5
;
void
countingSort(
int
*
a,
int
*
b,
int
k)
{
//
a数组元素在[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的元素个数
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
豪 阅读(675)
评论(2) 编辑 收藏 引用 所属分类:
算法&ACM