[Algorithm]Sort an array with space complexity is O(1) and time complexity is O(n)

[wutiejun]

[Algorithm]Sort an array with space complexity is O(1) and time complexity is O(n) such that all the elements in array at left is add, and the elements at right is even.

// Left is Odd and right is even
void SortForOdd(int *pA, int MaxNum)
{
    int MaxIndex = MaxNum - 1;
    int LeftIndex = 0;
    int RightIndex = MaxIndex;
    int Temp = 0;

    // assert(MaxNum >= 1)

    while (LeftIndex <= RightIndex)
    {
        if (pA[LeftIndex] % 2 != 0)
        {
            LeftIndex ++;
            continue;
        }
        if (pA[RightIndex] % 2 == 0)
        {
            RightIndex --;
            continue;
        }

        Temp = pA[LeftIndex];
        pA[LeftIndex] = pA[RightIndex];
        pA[RightIndex] = Temp;

        LeftIndex ++;
        RightIndex --;
    }
    return ;
}

TEST(SortForOdd, Test001)
{
    int Array[10] = {3, 4, 1, 6, 7, 9, 10, 2, 5, 8};
    int index = 0;
    SortForOdd(Array, 10);
    for(index = 0; index <10; index ++)
    {
        if (index < 10/2)
        {
            EXPECT_EQ(1, Array[index]%2);
        }
        else
        {
            EXPECT_EQ(0, Array[index]%2);
        }
    }
}

int main(int argc, char* argv[])
{
    cout << "Hello world!" << endl;
    testing::InitGoogleTest(&argc, argv);
    ::testing::GTEST_FLAG(filter) = "SortForOdd.Test001";
    return RUN_ALL_TESTS();
}

[wutiejun]

各种排序的比较： https://www.toptal.com/developers/sorting-algorithms