[Algo]dutch flag problem# JobHunting - 待字闺中
d*w
1 楼
简单型：sort 0， 1数组， O(n)时间，可以使用头尾两个pointer，
i = 0;
j = n-1;
while( i < j){
while( array[i] == 0 && i < j )
i++;
while( array[j] == 1 && j > i )
j--;
if ( i < j )
swap( a[i], a[j] );
}
如果是排序0，1，2数组，就是dutch flag问题， http://en.wikipedia.org/wiki/Dutch_national_flag_problem，跟quicksort中的partition类似
void threeWayPartition(int data[], int size, int low, int high) {
int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] < low) {
swap(data[i], data[++p]);
++i;
} else if (data[i] >= high) {
swap(data[i], data[--q]);
} else {
++i;
}
}
}
扩展问题
1）如果是n个数字呢，基数排序
2）如果要保证in order呢？
3）让0，1相间排列，如果多余0或1就放在尾部，保证O(n)时间，不使用辅助空间，
i.e.
input: 0 1 1 1 0 0 1 1 1 0
output: 0 1 0 1 0 1 0 1 1 1
i = 0;
j = n-1;
while( i < j){
while( array[i] == 0 && i < j )
i++;
while( array[j] == 1 && j > i )
j--;
if ( i < j )
swap( a[i], a[j] );
}
如果是排序0，1，2数组，就是dutch flag问题， http://en.wikipedia.org/wiki/Dutch_national_flag_problem，跟quicksort中的partition类似
void threeWayPartition(int data[], int size, int low, int high) {
int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] < low) {
swap(data[i], data[++p]);
++i;
} else if (data[i] >= high) {
swap(data[i], data[--q]);
} else {
++i;
}
}
}
扩展问题
1）如果是n个数字呢，基数排序
2）如果要保证in order呢？
3）让0，1相间排列，如果多余0或1就放在尾部，保证O(n)时间，不使用辅助空间，
i.e.
input: 0 1 1 1 0 0 1 1 1 0
output: 0 1 0 1 0 1 0 1 1 1
