这是一道典型的数据结构考研题，我看目前网上大部分博主讲的都不太通俗易懂，代码质量也参差不齐，本博文将用大白话帮你理解这道典型的分治思想算法题。

分治算法在维基百科上的定义为：在计算机科学中， 分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治和递归的区别： 分治算法是一种处理问题的思想，递归是一种编程技巧

治算法大都采用递归来实现，并且用递归实现的。分治算法的基本步骤为：

1：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； 2：解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题 3：合并：将各个子问题的解合并为原问题的解。

首先我们来看什么是全排列，百度百科中如下定义：

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

可能大家看定义还是不懂，我们来通过例子列举一下：

一个数字（1）：不需要排列：1

两个数字（1，2），共两种：1，2 | 2，1

三个数字（1，2，3），共六种：1，2，3 | 1，3，2 | 2，3，1 | 2，1，3 | 3，1，2 | 3，2，1

我们通过上面的例子不难发现，三个数字的全排列就是我先挑出一个数字例如1，则对2，3排列的规则，不就是用两个数字的规则嘛，产生的就是123和132。

同样，我们通过分治思想分而治之，求n个元素全排列时，我们可以将它逐步分解成一个个小问题： 先把第一个元素单独拎出来，然后我们对n-1元素进行全排列，依次类推…直到只有一个数字我们就不需要排列，也可以说我们的一个排列就好了。

而这个第一个元素，我们通过上面的例子就可以知道，就是所有的单个数字嘛，如123先拎出1，然后2，最后3。所以我们需要将第一个元素和之后的每一个元素进行互换来保证第一个元素把所有的数字都拎出来了。

然而当我们一个递归完成之后，我们可能在之前把第一个元素和后面的元素互换了，这时候如果我们直接递归的话原有的顺序会打乱，由于我们是依次让第一个元素和之后的每一个元素进行互换，所以我们需要先把他通过