1. 序言
文中详细介绍了常见的排序组合算法，包含全排列算法，全组合算法，m数量选n个组合算法等。
2. 排序优化算法
普遍的排序优化算法有：
- (A)字典序法
- (B)增长进位制数法
- (C)下降进位制数法
- (D)邻位互换法
- (E)递归法
详细介绍常见的二种：
(1) 字典序法
对给出的字段名中的标识符要求了一个依次关联，在这个基础上依照次序先后造成每一个排序。
[例]字段名{1,2,3},较小的数据较先,那样按字典序转化成的全排列是:123,132,213,231,312,321。转化成给出全排列的下一个排序 说白了一个的下一个便是这一个与下一个中间沒有词典次序中邻近的字符串数组。这就规定这一个与下一个有尽量长的一同作为前缀，也即转变限定在尽量短的后缀名上。
优化算法观念：
设P是[1,n]的一个全排列。
P=P1P2…Pn=P1P2…Pj-1PjPj 1…Pk-1PkPk 1…Pn , j=max{i|Pi<Pi 1}, k=max{i|Pi>Pj} ,互换Pj，Pk，将Pj 1…Pk-1PjPk 1…Pn旋转， P’= P1P2…Pj-1PkPn…Pk 1PjPk-1…Pj 1即P的下一个
事例:839647521的下一个排序.
从最右逐渐,寻找第一个比右侧小的数字4(由于4<7，而7>5>2>1),再从最右逐渐,寻找4右侧比4大的数字5(由于4>2>1而4<5),互换4、5,这时5右侧为7421,颠倒为1247,即得下一个排序:839651247.用此方式写成全排列的非递归算法以下
该方式适用数据信息反复，且在C STL中被选用。
(2) 递归法
设一组数p = {r1, r2, r3, … ,rn}, 全排列为perm(p)，pn = p – {rn}。则perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), … , rnperm(pn)。当n = 1时perm(p} = r1。
如：求{1, 2, 3, 4, 5}的全排列
1、最先看最终两个数4, 5。 他们的全排列为4 5和5 4, 就是以8开头的5的全排列和以5开始的4的全排列。
因为一个数的全排列便是其自身，进而获得之上結果。
2、再看后三个数3, 4, 5。他们的全排列为3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六组数。
就是以3开始的和4,5的全排列的组成、以8开头的和3,5的全排列的组成和以5开始的和3,4的全排列的组成.
#include <stdio.h>
int n = 0;
void swap(int *a, int *b) {
int m;
m = *a;
*a = *b;
*b = m;
}
void perm(int list[], int k, int m) {
int i;
if(k > m) {
for(i = 0; i <= m; i )
printf("%d ", list[i]);
printf("\n");
n ;
} else {
for(i = k; i <= m; i ) {
swap(&list[k], &list[i]);
perm(list, k 1, m);
swap(&list[k], &list[i]);
}
}
}
int main() {
int list[] = {1, 2, 3, 4, 5};
perm(list, 0, 4);
printf("total:%d\n", n);
return 0;
}
3. 组合算法
3.1 全组成
在这里详细介绍二进制转化法，即，将每一个组成与一个二进制数相匹配起來，枚举类型二进制的另外，枚举类型每一个组成。如字符串数组：abcde
00000 <– –> null
00001<– –> e
00010 <– –> d
… …
11111 <– –> abcde
3.2 从n选中m数量
(1) 递归
a. 最先从n数量中选择序号最大的数，随后在剩余的n-一个数里边选择m-一个数，直至从n-(m-1)数量中选择一个数截止。
b. 从n数量中选择序号次小的一个数，执行1步，直至当今可选序号最大的数为m。
下边是递归方法的完成：
/// 求从二维数组a[1..n]中随意选择m个原素的全部组成。
/// a[1..n]表明备选集，n为备选集尺寸，n>=m>0。
/// b[1..M]用于储存当今组成中的原素(这儿储存的是原素字符)，
/// 变量定义M表明符合条件的一个组成中原素的数量，M=m，这两个主要参数仅用于輸出結果。
voidcombine( inta[], intn, intm, intb[], constint M )
{
for(inti=n; i>=m; i--) // 留意这儿的循环系统范畴
{
b[m-1] = i - 1;
if(m > 1)
combine(a,i-1,m-1,b,M);
else // m == 1, 輸出一个组成
{
for(intj=M-1; j>=0; j--)
cout << a[b[j]] << " ";
cout << endl;
}
}
}
(2) 01转换法
本程序流程的构思是开一个二维数组，其字符表明1到n数量，二维数组原素的数值1表明其意味着的数被选定，为0则没选定。
最先复位，将二维数组前n个原素置1，表明第一个组成为前n数量。
随后从左往右扫描仪二维数组原素值的“10”组成，寻找第一个“10”组成后将其变成“01”组成，另外将其左侧的全部“1”所有挪动到二维数组的最左方。
当第一个“1”挪动到二维数组的n-m的部位，即n个“1”所有挪动到最右方时，就获得了最后一个组成。
比如求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
4. 参考文献
(1) http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html
(2) http://comic.sjtu.edu.cn/thucs/GD_jsj_025y/text/chapter01/sec05/default.htm
(3) http://blog.csdn.net/sharpdew/archive/2006/05/25/755074.aspx
(4) http://xiaomage.blog.51cto.com/293990/74094
