调用STL里#include
#include
#include
using namespace std;
const int N = 4;
int arr[N] = {1,2,3,4};
int main()
{
do{
for(int i=0; i < N; i++)
printf("%d ",arr[i]);
putchar('\n');
}while(next_permutation(arr,arr+N));//prev_permutation(arr,arr+ N) 的话arr里的数据按降序排列
return 0;
}
next_permutation是STL中专门用于排列的函数，运行需要包含头文件
#include
using namespace std
next_permutation(start,end)
注意：函数要求输入的是一个升序排列的序列的头指针和尾指针
如果输入的是一个数组例如：
double a[5]
则:
double *start = &a[0];
double *end = &a[5];(实际上数组的最有一个元素应该是a[4]，也就是说
end实际指向的应该是数组最有一个元素指针对下
一个指针）end = start+N;
函数输入之所以要求必须是一个升序的排列，原因在于函数运行一次对输入的数组进行移动排列一次后，在函数退出前判断移动后的数组是否升序，如果升序则函数返回BOOL变量false，否则返回true。这样当你输入的是一个升序的排列后，每运行一次函数就对数组进行一次移动得到一个新的排列，函数对数组的移动排列采用递归方式。当所有排列方式都遍历一遍后函数最后一次输出的又是一个升序的排列，也就是和你最先输入的数组一样的排列。
因此你可以用下面结构遍历所有的排列可能：
while ( next_permutation(start,end))//判断是否函数返回true,是责继
//续循环，否则推出说明排列完毕
{
//你要做的处理程序放在此循环内
copy(start,end, o stream_iterator ........ ....... } //排序可以用sort()实现 首先，给出算法的思路 设R={r1,r2,...,r n}是要进行排列的n个元素，R i=R-{r i}。 集合X中元素的全排列记为permutation(X)，(ri)permutation(X)表示在全排列permutation(X)的每一个排列前加上前缀r i得到的排列。 R的全排列可归纳定义如下： 当n=1时，permutation(R)={r},r是集合R中唯一的元素； 当n>1时，permutation(R)由(r1)permutation(R1)，(r2)permutation(R2)，……， (r n)permutation(R n)构成。 此算法要求待排列的数据是互异的，因为该算法不能检测同种排列是否已经输出，如： 1, 1, 2 那么，全排列期望输出是： 1, 1, 2 1, 2, 1 2, 1, 1 但是该算法的输出： 1, 1, 2 1, 2, 1 2, 1, 1 1, 1, 2 1, 2, 1 2, 1, 1 这是该算法的缺点，也限制了它的适用范围。 程序描述如下： #include < iostream > #include < algorithm > using namespace std; //递归产生R[k:n]的所有的排列，元素是互异的 template < class Type > void permutation(Type * R, int k, int n) { if (k == n) { for ( int i = 0 ;i < n; ++ i) cout << R[i] << " \t " ; cout << endl; } else for ( int i = k;i < n; ++ i) { swap(R[k],R[i]); permutation(R,k + 1 ,n); swap(R[k],R[i]); } } 还有一种很简单的方法，使用GP中的方法 该算法是STL中的范型算法，当然效果是很好的，不会出现上面的算法的情况。程序描述如下： //使用泛型算法next_permutation() #include < iostream > #include < vector > #include < algorithm > using namespace std; //产生R[k:n]的所有的排列 template < class Type > void pernutation(Type * R, int k, int n) { vector < Type > myVec; int i,size = n - k; for (i = k;i < n;i ++ ) myVec.push_back(R[i]); //使用next_permutation()函数必须是有序的数据 sort(myVec.begin(),myVec.end()); do { for (i = 0 ;i < size;i ++ ) cout << myVec[i] << " \t " ; cout << endl; } while (next_permutation(myVec.begin(),myVec.end())); 排列组合n选m，组合算法——0-1转换算法（巧妙算法）C++实现 知识储备 排列的定义：从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 A(n,m）表示计算公式： 注意：m中取n个数，按照一定顺序排列出来，排列是有顺序的，就算已经出现过一次的几个数。只要顺序不同，就能得出一个排列的组合，例如1,2,3和1,3,2是两个组合。 组合的定义：从n个不同元素中，任取m(m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示。 计算公式： 注意：m中取n个数，将他们组合在一起，并且顺序不用管，1,2,3和1,3,2其实是一个组合。只要组合里面数不同即可 组合算法 本算法的思路是开两个数组，一个index[n]数组，其下标0~n-1表示1到n个数，1代表的数被选中，为0则没选中。value[n]数组表示组合 的数值，作为输出之用。 ? 首先初始化，将index数组前m个元素置1，表示第一个组合为前m 个数,后面的置为0。? 然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为?“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。一起得到下一个组合（是一起得出，是一起得出，是一起得出）重复1、2步骤，当第一个“1”移动到数组的n-m的位置，即m个“1”全部移动到最右端时；即直到无法找到”10”组合,就得到了最后一个组合。 组合的个数为： 例如求5中选3的组合： 1 1 1 0 0 --1,2,3? 1 1 0 1 0 --1,2,4? 1 0 1 1 0 --1,3,4? 0 1 1 1 0 --2,3,4? 1 1 0 0 1 --1,2,5? 1 0 1 0 1 --1,3,5? 0 1 1 0 1 --2,3,5? 1 0 0 1 1 --1,4,5? 0 1 0 1 1 --2,4,5? 0 0 1 1 1 --3,4,5 代码如下： 第一章算法概述 1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。 2.算法的性质： 1)输入：有零个或多个输入 2)输出：有至少一个输出 3)确定性：每条指令是清晰的、无歧义的 4)有限性：每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复 杂性，需要空间资源的量称为空间复杂性 2)三种时间复杂性：最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念：直接或间接调用自身的算法 2.递归函数：用函数自身给出定义的函数 3.递归要素：边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout< 字符串的排列组合算法合集 全排列在笔试面试中很热门，因为它难度适中，既可以考察递归实现，又能进一步考察非递归的实现，便于区分出考生的水平。所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了，因此本文对全排列作下总结帮助大家更好的学习和理解。对本文有任何补充之处，欢迎大家指出。 首先来看看题目是如何要求的（百度迅雷校招笔试题）。一、字符串的排列 用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。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后，递归的代码就很容易写出来了： view plaincopy #includeiostream?using?namespace?std;?#includeassert.h?v oid?Permutation(char*?pStr,?char*?pBegin)?{?assert(pStr?pBe gin);?if(*pBegin?==?'0')?printf("%s",pStr);?else?{?for(char *?pCh?=?pBegin;?*pCh?!=?'0';?pCh++)?{?swap(*pBegin,*pCh);?P ermutation(pStr,?pBegin+1);?swap(*pBegin,*pCh);?}?}?}?int?m ain(void)?{?char?str[]?=?"abc";?Permutation(str,str);?retur n?0;?}? 另外一种写法： view plaincopy --k表示当前选取到第几个数，m表示共有多少个数?void?Permutation(char*?pStr,int?k,int?m)?{?assert(pStr); ?if(k?==?m)?{?static?int?num?=?1;?--局部静态变量，用来统计全排列的个数?printf("第%d个排列t%s",num++,pStr);?}?else?{?for(int?i?=?k;?i?=?m;?i++)?{?swa p(*(pStr+k),*(pStr+i));?Permutation(pStr,?k?+?1?,?m);?swap( *(pStr+k),*(pStr+i));?}?}?}?int?main(void)?{?char?str[]?=?" abc";?Permutation(str?,?0?,?strlen(str)-1);?return?0;?}? 如果字符串中有重复字符的话，上面的那个方法肯定不会符合要求的，因此现在要想办法来去掉重复的数列。二、去掉重复的全排列的递归实现 由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122，第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了，但对212，它第二个数 排序算法 一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType); //对R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入R[2],...,R[n]// begin R[0] := R[I]; J := I - 1; While R[0] < R[J] Do //查找R[I]的插入位置// begin R[J+1] := R[J]; //将大于R[I]的元素后移// J := J - 1 end R[J + 1] := R[0] ; //插入R[I] // end End; //InsertSort // 二、选择排序 1. 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2. 排序过程： 【示例】： 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 ［38 65 97 76 49 27 49] 第二趟排序后13 27 ［65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 97 76] 全排列的生成算法对于给左的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。字典序法按照字典序求下一个排列的算法广例字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是：123,132,213,231,312,321o注意一个全排列可看做一个字符串，字符串可有前缀、后缀/生成给泄全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。广例839647521是1—9的排列。1—9的排列最前而的是123456789,最后而的是987654321,从右向左扫描若都是增的，就到了987654321,也就没有下一个了。否则找出第一次出现下降的位置。算法：由P1P2...Pn生成的下一个排列的算法如下：1求j=max{j| Pj-I 字符串全排列算法C语言实现 问题描述： 输入一个字符串，打印出该字符串中字符的所有排列。 输入: 123 输出: 123 132 213 231 312 321 问题分析： 现象分析： 这种问题，从直观感觉就是用递归方法来实现即：把复杂问题逐渐简单化，进而得出具体代码实现。（如何发现一个问题可以使用递归方式来解决？经分析可以发现：M 个数的排列方法与N(N>M)个数的排列方法没有区别，处理方法与数据的个数没有关系。 处理方法的一致性，就可以采用递归）。 3个数（123）排列，第一位1不动，剩下两个数（23）的排列，只要相互颠倒一下，就可以出现关于1开头的所有排列 123 132 把2换到第一位，保持不动，剩下的两个数（13）的排列，只要相互颠倒一下，就可以出现关于2开头的所有排列 213 231 同理，把3换到第一位，可得到 312 321 扩展： 把3个数的所有排列，前面加一个4，就可以得到关于4开头的所有的排列4123 4132 4213 4231 4312 4321 若把4与后续数据中的任意一个数据交换，通过完成对后续三个数的全排列，就可以得到相应的数开头的四数的排列。 总结： 对4个数的排列，可以转换成首位不动，完成对3个数的排列 对3个数的排列，可以转换成首位不动，完成对2个数的排列 对2个数的排列，可以转换成首位不动，完成对1个数的排列 对于1个数，无排列，直接输出结果 算法实现说明： 对n个数的排列，分成两步： （1）首位不动，完成对n-1个数的排列， （2）循环将后续其他数换到首位，再次进行n-1个数的排列 注：排列完成后，最终的串要与原串相同 C语言代码实现： #include 排序算法 排序算法大致分为两大类，即排序对象全部位于内存的内排序以及排序对象不完全位于内存的外排序。其中又以内排序为排序算法的主要部分，绝大多数的排序算法均适用于内排序。 除了以排序对象是否全部位于内存来划分的两种类型外，排序算法又分为： 1)对待排序对象进行两两比较以确定两对象次序，进而确定整个序列的交换排序 2)将待排序对象中的未排序对象依次插入到已排序好的序列中，此为插入排序 3)将未排序子序列中的最小对象移动到该子序列的最前端并于未排序子序列中 删除此最小对象，这是选择排序 4)利用堆结构实现的堆排序，相当的优秀，对于一般数据有着nlog2(n)的算法复 杂度，并且不需要额外的内存空间 5)十分适合于外排序的归并排序，原理是将待排序序列分割为两两一对的小序 列，对这些小序列进行排序并不断将这些小序列合并，最终获得完整有序序列， 和堆排序一样的算法复杂度，不过需要额外的储存空间。相对于堆排序的优点 是可以处理外排序 以上的5个算法均基于对象关键字大小的比较，以下的两种算法是基于对象关键字 大小的统计比较。 6)比较统计排序，基本思想是对给定的待排序序列中的每一个对象，确定该序列 中键值小于对象键值的对象个数，一旦知道了这个统计信息，那么就可以直接 将对象放到输出序列的正确的位置上了。 7)分布统计排序，是比较统计排序的升级版本，可以获得O(n)的算法复杂度，可 以说是所有算法里面最优的，但是缺点也是很明显，就是对于输入数据结构有 明显的要求和需要额外的内存空间。 下面对上面所述的相关算法进行描述。 一、交换排序 交换排序中最基本简单的就是冒泡排序了，基于冒泡排序的优化算法又有双向冒泡排序。而除了冒泡排序之外，快速排序也是常见的交换排序算法。鉴于冒泡排序太简单了，这里就不打算进行介绍了。 快速排序，是一种效率很好的排序方法，适用于排序问题的规模很大但对于稳定性不做要求的情况。这里的稳定性指的是，对于原序列中拥有相同大小关键字的项，如果在排序后这些项的前后顺序没有变化，那么我们就称该算法为稳定的。 快速排序的设计方法是分冶法，基本思想是：在待排序序列中选择一个对象(比如说第一个对象)作为基准点(pivot)，通过将将序列分割为两个子序列(一个子序列的对象都大于基准点，另一个则是小于)来确定基准点的位置。确定了基准点的位置之后对分割开来的两个子序列重复上面的操作(此即为分冶)，直到所有的对象都被确定了位置。 举一个例子以较形象的表达这一过程，以数据10、25、25、11、2、5来做例子，其中因为有两个25，所以第2个25以25*表示。 算法设计与分析期末综合实验试题清单 分治与递归 1-1 合并排序 问题描述：给定n 个整数，利用合并排序思想将其调整成单调序列。 输入：整数的个数n ，以及n 个整数 输出：从大到小排序的n 个整数（或从小到大排序） 1-2 split 快速排序（枢点法） 问题描述：给定n 个整数，利用枢点法快速排序的思想将其调整成单调序列。 输入：整数的个数n ，以及n 个整数 输出：从大到小排序的n 个整数（或从小到大排序） 1-3 平面最近点对 问题描述：平面内有若干点，设计一算法在O （nlogn ）时间内求出直线距离最近的一对点，并输它们的距离。 输入：点对的数目n 以及n 对点的坐标 输出：最近的点对坐标（x,y ）以及距离d 1-4 棋盘覆盖问题 问题描述：在一个2k ×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该 方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L 型骨牌不得重叠覆盖。 输入：棋盘的行列数n ，棋盘中特殊方格的行列号（x,y ） 输出：棋盘的覆盖方案 1-5 求k 大（小）元素（基于split 枢点法划分） 问题描述：有一数列，设计一分治递归算法，以Ω(nlogn)时间找出其第k 大（小）元素。 输入：整数的个数n 、n 个整数以及k 值 输出：第k 大（小）元素值以及其对应的下标i 1-6 二分检索 问题描述：有一单调序列，设计一分治算法检索出元素x 。 输入：整数的个数n、n个单调增（减）个整数以及需检索的元素值x 输出：最近的点对坐标（x,y）以及距离d 1-7 大整数乘法（10进制） 问题描述：有两个10制的大整数（不少于30位），设计一分治算法，以O（nlogn）时间算出其乘积。 输入：第一个大整数的位数m、第二个大整数的位数n，以及两个大整数x,y 输出：两个大整数的乘积s 1-8 循环赛比赛安排 问题描述：设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能赛一次； (3)循环赛一共进行n-1天。 输入：选手的个数n、n个选手的编号 输出：每天的赛事安排(共n-1天） 1-9 整数的划分问题 问题描述：将正整数n表示成一系列正整数之和：n=n1+n2+…+n k，其中n1≥n2≥…≥n k≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数以及划分情况。 输入：正整数n 输出：n的划分个数以及划分情况 1-10 主元素问题 问题描述：有一个整数数列，数列中元素出现次数超过一半的元素定义为主元素，设计一分治算法，求出主元素。 输入：整数的个数n以及n个整数 输出：如果有主元素，输出主元素以及它们所在的位置；如果没有主元素，输出-1 1-11 全排列的生成 问题描述：给出一个序列，生成这个序列的全排列 输入：整数的个数n以及n个整数 输出：生成这n个数的全排列 贪婪算法 2-1 加油站问题 问题描述：一辆汽车加满油后,可行使n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法，对于给定的n和k个加油站位置，指出应在哪些加油站停靠加油才能使加油次数最少。 输入：汽车加满油后可行驶千米数n，加油站个数k。以及两两加油站之间的距离。 输出：最少的加油次数m，如果无法到达目的地，则输出“No Solution”。 各种排序算法的总结和比较 1 快速排序（QuickSort） 快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。 （1）如果不多于1个数据，直接返回。 （2）一般选择序列最左边的值作为支点数据。（3）将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。 （4）对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。 2 归并排序（MergeSort） 归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。 3 堆排序（HeapSort） 堆排序适合于数据量非常大的场合（百万数据）。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。 Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 5 插入排序（InsertSort） 插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。 1.5全排列的生成算法 全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 这里介绍全排列算法四种： (A)字典序法 (B)递增进位制数法 (C)递减进位制数法 (D)邻位对换法 1.5.1字典序法 对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。 [例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列 是:123,132,213,231,312,321。 [注意] 一个全排列可看做一个字符串，字符串可有前缀、后缀。 1）生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。 / 1.5.2递增进位制数法 1)由排列求中介数 在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。 在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2—n)一致。可看出n-1位的进位链。右端位逢2进1，右起第2位逢3进1，…，右起第i位逢i+1进1，i=1,2,…,n-1. 这样的中介数我们称为递增进位制数。上面是由中介数求排列。 由序号（十进制数）求中介数（递增进位制数）如下： m=m1,0≤m≤n!-1 m1=2m2+kn-1,0≤kn-1≤1 m2=3m3+kn-2,0≤kn-2≤2 …………… mn-2=(n-1)mn-1+k2,0≤k2≤n-2 mn-1=k1,0≤k1≤n-1 p1p2…pn←→(k1k2…kn-1)↑←→m 在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。为方便起见，令ai+1=kn-1，i=1,2,…,n-1 (k1k2…kn-1)↑=(anan-1…a2)↑ ai：i的右边比i小的数字的个数 在这样的定义下， 有839647521←→(67342221)↑ 全排列的生成算法对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。字典序法按照字典序求下一个排列的算法 /*例字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。注意一个全排列可看做一个字符串，字符串可有前缀、后缀。*/生成给定全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。/*例 839647521是1—9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。算法: 由P1P2…Pn 生成的下一个排列的算法如下:1. 求i=max{j| Pj-1 概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。 直接插入排序示例： 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。 算法的实现： 1.void print(int a[], int n ,int i){ 2. cout< 13.if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。 小于的话，移动有序表后插入 14.int j= i-1; 15.int x = a[i]; //复制为哨兵，即存储待排序元素 16. a[i] = a[i-1]; //先后移一个元素 17.while(x < a[j]){ //查找在有序表的插入位置 18. a[j+1] = a[j]; 19. j--; //元素后移 20. } 21. a[j+1] = x; //插入到正确位置 22. } 23. print(a,n,i); //打印每趟排序的结果 24. } 25. 26.} 27. 28.int main(){ 29.int a[8] = {3,1,5,7,2,4,9,6}; 30. InsertSort(a,8); 31. print(a,8,8); 32.} 效率： 时间复杂度：O（n^2）. 其他的插入排序有二分插入排序，2-路插入排序。 2. 插入排序—希尔排序（Shell`s Sort） 希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序 基本思想： 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序” 时，再对全体记录进行依次直接插入排序。 排列组合——排列公式的推理和组合 加法原理和乘法原理，是排列组合中的二条基本原理，在解决计数问题中经常运用。掌握这两条原理，并能正确区分他们，至关重要。 加法原理 若完成一件事情有3类方式，其中第一类方式有1种方法，第二类方式有3种方法，第三类有2种方法，这些方法都不相同，但任选一种方法都可以完成此事，则完成这件事情共有1+3+2=6种方法，这一原理称为加法原理。例如:从甲地到乙地有三类方式，一是汽车，二是火车，三是飞机。若一天中汽车有2班，火车有4班，飞机有一班，那么从甲地到乙地共有多少种不同的走法。共有2+4+1=7种。 乘法原理 若完成一件事情分r个步骤，其中第一个步骤有m1种方法，第二个步骤有m2种方法……第步骤共有mr种方法，各步骤连续或同时完成，这件事才算完成，则完成这件事共有m1*m2*……*mr种方法。例如:从甲地到丙地必须经过乙地。从甲地到乙地有4条路线，从乙地到丙地有3条路线，问从甲地到丙地共有多少种不同的走法？解：要从甲地到达丙地，必须经过两个步骤：先从甲地到乙地，有4条路线；再从乙地到丙地，有3条路线。只有这两个步骤都完成了，才能完成这种事情，缺少哪一个步骤都不行。因此从甲地到丙地共有4*3=12种走法。 加法原理和乘法原理的区别 以上两个基本原理在排列组合问题中将会反复使用。这两个原理回答的都是关于完成一件事情的不同方法的种数问题，但是又有根本区别。加法原理针对的是“分类”问题，若完成一件事情有多类方式，每一类方式的各种方法相互独立，用其中任何一种方法都可以完成这件事情，则用加法原理；而乘法原理针对的是“分步”问题，若完成一件事情必须依次经过多个步骤，每一个步骤的各种方法相互依存，只有各种步骤都完成才算做完成这种事情，则这时用乘法原理。 排列数公式推理过程 例：用1、2、3这3个数字可以组成多少个数字十位和个位不重复的两位数？解：要组成数字不重复的两位数，需要经过两个步骤：第一步确定十位上的数，数字1、2、3都可以放在十位上，共有3种方法；第二步确定个位上的数，因为要求个位数与十位数不能重复，所以个位上的数，只能从三个数字中去掉十位数后所剩的两个数字中任选一个，共有2种方法。只有十位和个位上的数都确定了，才能组成数字不重复的两位数，这两个步骤缺少哪一个都不行。因此，根据乘法原理，3*2=6. 上例中，我们把数字1、2、3称为元素。组成数字不重复的两位数这个问题，从3个不同的元素中任取2个，然后按顺序排成一列数，由于这样的排列与数字不重复的两位数是一一对应的，因此求数字不重复的两位数的个数等同于求这样的排列个数。 推理过程：从n个不同元素中取出m个不同元素排成一列，必须经过m 个步骤。第一步，确定第1个位置上的元素,可以从这n个元素中任取1个放在这个位置上，共有n种方法，即n-(1-1)括号内为位置数减1；第 精品文档 全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1?n的n个数字的排列一一对应，因此 在此就以n 个数字的排列为例说明排列的生成法。 n 个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从它的 前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。 全排列的生成法通常有以下几种：字典序法递增进位数制法递减进位数制法邻位交换法 递归类算法 1. 字典序法 字典序法中，对于数字1、2、3 ......n 的排列，不同排列的先后关系是从左到右逐 个比较对应的数字的先后来决定的。例如对于5个数字的排列 1 2354和12345，排列12345 在前，排列12354 在后。按照这样的规定， 5 个数字的所有的排列中最前面的是 1 2345 ，最后面的是54321 。 字典序算法如下： 设P是1?n的一个全排列： p=p1p2 .... pn=p1p2 ...... pj-1pjpj+1 ..... p k-1pkpk+1 .... pn 1 ）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j 从左端开始计算），即j=max{i|pi 一、冒泡排序 冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 代码实现如下： 二、插入排序 插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。 直接插入排序具体算法描述如下： 1. 从第一个元素开始，该元素可以认为已经被排序 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5. 将新元素插入到下一位置中 6. 重复步骤2 伪码描述如下： 代码实现如下： 三、归并排序 归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并。直到得到长度为n的有序表，排序结束。 归并操作的工作原理如下： 1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 2、设定两个指针，最初位置分别为两个已经排序序列的起始位置 3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 4、重复步骤3直到某一指针达到序列尾 5、将另一序列剩下的所有元素直接复制到合并序列尾 代码实现如下： 1、数列全排列递归算法； 2、在不打印所有全排列时，数列长度分别为10、11、12、13时全排列花费时间测试，修改N的值重新编译即可运行测试； 3、如果需要打印全排列，打开perm函数中的注释掉的两行printf语句即可。 #include { int i = 0; if (begin == end){ for ( i = 0; i < N ; i++){ //printf("%d", list[i]); } //printf("\n"); } else{ for (i = begin; i <= end; i++) { swap(begin,i); perm(list,begin+1,end); swap(begin,i); } } } int main(int argc, char *argv[]) { int *list=a; int i; perm(list, 0, N-1); for (i = 0; i < N; i++){ printf("%d", list[i]); } return 0; } 。 算法导论复习——常见算法思想 PPT2-1： 1.堆排序（选择类排序，不稳定） （1）初始化操作：将R[1..n]构造为初始堆； （2）每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。 时间复杂度是：O（nlgn） 2.归并排序 ) 归并排序采用分治法思想的稳定的排序。算法思想是先使每个子序列有序，再使子序列段间有序。 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。 时间复杂度是：O（nlgn） 3.快速排序（交换类排序，不稳定） | （1）通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据 都比另外一部分的所有数据都要小； （2）然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 时间复杂度是：O（nlgn）。 4.分治法实现大数相乘 将a，b写成前一半数字和后一半数字相加的形式，例如若 a = 5423678，那么a1 = 542，a0 = 3678（注意若不是偶数截取较小一半） 这样a和b相乘就可以写为：a * b = { a1 * 10^(n1/2) + a0 } * { b1 * 10^(n 2/2) + b0 } （ 展开后整理得： a * b = a1*b1 * 10^[ (n1+n2)/2 ] + a1*b0 * 10^(n1/2 ) + a0*b1 * 10^(n2/2) + a0*b0 四项 这样就很容易递归的来求a * b，如果你嫌分解后的数还太大，就可以继续分解。（你可以自己规定在何时结束递归） 时间复杂度是：O（nlgn）排 列 组 合 公 式 及 排 列 组 合 算 法
算法分析与设计总结
排 列 组 合 公 式 及 排 列 组 合 算 法 ( 2 0 2 0 )
各种排序算法比较
全排列生成算法
补充全排列算法C语言实现
排序算法简介
算法设计与分析
各种排序算法的总结和比较
全排列问题的解析
全排列生成算法
8大排序算法
排 列 组 合 公 式 及 排 列 组 合 算 法
全排列的生成算法
排序算法
c语言递归算法实现数列全排列
算法分析与设计常见算法思想
相关主题
文本预览