谁能解释一下用递归做的排列算法的详细步骤？参考王晓东的《计算机算法设计与分析》p11

Question

如题所述

Answer 1

用到递归的排序算法有快速排序和归并排序。
快速排序：先选最开始的元素为枢轴，然后分别从两头中的一头开始与枢轴比较。后面的应该大于枢轴，前面的应该小于枢轴，不然则交换（前面与后面），最后确定下来的位置（前后重合）就是枢轴的位置。这样一来原序列就一分为二。不断递归，再一分为二，最后直到被分为的两端中有一个元素单独的时候就结束分割。
归并排序:第一次两个两个的来，排序之后就归并成一个有序列，然后再四个四个的来，排序之后归并成一个有序列……直到最后两个归并为一个有序列。

Answer 2

分治法求解问题分为三个步骤：
- 分解：将问题分为若干个子问题。
- 解决：递归地求解每个子问题。
- 合并：将每个子问题的解合并成为整个问题的解。
现在我们需要求具有n个元素的数组A的全排列。例如：大小为3的数组A=[a,b,c] (为方便起见，我把引号全都省略了，其实应该是A=['a','b','c']。下同），它的全排列为：
[[a,b,c],
[a,c,b],
[b,a,c],
[b,c,a],
[c,a,b],
[c,b,a]]
这是一个大小为 n!*n 的二维数组。

使用分治算法求解全排列的过程如下
- 分解：将数组分为子数组 A[1..k-1] 和一个元素 A[k]。 (1≤k≤n)
- 解决：递归地求解每个子数组 A[1..k-1] 的全排列，直至子数组A[1..k-1]为空时结束递归。
- 合并：将上一步的结果---A[1..k-1]的全排列（一个二维数组）与元素A[k]合并，得出A[1..k]的全排列。例如：
[[]] 与 a 合并得到 [[a]]
[[a]] 与 b 合并得到 [[a,b], [b,a]]
[[a,b],[b,a]] 与 c 合并得到 [[a,b,c],[a,c,b],[c,a,b],[b,c,a],[c,a,b],[c,b,a]]本回答被网友采纳