数组奇偶重排算法：双指针与稳定排序实战-AI智能范式网

数组奇偶重排算法：双指针与稳定排序实战

智芯融·2026-08-30·阅读 23 GEO检测（免费）

数组重排双指针算法稳定排序

|难度：普通|阅读约 9 分钟

1. 项目概述：调整数组顺序使奇数位于偶数前面

在编程面试和算法练习中，"调整数组顺序使奇数位于偶数前面"是一个经典的数组操作问题。这个看似简单的问题背后，蕴含着对数组操作、指针运用和算法效率的深刻理解。作为一线开发者，我在实际工作中多次遇到类似的数据重组需求，比如日志分类、用户分组等场景。

问题的核心要求是：给定一个整数数组，将所有奇数移动到数组的前半部分，所有偶数移动到数组的后半部分，同时保持奇数之间和偶数之间的相对顺序不变。例如，输入数组 [1,2,3,4,5] 经过处理后应该变成 [1,3,5,2,4]。这与简单的奇偶分类不同，因为我们需要保持原始顺序，这增加了问题的复杂度。

需要模型API调用？免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。

2. 解决方案设计与思路拆解

2.1 暴力解法与空间换时间

最直观的解法是创建两个临时数组，分别存放奇数和偶数，最后合并它们。这种方法时间复杂度为O(n)，空间复杂度也是O(n)。虽然简单易懂，但在内存受限的场景下可能不是最优解。

python复制def reorder_array_extra_space(nums):
    odds = [x for x in nums if x % 2 == 1]
    evens = [x for x in nums if x % 2 == 0]
    return odds + evens

注意：这种方法虽然空间效率不高，但在实际工程中，当内存不是瓶颈时，这种清晰易懂的代码往往更受欢迎。可读性有时比微小的性能提升更重要。

2.2 原地交换的双指针法

更高效的解法是使用双指针进行原地交换，无需额外空间。基本思路是：

初始化两个指针：i从前往后找偶数，j从后往前找奇数
当i找到偶数且j找到奇数时，交换它们
重复直到i >= j

python复制def reorder_array_in_place(nums):
    i, j = 0, len(nums) - 1
    while i < j:
        while i < j and nums[i] % 2 == 1:
            i += 1
        while i < j and nums[j] % 2 == 0:
            j -= 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    return nums

然而，这种方法会破坏奇数和偶数各自的相对顺序。例如，输入[1,2,3,4,5]可能输出[1,5,3,4,2]，这不符合题目要求。

2.3 保持相对顺序的稳定排序法

为了保持相对顺序，我们可以利用稳定的排序特性。自定义一个排序键，使得所有奇数都"小于"偶数：

python复制def reorder_array_stable(nums):
    return sorted(nums, key=lambda x: x % 2 == 0)

这种方法简洁但时间复杂度为O(nlogn)，不是最优解。我们需要寻找线性时间的稳定重排方法。

3. 最优解法：类插入排序法

3.1 算法思路

我们可以模仿插入排序的思想：

记录当前已排好序的奇数末尾位置
遍历数组，遇到奇数时就"插入"到已排序奇数的末尾
通过元素后移保持偶数顺序不变

python复制def reorder_array(nums):
    if not nums:
        return nums
    
    # 已排序奇数的末尾位置
    last_odd_pos = -1
    
    for i in range(len(nums)):
        if nums[i] % 2 == 1:
            # 找到奇数，需要移动到last_odd_pos后面
            last_odd_pos += 1
            # 保存当前奇数
            current_odd = nums[i]
            # 将last_odd_pos到i-1的元素后移一位
            for j in range(i, last_odd_pos, -1):
                nums[j] = nums[j-1]
            # 将奇数放到正确位置
            nums[last_odd_pos] = current_odd
    return nums

3.2 复杂度分析

时间复杂度：O(n²) - 最坏情况下每次奇数都需要移动大量元素
空间复杂度：O(1) - 原地操作，仅使用常数额外空间

