下载文档原格式
全排列的⼏种算法全排列，我们⾼中时就学过，数学上很简单，可是⽤计算机的算法实现还是有点味道的，今天我将我碰到的⼏种算法如数奉上，欢迎交流！第⼀种：递归最常见的也是最好理解的⽅法：简单点：⽐如"a" ,"b","c"全排列，可以看做事"a" +"b","c"的全排列及"b"+ "a","c"的全排列及"c" + "a","b"的全排列也就是说，遍历原数组中的每个元素，让剩余的元素全排列，这样就找到规律了。
代码如下：public static void main(String[] args) {char buf[]={'a','b','c','d'};perm(buf,0,buf.length-1);}public static void perm(char[] buf,int start,int end){if(start==end){//当只要求对数组中⼀个字母进⾏全排列时，只要就按该数组输出即可（特殊情况）for(int i=0;i<=end;i++){System.out.print(buf[i]);}System.out.println();}else{//多个字母全排列（普遍情况）for(int i=start;i<=end;i++){//（让指针start分别指向每⼀个数）char temp=buf[start];//交换数组第⼀个元素与后续的元素buf[start]=buf[i];buf[i]=temp;perm(buf,start+1,end);//后续元素递归全排列temp=buf[start];//将交换后的数组还原buf[start]=buf[i];buf[i]=temp;}}}第⼆中⽅法：也是递归，但是和第⼀种有所区别，算法：将数据分为两部分，递归将数据从左侧移右侧实现全排列⽐较抽象，如list abcd，遍历每⼀个数，将每个数放到⼀个新的list中,并将该元素从原list删除，然后将剩下的元素继续遍历每个元素继续放到新的list ⾥，这样，当list的长度为原list长度，或者原list长度为0时打印结果！下⾯是简单的⽰意图：// abcd//bcd a//cd ab//d abc//abcd//c abd//abdc//bd ac//d acb//acbd//b acd//acdb//bc ad ...//acd b ...//abd c ...//abc d ...源代码如下：private static void sort(List datas, List target) {//System.out.println("size="+datas.size());if (datas.size()==0) {for (Object obj : target)System.out.print(obj+" ");System.out.print(" ");return;}for (int i = 0; i < datas.size(); i++) {List newDatas = new ArrayList(datas);List newTarget = new ArrayList(target);newTarget.add(newDatas.get(i));newDatas.remove(i);sort(newDatas, newTarget);}}public static void main(String[] args) {List list = new ArrayList();for(int i=0;i<5;i++){list.add(i+1);}sort(list, new ArrayList());}第三种⽅法：⾮递归直接上代码：public static void main(String[] args) {int[] arr = new int[]{1,2,3,4,5,6};for(int i :arr){System.out.print(i + " ");}System.out.println();int totalnum = 1;while(NextNumber(arr,arr.length)){for(int i :arr){System.out.print(i + " ");}System.out.println();totalnum ++;}System.out.println("Total Num: " + totalnum);}private static Boolean NextNumber(int[] arr, int n){//数组最后⼀个元素位置int lastIndex = n-1;//从右向左确定第⼀个数字（前⾯的数字⽐它⼩）int firstIndex = lastIndex;for(;arr[firstIndex-1]>arr[firstIndex];firstIndex--){if(firstIndex == 1){//已经轮询完毕,此数已经是最⼤的那个数return false;}}//从右向左确定⼀个交换数（此数⽐arr[firstIndex]⼩且⽐arr[firstIndex-1]⼤）int swapIndex = lastIndex;for(;swapIndex > firstIndex;swapIndex--){if(arr[swapIndex] < arr[firstIndex] && arr[swapIndex] > arr[firstIndex-1]){break;}}//交换数字swap(arr,firstIndex-1,swapIndex);//将firstIndex右边的数字排序for(;firstIndex < lastIndex;firstIndex++,lastIndex--){if(arr[firstIndex] > arr[lastIndex]){swap(arr,firstIndex,lastIndex);}}return true;}private static void swap(int[] arr,int i, int j){int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}如果此⽂对你有帮助，请留个⾔，新⼈需要打架的⽀持和⿎励！。
详解全排列全排列在笔试面试中很热门，因为它难度适中，既可以考察递归实现，又能进一步考察非递归的实现，便于区分出考生的水平。
所以在百度和迅雷的校园招聘中都会考到。
首先来看看题目是如何要求的（百度迅雷校招笔试题）。
题目：用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列, 如 abc 的全排列: abc, acb, bca, dac, cab, cba。
一、全排列的递归实现为方便起见，用123来示例下。
123的全排列有123、132、213、231、312、321这六种。
首先考虑213和321这二个数是如何得出的。
显然这二个都是123中的1与后面两数交换得到的。
然后可以将123的第二个数和每三个数交换得到132。
同理可以根据213和321来得231和312。
因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。
找到这个规律后，递归的代码就很容易写出来了：#include<iostream>using namespace std;void Swap(char *a,char *b){char tmp=*a;*a=*b;*b=tmp;}void AllRange(char *pszStr,int k,int m){if(k==m){static int s_i=1;printf("第%d个排列是%s\n",s_i++,pszStr);}else{for(int i=k;i<=m;i++){Swap(pszStr+i,pszStr+k);AllRange(pszStr,k+1,m);Swap(pszStr+i,pszStr+k);}}}void Foo(char *pszStr){AllRange(pszStr,0,strlen(pszStr)-1);}int main(){printf("全排列的递归实现:\n");char szT extStr[] = "123";printf("%s的全排列如下:\n", szTextStr);Foo(szTextStr);system("pause");return0;}运行结果如下图所示：注意这样的方法没有考虑到重复数字，如122将会输出：这种输出绝对不符合要求，因此现在要想办法来去掉重复的数列。
⼀⽂搞懂全排列、组合、⼦集问题微信搜⼀搜：【bigsai】获取更多肝货知识春风⼗⾥，感谢有你前⾔Hello，⼤家好，我是bigsai，long time no see！在刷题和⾯试过程中，我们经常遇到⼀些排列组合类的问题，⽽全排列、组合、⼦集等问题更是⾮常经典问题。
本篇⽂章就带你彻底搞懂全排列！求全排列？全排列即：n个元素取n个元素(所有元素)的所有排列组合情况。
求组合？组合即：n个元素取m个元素的所有组合情况(⾮排列)。
求⼦集？⼦集即：n个元素的所有⼦集(所有可能的组合情况)。
总的来说全排列数值个数是所有元素，不同的是排列顺序；⽽组合是选取固定个数的组合情况(不看排列)；⼦集是对组合拓展，所有可能的组合情况(同不考虑排列)。
当然，这三种问题，有相似之处⼜略有所不同，我们接触到的全排列可能更多，所以你可以把组合和⼦集问题认为是全排列的拓展变形。
且问题可能会遇到待处理字符是否有重复的情况。
采取不同的策略去去重也是相当关键和重要的！在各个问题的具体求解上⽅法可能不少，在全排列上最流⾏的就是邻⾥互换法和回溯法，⽽其他的组合和⼦集问题是经典回溯问题。
⽽本篇最重要和基础的就是要掌握这两种⽅法实现的⽆重复全排列，其他的都是基于这个进⾏变换和拓展。
全排列问题全排列，元素总数为最⼤，不同是排列的顺序。
⽆重复序列的全排列这个问题刚好在是原题的，⼤家学完可以去a试试。
问题描述：给定⼀个没有重复数字的序列，返回其所有可能的全排列。
⽰例：输⼊: [1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]回溯法实现⽆重复全排列回溯算法⽤来解决搜索问题，⽽全排列刚好也是⼀种搜索问题，先回顾⼀下什么是回溯算法：回溯算法实际上⼀个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满⾜求解条件时，就“回溯”返回，尝试别的路径.⽽全排列刚好可以使⽤试探的⽅法去枚举所有中可能性。
全排列递归算法概述及举例说明1. 引言1.1 概述在计算机科学中，全排列递归算法是一种常见且重要的算法。
它能够通过递归的方式生成给定元素集合的所有可能排列组合。
全排列递归算法的实现原理相对简单，但其应用领域十分广泛，并在许多其他算法中扮演着关键角色。
1.2 文章结构本文将首先介绍全排列递归算法的概述，包括其定义、特点和应用场景等。
随后，我们将深入探讨该算法的实现原理，并对其优缺点进行详尽分析。
接下来，我们会通过三个具体的举例说明来展示全排列递归算法的具体运用情况。
在最后部分，我们将探究该算法在其他领域中的应用以及进一步扩展与改进思路。
1.3 目的本文旨在提供一个清晰而全面的介绍全排列递归算法及其应用示例。
通过阅读本文，读者将能够了解该算法的基本原理、实现方法和优缺点，并对其在不同场景下的具体应用有更深入、更具体的认识。
此外，本文还将探讨该算法的拓展和改进思路，为读者提供继续研究和应用的思路。
2. 全排列递归算法概述2.1 什么是全排列递归算法全排列递归算法是一种用于确定给定元素集合所有可能排列方式的算法。
它通过递归的方式将原始集合分解成更小的子问题，并且在每个步骤中交换不同位置上的元素来生成新的排列。
这个过程会一直持续到达到基本情况，也就是无法再进一步交换元素位置为止。
2.2 实现原理全排列递归算法可以通过以下方法实现：1) 确定基本情况：当待排序集合只包含一个元素时，即达到了基本情况。
此时，我们可以认为该集合已经被排列好了。
2) 对于超过一个元素的集合，选择其中一个元素作为固定元素，并将其与其他每个位置上的元素进行交换。
这样，我们就得到了以不同元素开头的一系列子问题。
3) 对于每个子问题，重复步骤2中的操作，对其余部分进行递归地全排列。
4) 在重复进行步骤2和3后，我们可以得到最终的全排列结果。
2.3 优缺点分析全排列递归算法具有以下优点：- 算法逻辑简单易懂，易于实现和理解。
- 能够生成给定元素集合的所有可能排列方式。
全排列的⼏种实现（含字典序排列算法分析） 始于⼀个很简单的问题：⽣成｛0，1，2，3，...，n-1｝的n！种排列，即全排列问题。
下⾯介绍⼏种全排列的实现，以及探讨⼀下其解题思路。
基于枚举/递归的⽅法思路： 基于枚举的⽅法，也可以说是基于递归的⽅法，此⽅法的思路是先将全排列问题的约束进⾏放松，形成⼀个较容易解决的新问题，解新问题，再对新问题进⾏约束，解出当前问题。
以上全排列问题是⽣成｛0，1，2，...，n-1｝的n！个排列，隐含的⼀个约束是这个n个位置上的数必须是给出的集合中的数，不能重复使⽤。
当我们将此约束放松的时候，问题就变成了n个位置每个位置上有0~n-1种可能出现的数字，列出所有n n种数列，即在每⼀位上枚举所有的可能。
新问题的算法⾮常简单：private Integer[] perm;private void permut(int pos, int n) {if (pos == n) {for (int i = 0; i < perm.length; i++) {System.out.print(perm[i]);}System.out.println();return;}for (int i = 0; i < n; i++) {perm[pos] = i;permut(pos+1, n);}} ⽽我们实际的问题只要保证每⼀位上的数字在其他位置上没有使⽤过就⾏了。
private boolean[] used;private Integer[] perm;private void permut(int pos, int n) {if (pos == n) {for (int i = 0; i < perm.length; i++) {System.out.print(perm[i]);}System.out.println();return;} //针对perm的第pos个位置，究竟使⽤0~n-1中的哪⼀个进⾏循环for (int i = 0; i < n; i++) {if (used[i] == false) {perm[pos] = i;used[i] = true; //i已经被使⽤了，所以把标志位设置为Truepermut(pos+1, n);used[i] = false; //使⽤完之后要把标志复位}}} 或者完全按递归是思想，对｛0，1，2，...，n-1｝进⾏排列，分别将每个位置交换到最前⾯位，之后全排列剩下的位：private static void PermutationList(int fromIndex, int endIndex){if (fromIndex == endIndex)Output();else{for (int index = fromIndex; index <= endIndex; ++index){// 此处排序主要是为了⽣成字典序全排列，否则递归会打乱字典序Sort(fromIndex, endIndex);Swap(fromIndex, index);PermutationList(fromIndex + 1, endIndex);Swap(fromIndex, index);}}}基于字典序的⽅法 基于字典序的⽅法，⽣成给定全排列的下⼀个排列，所谓⼀个的下⼀个就是这⼀个与下⼀个之间没有其他的。
快速排序非递归算法快速排序是一种常用的排序算法，其主要思想是通过分治的思想将待排序序列不断划分成较小的子序列，并分别对子序列进行排序，最终将所有子序列合并得到有序序列。
与递归版本不同，快速排序的非递归算法通过使用栈来模拟递归过程，实现排序过程的迭代。
快速排序的非递归算法主要包含以下几个步骤：1. 首先，我们需要选择一个枢轴元素（pivot），通常可以选择待排序序列的第一个元素作为枢轴元素。
2. 然后，我们需要将待排序序列分成两部分，一部分是小于等于枢轴元素的元素，另一部分是大于枢轴元素的元素。
这一步骤被称为划分（partition）操作。
3. 接下来，我们将划分得到的两个子序列分别压入栈中。
4. 从栈中取出一个子序列，对其进行划分操作，将划分得到的两个子序列压入栈中。
5. 重复步骤4，直到栈为空。
此时，所有的子序列都已经排好序。
下面我们通过一个例子来说明快速排序的非递归算法的具体步骤。
假设我们要对序列[6, 3, 8, 2, 9, 1]进行排序。
选择第一个元素6作为枢轴元素。
然后，进行划分操作，得到两个子序列[3, 2, 1]和[8, 9]。
将这两个子序列压入栈中。
从栈中取出子序列[8, 9]，进行划分操作，得到两个子序列[8]和[9]。
由于子序列[8]和[9]已经有序，所以不需要继续划分，我们可以将其从栈中弹出。
接下来，从栈中取出子序列[3, 2, 1]，进行划分操作，得到两个子序列[1, 2]和[3]。
将这两个子序列压入栈中。
从栈中取出子序列[1, 2]，进行划分操作，得到两个子序列[1]和[2]。
由于子序列[1]和[2]已经有序，所以不需要继续划分，我们可以将其从栈中弹出。
从栈中取出子序列[3]，由于只有一个元素，不需要划分，我们可以将其从栈中弹出。
栈为空，排序过程结束。
将所有的子序列合并，得到有序序列[1, 2, 3, 8, 9]。
通过上述例子可以看出，快速排序的非递归算法通过使用栈来模拟递归过程，实现了排序过程的迭代。
