数据结构: 判断下面代码段的复杂度

Question

今天写了一个代码段：代码实现的功能是将一个数组中的所有奇数移到偶数前面。有个要求是复杂度为n，不太确定是不是n，求大佬们帮忙讲解下。

Answer 1

先说程序的复杂度：两层for循环，虽然第二层for循环是从i+1开始的，其实可以忽略，故总的复杂度为O(n^2)。
复杂度为O(n)的算法是：使用两个指针 i 和 j，i从前往后遍历，直到 i 指向偶数，j 从后往前遍历，直到 j 指向奇数，
每次 i 和 j 符合条件的时候交换，然后重复操作，一直到 i >= j ，这样遍历数组一次，复杂度为O(n)。