俺写了一个, 没有测试过只有1, 2, 或者0 的情况...
请高手指正...
思路就是维护了三个指针p0, p1, p2, 分别指向了数组index最小的0, 1, 2值所在位置,
然后遍历的过程中,不断swap(值和指针同时swap), 复杂度为O(n), 常数空间.
请高手们多指正了!
#include
#include
using namespace std;
class MITbbSolver
{
public:
MITbbSolver() {}
virtual ~MITbbSolver() {}
public:
void swap_pv(int* &p1, int* &p2) {
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
int* p = p1;
p1 = p2;
p2 = p;
return;
}
void sort_012_array(int* a, int n)
{
if (NULL==a || n<1) return;
int *p1, *p2, *p0;
p0 = p1 = p2 = NULL;
int i;
int* p = NULL, *pcur = NULL;
for (i = 0; i < n; i++) {
if (a[i]==0 && NULL==p0) {
p0 = a + i;
break;
}
}
if (p0 != a) {
pcur = a;
swap_pv(p0, pcur);
}
for (pcur = p0; pcur < a + n; pcur++) {
if (*pcur==1 && NULL==p1) {
p1 = pcur;
}
if (*pcur==2 && NULL==p2) {
p2 = pcur;
}
}
if (p1==NULL && p2==NULL) {
return;
}
if (p1 > p2) {
swap_pv(p1, p2);
}
for (pcur = p1; pcur < a + n; pcur++) {
if (*pcur==2) {
p2 = pcur;
break;
}
}
for (i = 0; i < n; i++) {
p = a + i;
if (*p==0 && p>p1) {
pcur = p;
if (pcur > p1) {
swap_pv(pcur, p1);
p1 = pcur + 1;
}
if (p1 > p2) {
swap_pv(p1, p2);
p2 = p1 + 1;
}
}
if (*p==1 && p>p2) {
pcur = p;
if (pcur > p2) {
swap_pv(pcur, p2);
p2 = pcur + 1;
}
}
} //for//
return;
}
void test_sort_012_array()
{
int a[] = {0, 2, 2, 2, 1, 1, 1, 0, 1, 2, 0, 0, 2, 2, 1, 1};
int n = sizeof(a) / sizeof(a[0]);
// original
copy(a, a+n, ostream_iterator(cout, " "));
cout << endl;
sort_012_array(a, n);
// sorted result
copy(a, a+n, ostream_iterator(cout, " "));
cout << endl;
return;
}
};