test21_调整数组顺序使奇数位于偶数前.py

'''
题目：输入一个整数数组，实现一个函数调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于后半部分。

思路：
①从头开始遍历，遇到偶数就移到最后面。时间复杂度和空间复杂度都为O(n)，但是是稳定的，即移动后奇数相对于奇数、偶数相对偶数位置是不变的；
②找两个指针分别放在头部cur1和尾部cur2，若cur1指的是偶数，cur2指的是奇数，则交换元素，时间复杂度为O(log n )，但是是不稳定的
③特殊用例：传入的是空数组；传入的列表只有一个元素；所有的偶数都在前半部分

变体：
①改成负数都在非负数前面
②能被3整除的数都在不能被3整除数的前面
'''
def reOrderArray(array):
    if len(array)==0:return 
    #############################################################################################################
    # 方法一，稳定解法
    # ret = []
    # for i in array:
    #     if i%2==1:
    #         ret.append(i)
    # for i in array:
    #     if i%2==0:
    #         ret.append(i)
    # return array
    #############################################################################################################
    
    #############################################################################################################
    # 方法二，时间复杂度低，但是不稳定
    cur1, cur2 = 0, len(array)-1
    while cur1<cur2:
        if array[cur1]%2==0 and array[cur2]%2==1:
            array[cur1], array[cur2] = array[cur2], array[cur1]
            cur1 += 1; cur2 -= 1
        elif array[cur1]%2==0 and array[cur2]%2==0:
            cur2 -= 1
        elif array[cur1]%2==1 and array[cur2]%2==1:
            cur1 += 1
        else:
            cur1 += 1; cur2 -= 1
    return array
    #############################################################################################################

print(reOrderArray([1,2,3,4,5,6]))
print(reOrderArray([4,2,6,8,1,3,5,7,9]))
print(reOrderArray([]))