关于全排列的算法问题

来源:百度知道 编辑:UC知道 时间:2024/05/10 10:20:59
我写了一个全排列的算法同,但是效率极差想,想请问一下有没有其它的高效算法,谢谢!

下面是我写的
#include <iostream>
#include "stdio.h"
#include <windows.h>

using namespace std;
#define MAX 100
int used[MAX];
int data[MAX];

void QPL(int n,int step)
{
int i;
if(step<n)
for(i=0;i<n;i++)
{
if(!used[i])
{
used[i]=1;
data[step]=i;
QPL(n,step+1);
used[i]=0;
}
}
else
{
for(i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
}
void main()
{
int n,start;
for(start=0;start<MAX;start++)
used[start]=0;
cout<<"input n please\n";
cin>>n;
start=GetTickCount();
QPL(n,0);
cout<<"use "<<GetTickCount()-start<<" seconds"<<endl;
}
快排??

这不是排序么?

全排列的效率高不起来,你的程序至多只能进行代码级别的优化而不可能再有什么质的飞跃了
n个数的全排列共有n!个,因此整个程序的时间复杂度是O(n!)级别的,即使1秒钟输出一亿个排列,当n稍微大一点都要不少时间,比如n=15时需要大约三个半小时
如果希望一切可能的优化,理论上的最优方式是直接用机器语言来写
如果是C++语言范围内,用scanf/printf代替cin/cout以及输出到文件而不是屏幕都可以让程序快点结束

全排列的话,QUICK SORT 效率高,上百度直接打上“QUICK SORT”就有好多代码,我觉得正是你所需要的

我的C语言的入门书里面还有“冒泡法”好象英文名叫"BUBBLE SORT", 同样百度上也有N多代码。。