虽然时间复杂度较高，但这是保持相对顺序的线性空间解法。在实际应用中，当数组不大时，这种方法的性能是可以接受的。

4. 线性时间复杂度的稳定重排算法

4.1 基于队列的解法

我们可以通过两次遍历实现线性时间复杂度：

第一次遍历收集所有奇数
第二次遍历收集所有偶数
将结果写回原数组

python复制def reorder_array_linear(nums):
    if not nums:
        return nums
    
    result = []
    # 第一次遍历收集奇数
    for num in nums:
        if num % 2 == 1:
            result.append(num)
    # 第二次遍历收集偶数
    for num in nums:
        if num % 2 == 0:
            result.append(num)
    # 写回原数组
    for i in range(len(nums)):
        nums[i] = result[i]
    return nums

4.2 复杂度分析

时间复杂度：O(n) - 三次线性遍历
空间复杂度：O(n) - 需要额外存储结果

这是典型的空间换时间策略，适合处理大规模数据且内存充足的情况。

5. 实际应用中的变种与扩展

5.1 通用条件重排框架

我们可以将奇偶判断抽象为更通用的条件函数，使代码更灵活：

python复制def reorder_by_condition(nums, condition):
    return [x for x in nums if condition(x)] + [x for x in nums if not condition(x)]

# 使用示例：奇数在前
reorder_by_condition(nums, lambda x: x % 2 == 1)

5.2 多条件分类

当需要按多个条件分类时（如正负数、能被3整除等），可以扩展为多段分组：

python复制def multi_condition_reorder(nums, conditions):
    groups = [[] for _ in range(len(conditions) + 1)]
    for num in nums:
        placed = False
        for i, cond in enumerate(conditions):
            if cond(num):
                groups[i].append(num)
                placed = True
                break
        if not placed:
            groups[-1].append(num)
    return [num for group in groups for num in group]

5.3 并行处理优化

对于超大数组，可以考虑并行处理：

python复制from multiprocessing import Pool

def parallel_reorder(nums, condition, chunk_size=10000):
    def process_chunk(chunk):
        return (
            [x for x in chunk if condition(x)],
            [x for x in chunk if not condition(x)]
        )
    
    chunks = [nums[i:i+chunk_size] for i in range(0, len(nums), chunk_size)]
    with Pool() as pool:
        results = pool.map(process_chunk, chunks)
        odds = [num for chunk_odds, _ in results for num in chunk_odds]
        evens = [num for _, chunk_evens in results for num in chunk_evens]
        return odds + evens

6. 性能对比与选型建议

方法	时间复杂度	空间复杂度	保持顺序	适用场景
暴力解法	O(n)	O(n)	是	小数据量，代码可读性优先
双指针交换	O(n)	O(1)	否	不需要保持顺序，内存敏感
稳定排序	O(nlogn)	O(n)	是	需要简洁代码，性能非关键
类插入排序	O(n²)	O(1)	是	小数据量，内存敏感
线性队列法	O(n)	O(n)	是	大数据量，内存充足

在实际工程中选择方案时，需要考虑：

数据规模：小数据量可用简单方法，大数据量需考虑线性时间算法
内存限制：嵌入式系统可能更关注空间效率
顺序要求：是否需要保持原始相对顺序
代码维护：团队熟悉度和代码可读性

7. 常见问题与调试技巧

7.1 边界条件处理

空数组输入：应直接返回空数组
全奇数或全偶数数组：应返回原数组
包含0的数组：0是偶数，应归到偶数部分

python复制# 边界测试用例
test_cases = [
    ([], []),
    ([1,3,5], [1,3,5]),
    ([2,4,6], [2,4,6]),
    ([1,2,3,4,5,0], [1,3,5,2,4,0])
]

7.2 性能优化技巧

预分配数组大小：避免动态扩容开销
使用生成器表达式：减少内存使用
位运算优化：用x & 1代替x % 2判断奇偶

python复制# 位运算优化示例
def is_odd(x):
    return x & 1

7.3 调试日志

