alogrithm

gistfile1.txt

// 已知数组 A[1··n]的元素类型为整型 int，设计一个时间和空间上尽可能高效的算法
// 将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，不要求对这些元素排序
// (1) 给出算法的基本设计思想:
// (2) 根据设计思想，采用 c 语言表述算法，关键之处给出注释:
// (3) 说明你所设计算法的时间复杂度和空间复杂度。
#include <iostream>
#include <vector>
#include <random>
using namespace std;

bool JAO(int a){
    if(a % 2 == 1){
        return 1;//jishu
    }
    else{
        return 0;//oushu
    }
}
template <typename T>
void dividedDate(std::vector<T> &A){
    int i = 0;
    int j = A.size();
    while(i < j){
        if(JAO(A[i]) == 0 && JAO(A[j]) == 1){
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            i++;
            j--;
        }
        else if(JAO(A[i]) == 1 && JAO(A[j]) == 0){
            i++;
            j--;
        }
        else if(JAO(A[i]) == 0  && JAO(A[j]) == 0){
            j--;
        }
        else if(JAO(A[i]) == 1  && JAO(A[j]) == 1){
            i++;
        }
    }
}
int main(){
    std::vector<int> A;
    std::random_device rd;  // 以获得随机数种子
    std::mt19937 gen(rd()); // 生成随机数的引擎
    std::uniform_int_distribution<> dis(0, 100); // 定义一个范围为 [0, 100] 的均匀分布

    for (int i = 0; i < 100; ++i) {
        A.push_back(dis(gen)); // 用随机数填充向量
    }
    dividedDate(A);
    for(int i =0 ;i < A.size();i++){
        std::cout<<A[i]<<" ";
    }
}


//空间复杂度:O(n)，时间复杂度O(n)

@Gavin0x0

@Gavin0x0
有没有好的思路，能把时间复杂度压缩到O(log2n)