13 调整数组顺序使奇数位于偶数前面

题目描述

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

示例：

输入: [1, 2, 3, 4, 5, 6]
输出: [1, 3, 5, 2, 4, 6]

输入: [2, 4, 6, 1, 3, 5]
输出: [1, 3, 5, 2, 4, 6]

解题思路

方法一：双指针（不稳定）

核心思想：使用双指针，一个从前往后找偶数，一个从后往前找奇数，交换。

• 缺点：不稳定，会改变相对顺序

方法二：空间换时间（稳定）

核心思想：创建新数组，先存奇数再存偶数。

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

方法三：类似插入排序（稳定，O(1)空间）

核心思想：类似插入排序，找到偶数后向后查找奇数，插入到前面。

Python 实现

# 方法一：空间换时间
def re_order_array(nums):
    """
    稳定版本，使用额外空间
    """
    if not nums:
        return nums

    # 分别收集奇数和偶数
    odds = [x for x in nums if x % 2 == 1]
    evens = [x for x in nums if x % 2 == 0]

    return odds + evens


# 方法二：双指针（不稳定）
def re_order_array_unstable(nums):
    """
    不稳定版本，双指针交换
    """
    if not nums:
        return nums

    left, right = 0, len(nums) - 1

    while left < right:
        # 从左找偶数
        while left < right and nums[left] % 2 == 1:
            left += 1
        # 从右找奇数
        while left < right and nums[right] % 2 == 0:
            right -= 1

        if left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    return nums


# 方法三：类似插入排序（稳定，O(1)空间）
def re_order_array_stable(nums):
    """
    稳定版本，类似插入排序
    """
    if not nums:
        return nums

    k = 0  # 记录当前奇数的位置

    for i in range(len(nums)):
        if nums[i] % 2 == 1:
            # 如果是奇数
            temp = nums[i]
            j = i
            # 将偶数向后移动
            while j > k:
                nums[j] = nums[j - 1]
                j -= 1
            nums[k] = temp
            k += 1

    return nums


# 测试代码
if __name__ == "__main__":
    test_cases = [
        [1, 2, 3, 4, 5, 6],
        [2, 4, 6, 1, 3, 5],
        [1, 3, 5, 2, 4, 6],
        [],
    ]

    for case in test_cases:
        print(f"原数组: {case}")
        print(f"结果:   {re_order_array(case[:])}")
        print()

图解

方法一（空间换时间）示例:
输入: [1, 2, 3, 4, 5, 6]

步骤1: 遍历数组，奇数: [1, 3, 5], 偶数: [2, 4, 6]
步骤2: 拼接: [1, 3, 5] + [2, 4, 6]
结果: [1, 3, 5, 2, 4, 6]

方法二（双指针）示例:
输入: [1, 2, 3, 4, 5, 6]

初始: left=0, right=5
step1: left停在1(偶数), right停在5(奇数), 交换 → [1,5,3,4,2,6]
step2: left停在3(偶数), right停在3(奇数), 交换 → [1,5,3,4,2,6]
step3: left=right, 结束
结果: [1, 5, 3, 4, 2, 6] (顺序变了！)

方法三（插入排序）示例:
输入: [1, 2, 3, 4, 5, 6]

i=0: nums[0]=1是奇数, k=1
i=1: nums[1]=2是偶数, 跳过
i=2: nums[2]=3是奇数, 插入到k=1的位置 → [1,3,2,4,5,6], k=2
i=3: nums[3]=4是偶数, 跳过
i=4: nums[4]=5是奇数, 插入到k=2的位置 → [1,3,5,2,4,6], k=3
i=5: nums[5]=6是偶数, 跳过
结果: [1, 3, 5, 2, 4, 6] (顺序保持)