在复杂算法中添加调试日志：

python复制def reorder_array_debug(nums):
    print(f"原始数组: {nums}")
    last_odd_pos = -1
    for i in range(len(nums)):
        if nums[i] % 2 == 1:
            last_odd_pos += 1
            print(f"发现奇数 {nums[i]} 在位置 {i}, 移动到 {last_odd_pos}")
            current_odd = nums[i]
            for j in range(i, last_odd_pos, -1):
                nums[j] = nums[j-1]
            nums[last_odd_pos] = current_odd
            print(f"移动后数组状态: {nums}")
    return nums

8. 语言特性与库函数利用

8.1 Python中的高效实现

利用列表推导式和内置函数：

python复制def reorder_array_pythonic(nums):
    return list(filter(lambda x: x % 2 == 1, nums)) + list(filter(lambda x: x % 2 == 0, nums))

8.2 C++中的稳定分区

C++标准库提供了stable_partition算法：

cpp复制#include <algorithm>
#include <vector>

void reorderArray(std::vector<int>& nums) {
    auto is_odd = [](int x) { return x % 2 != 0; };
    std::stable_partition(nums.begin(), nums.end(), is_odd);
}

8.3 Java中的流处理

Java 8+可以使用Stream API：

java复制import java.util.Arrays;
import java.util.stream.Stream;

public static int[] reorderArray(int[] nums) {
    return Stream.concat(
        Arrays.stream(nums).filter(x -> x % 2 != 0).boxed(),
        Arrays.stream(nums).filter(x -> x % 2 == 0).boxed()
    ).mapToInt(Integer::intValue).toArray();
}

9. 测试策略与验证方法

9.1 单元测试设计

全面的测试应包含：

正常情况测试
边界条件测试
性能测试
随机测试

python复制import unittest
import random

class TestReorderArray(unittest.TestCase):
    def test_empty(self):
        self.assertEqual(reorder_array([]), [])
    
    def test_all_odd(self):
        self.assertEqual(reorder_array([1,3,5]), [1,3,5])
    
    def test_random_case(self):
        nums = [random.randint(0, 100) for _ in range(100)]
        expected = [x for x in nums if x % 2 == 1] + [x for x in nums if x % 2 == 0]
        self.assertEqual(reorder_array(nums.copy()), expected)

9.2 性能基准测试

使用timeit模块比较不同实现的性能：

python复制import timeit

def benchmark():
    setup = """
from __main__ import reorder_array, reorder_array_linear, reorder_array_pythonic
import random
nums = [random.randint(0, 10000) for _ in range(10000)]
    """
    stmt1 = "reorder_array(nums.copy())"
    stmt2 = "reorder_array_linear(nums.copy())"
    stmt3 = "reorder_array_pythonic(nums.copy())"
    
    t1 = timeit.timeit(stmt1, setup, number=100)
    t2 = timeit.timeit(stmt2, setup, number=100)
    t3 = timeit.timeit(stmt3, setup, number=100)
    
    print(f"类插入排序: {t1:.3f}s")
    print(f"线性队列法: {t2:.3f}s")
    print(f"Pythonic方法: {t3:.3f}s")

10. 工程实践中的经验总结

在实际项目中应用此类算法时，有几个关键经验值得分享：

明确需求细节：确认是否真的需要保持相对顺序，这个要求会极大影响算法选择
考虑数据特性：如果知道数据中奇数/偶数的分布比例，可以针对性优化
权衡时空效率：在内存受限环境中，可能不得不接受更高的时间复杂度
代码可读性：算法题追求极致效率，但工程代码需要兼顾可维护性
测试覆盖率：边界条件测试尤为重要，特别是0值、空数组等特殊情况

我曾在一个日志处理系统中应用类似算法，最初使用了不保持顺序的双指针法，结果导致日志时间顺序错乱，给问题排查带来了很大困扰。后来改用稳定重排算法，虽然性能略有下降，但保证了日志的时序正确性，这个经验让我深刻理解了需求细节的重要性。