排列算法（递归实现）（1~n全排列）（字典序全排列）

1.? 1~n全排列

比如1，2，3；我们要将它们排序，首先分为三种情况：三个数字分别作为第一个位置，那么就要将其放在第一个位置，然后再对后面剩下的数进行排列...很明显这样会重复上述操作，就可以用递归去实现。

模拟一下过程：

1，2，3

1，3，2

2，1，3

2，3，1

3，2，1

3，1，2

位置的替换可以使用swap函数实现，记得位置替换后要再一次换回来，确保每个数字都可以出现在第一个位置，避免了重复的结果。

如果不换回来就会：

1，2，3

1，3，2

3，1，2

3，2，1

1，2，3

1，3，2

这很明显是错的。

具体实现：

#include <iostream>
using namespace std;

void swap(int* arr, int p, int q)
{
	int temp = arr[p];
	arr[p] = arr[q];
	arr[q] = temp;
}

void Array(int* arr, int p, int q)
{
	if (p == q)//回归条件
	{
		for (int j = 0; j < q + 1; j++)
		{
			cout << arr[j];
		}
		cout << endl;
	}
	else
	{
		for (int i = p; i <= q; i++)
		{
			swap(arr, p, i);
			Array(arr, p + 1, q);//开始递归
			swap(arr, p, i);//交换回来，才能使每个数都有机会在起始位置
		}
	}
}

int main()
{
	int arr[] = { 1,2,3 };
	Array(arr,0,2);

	return 0;
}

?但可以发现上面只能进行全排列，并不能满足字典序全排列，这是为什么？

还是1，2，3为例子，当3为第一个位置时，是执行了1与3进行的换，导致了后面出现：

3，2，1

3，1，2

不符合字典序，要怎么实现呢？

2.? 字典序全排列

上面已经实现了全排列，要实现字典序，很明显要在交换那里动手脚：

要跟上面一样，每个数字都要有机会排在第一个位置，同时实现字典序，就要通过三个数字对第一位置循环后移滚动实现，确保字典序最小。

模拟实现：

1，2，3

1，3，2

2，1，3

2，3，1

3，1，2

3，2，1

同样交换后不要忘记换回来。

具体实现：

#include <iostream>
using namespace std;

void swap(int* arr, int p, int q)//向后滚
{
	int temp = arr[q];
	for (int i = q; i > p; i--)
	{
		arr[i] = arr[i - 1];
	}
	arr[p] = temp;
}

void swapback(int* arr, int p, int q)//返回就得向前滚
{
	int temp = arr[p];
	for (int i = p; i < q; i++)
	{
		arr[i] = arr[i + 1];
	}
	arr[q] = temp;
}

void Array(int* arr, int p, int q)
{
	if (p == q)//回归条件
	{
		for (int j = 0; j < q + 1; j++)
		{
			cout << arr[j];
		}
		cout << endl;
	}
	else
	{
		for (int i = p; i <= q; i++)
		{
			swap(arr, p, i);
			Array(arr, p + 1, q);//开始递归
			swapback(arr, p, i);//交换回来，才能使每个数都有机会在起始位置
		}
	}
}

int main()
{
	int arr[] = { 1,2,3 };
	Array(arr,0,2);

	return 0;
}