题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

1、遍历算法

使用一个列表变量存数，先按顺序存奇数，再按顺序存偶数

class Solution:
    def reOrderArray(self, array):
        # write code here
        # 1 2 3 4 5 6 7 8 9
        # 1 3 5 7 9 2 4 6 8
        # space complexity O(n)
        # time complexity O(n)

        ret = []
        for i in array:
            if i % 2 == 1:
                ret.append(i)
        for i in array:
            if i % 2 == 0:
                ret.append(i)
                
        return ret

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

2、冒泡排序

知识点讲解参考：
三分钟彻底理解冒泡排序 - stone1234567890 - 博客园

冒泡排序及优化详解

排序算法之 冒泡排序 及其时间复杂度和空间复杂度

class Solution:
    def reOrderArray(self, array):
        # write code here
        # 1 2 3 4 5 6 7 8 9
        # 1 3 5 7 9 2 4 6 8

        # bubble_sort
        # time complexity O(n^2)
        # space complexity O(1)

		# 这里不论是len(array)还是len(array)-1都可以，区别是是否再对比最后一个， 之前的n-1排完后，最后一个已经确定运不运行结果都是相同的
        for i in range(len(array)-1):
            for j in range(len(array)-i-1):
                if array[j] % 2 == 0 and array[j+1] % 2 ==1:
                    array[j],array[j+1] = array[j+1],array[j]
        return array

平均时间复杂度为O(n²)，最优为O(n²)，最坏为O(n²)
空间复杂度为O(1)，最优为O(0)，最坏为O(n)