本文详解如何使用递归方法生成字符数组的所有排列，基于heap算法实现高效、无重复的全排列输出，并提供可运行代码与关键逻辑说明。
在Java中，通过递归生成字符数组的全排列是一个经典算法题。题目要求不依赖内置库，仅用 void permute(char[] a, int lengthOfa) 方法完成——这本质上是实现Heap算法（Heap's Algorithm） 的递归版本，它能在 O(n!) 时间内生成 n 个元素的所有排列，且空间效率高、无需额外集合去重。
核心思想是：对长度为 n 的数组，递归处理前 n−1 个元素；每次递归返回后，根据当前长度的奇偶性决定交换方式：
- 若 lengthOfa 为奇数：始终将首元素与末元素交换；
- 若 lengthOfa 为偶数：将第 i 个元素（循环变量）与末元素交换。
这种策略确保每轮递归都能“轮换”不同元素到末位，从而系统性覆盖所有排列组合。
以下是完整、可直接运行的实现：
立即学习“Java免费学习笔记（深入）”；
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();
}
}✅ 关键注意事项：
- 初始调用应为 permute(a, a.length)，而非 permute(a, 3)——否则会遗漏以 'd' 开头的排列；
- printArray 中使用 a.length 更健壮，避免硬编码 4；
- Heap算法生成顺序不是字典序，但保证无重复、全覆盖（共 4! = 24 种排列）；
- 原始代码中 a[1] = a[2] 等手动交换逻辑缺乏通用性，无法扩展到任意长度，而Heap算法具有普适性。
该实现时间复杂度为 O(n×n!)（含输出开销），空间复杂度为 O(n)（递归栈深度）。掌握此模式，不仅可解字符排列，还可轻松迁移至整数数组、字符串甚至自定义对象的全排列场景。
