算法题:如何对包含一万个元素为1或0的数组进行排序?(0和0一起在前面或者后面)

Question

要求:
1.不能用快排,
2.for嵌套不超过2个
3.不产生中间数组
4.用算法实现,或者写出实现思路

Answer 1

左右逼近，找到能交换的就交换

#include <stdio.h>

void sort01(int* datas, int len) {
    int i = 0;
    int j = len-1;

    while(i < j) {
        if (datas[i] == 0) {
            i++;
            continue;
        }

        if (datas[j] == 1) {
            j--;
            continue;
        }

        datas[i] = 0;
        datas[j] = 1;
        i++;
        j--;
    }
}


int main() {

    int datas[] = {1,0,0,0,1,0,1,0,1};
    int len = sizeof(datas)/sizeof(datas[0]);

    sort01(datas,len);

    for(int i=0; i<len; i++) {
        printf("%d",datas[i]);
    }

    return 0;
}