今天，AC在程痴群问到一个问题：如何用O(N+K)时间，O(K)辅助空间完成对N个关键字范围为[0,K)的项的基数排序？想了一下，主要难点在O(K)空间上，也就是说，你不能另开一个大小为N的数组（否则就是无敌BC题了）。想了一下，得算法如下。
容易想到用基数排序，但由于题目限制不能用链表或数组将其全部收集起来，便想到用数组本身做收集器，这样问题就变成如何处理将被收集的项与未被排序的项的空间冲突问题了。方法也很简单，将这两项交换，则原来将被收集的项被移到该它的归宿地，而那时的未排序项则成为下一个将被收集的项。
具体代码如下，我用了一个c[]数组统计各关键字拥有的项的数目，然后自然可以O(K)地求出所有队列的首地址和尾地址（初始时两者相等，因为所有收集队列皆空）
然后用i指针去扫描数组，若发现一个未被排序的项——其特征是所处下标比其收集队列的首地址还小，则将其与收集队列的尾地址上的项交换，同时将收集队列的尾指针加1。这样当i扫描到数组尾时，排序也就完成了。
初看代码时看到for里边有个while，很容易误以为是O（N^2）的算法，但实际上它是O(N)的，证明方法很简单：对于数组中的任意一个项，它都不会被移动超过2次，不会比j指针访问超过1次，不会比i指针访问超过2次。
/**/
/*
解决：用O(N+K)时间，O(K)辅助空间完成对N个关键字范围为[0,K)的项的基数排序
最后更新：07-01-22
提问者：AC
*/
#include
<
cstdio
>
#include
<
cstring
>
typedef
int
T;
//
定义排序类型,以int为例
int
key(T item)
{
//
对T类型定义关键字
return
item;
}
T a[]
=
{
1
,
0
,
2
,
0
,
2
,
2
,
1
,
1
}
;
//
待排序数组
const
int
N
=
sizeof
(a)
/
sizeof
(
*
a);
const
int
K
=
3
;
//
排序关键字范围[0,K)
int
c[K];
//
队列计数器
int
b[K];
//
排序队列头指针
int
e[K];
//
排序队列尾指针
void
sort()
{
int
i,j;
memset(c,
0
,
sizeof
(c));
for
(i
=
0
; i
<
N;
++
i) c[key(a[i])]
++
;
for
(b[
0
]
=
e[
0
]
=
0
,i
=
1
; i
<
K;
++
i) b[i]
=
e[i]
=
b[i
-
1
]
+
c[i
-
1
];
for
(i
=
0
; i
<
N;
++
i)
{
while
(i
<
b[key(a[i])])
{
//
a[i]的位置不合法
j
=
e[key(a[i])]
++
;
//
j指向a[i]所属队列尾
T tmp
=
a[j]; a[j]
=
a[i]; a[i]
=
tmp;
//
交换a[i],a[j]
}
}
}
#include
<
iostream
>
using
namespace
std;
int
main()
{
sort();
for
(
int
i
=
0
; i
<
N;
++
i) cout
<<
a[i]
<<
'
'
;
cout
<<
'
'
;
return
0
;
}
如果你有别的算法，或者发现文中的错漏，请不吝赐教！谢谢！
posted on 2007-01-22 02:33
踏雪赤兔 阅读(1235)
评论(2) 编辑 收藏 引用 所属分类:
玩转编程