如何用递归实现字符数组的全排列（Java）

碧海醫心 2025-12-29 00:00:00 次阅读

本文详解如何使用递归方法生成字符数组的所有排列，基于heap算法实现高效、无重复的全排列输出，并提供可运行代码与关键逻辑说明。

在Java中，通过递归生成字符数组的全排列是一个经典算法题。题目要求不依赖内置库，仅用 void permute(char[] a, int lengthOfa) 方法完成——这本质上是实现Heap算法（Heap's Algorithm） 的递归版本，它能在 O(n!) 时间内生成 n 个元素的所有排列，且空间效率高、无需额外集合去重。

核心思想是：对长度为 n 的数组，递归处理前 n−1 个元素；每次递归返回后，根据当前长度的奇偶性决定交换方式：

若 lengthOfa 为奇数：始终将首元素与末元素交换；
若 lengthOfa 为偶数：将第 i 个元素（循环变量）与末元素交换。

这种策略确保每轮递归都能“轮换”不同元素到末位，从而系统性覆盖所有排列组合。

以下是完整、可直接运行的实现：

public class Main2 {
    public static void main(String[] args) {
        char[] charArray = {'a', 'b', 'c', 'd'};
        permute(charArray, charArray.length);
    }

    public static void permute(char[] a, int lengthOfa) {
        // 递归基：当子数组只剩1个元素时，已确定一种完整排列
        if (lengthOfa == 1) {
            printArray(a, a.length); // 输出当前排列
            return;
        }

        // 递归处理前 lengthOfa-1 个元素
        for (int i = 0; i < lengthOfa; i++) {
            permute(a, lengthOfa - 1);

            // 根据子数组长度奇偶性执行对应交换
            if (lengthOfa % 2 == 1) {
                // 奇数长度：固定交换首尾（索引 0 和 lengthOfa-1）
                swap(a, 0, lengthOfa - 1);
            } else {
                // 偶数长度：轮流交换第 i 位与末位
                swap(a, i, lengthOfa - 1);
            }
        }
    }

    private static void swap(char[] a, int i, int j) {
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static void printArray(char[] a, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(a[i]);
            if (i < n - 1) System.out.print(" ");
        }
        System.out.println();
    }
}

✅ 关键注意事项：