有关算法快速排序的问题

先说一下快速排序中最好的排序情况，最好的情况下，每次进行一次分区，我们会把一个序列刚好分为几近相等的两个子序列，这个情况也每次递归调用的是时候也就刚好处理一半大小的子序列。这看起来其实就是一个完全二叉树，树的深度为 O(logn)，所以需要做 O(logn) 次嵌套调用。但是在同一层次结构的两个程序调用中，不会处理为原来数列的相同部分。因此，程序调用的每一层次结构总共全部需要 O(n) 的时间。所以这个算法在最好情况下的时间复杂度为 O(nlogn)。

但是将递减数据调用快速排序进行递增排序，是快速排序中情况最差的，你可以试想一下，假设每次分区后都出现子序列的长度一个为 1 一个为 n-1，这会导致我们的表达式变成：

T(n) = O(n) + T(1) + T(n-1) = O(n) + T(n-1)

这是时间复杂度就是 O(n²)。

void

show(int

n,int

len

,char

str[],

char

p[],int

*i){/*函数功能说明：

密码穷举法

递归算法参数说明：len

密码可选元素的个数，实际等于

strlen(str)

n

密码位数。

str[]密码表。

*p

密码排列组合的临时存档*/int

an--for(a=0

a

<

len

a++){p[n]=str[a]

if(n==0)printf("%d:%s

",(*i)++,p)

if(n0)show(n,len

,

str,p,i)}}

/*驱动程序

用于测试*/

int

main(void){char

str[]="abcdef"//密码表

可选元素集合可根据选择修改

int

n=4//密码位数，根据具体应用而定。

int

len=strlen(str)//用于密码元素集合计数。

char

p[20]//存放排列组合的密码，用于输出。

int

num=0//存放统计个数的整数值，

int

*i=#//计数器

地址。

p[n]='\0'//这个不用说啦。

printf("\n%d

位密码,每个密码有%d个选择的话，共有：%d个组合。\n",n,len,*i)return

0}

最低0.27元/天开通百度文库会员，可在文库查看完整内容>

原发布者:ON9V4Xr2gU9J7

全排列以及相关算法在程序设计过程中，我们往往要对一个序列进行全排列或者对每一个排列进行分析。全排列算法便是用于产生全排列或者逐个构造全排列的方法。当然，全排列算法不仅仅止于全排列，对于普通的排列，或者组合的问题，也可以解决。本文主要通过对全排列以及相关算法的介绍和讲解、分析，让读者更好地了解这一方面的知识，主要涉及到的语言是C和C++。本文的节数：1.全排列的定义和公式：2.时间复杂度：3.列出全排列的初始思想：4.从第m个元素到第n个元素的全排列的算法：5.全排列算法：6.全排列的字典序：7.求下一个字典序排列算法：8.C++STL库中的next_permutation()函数：（#include）9.字典序的中介数，由中介数求序号：10.由中介数求排列：11.递增进位制数法：12.递减进位制数法：13.邻位对换法：14.邻位对换法全排列：15.邻位对换法的下一个排列：16.邻位对换法的中介数：17.组合数的字典序与生成：由于本文的，内容比较多，所以希望读者根据自己的要求阅读，不要一次性读完，有些章节可以分开读。第1节到第5节提供了全排列的概念和一个初始的算法。第6节到第8节主要讲述了字典序的全排列算法。第9到第10节讲了有关字典序中中介数的概念。第11到第12节主要介绍了不同的中介数方法，仅供扩展用。第13节到15节介绍了邻位对换法的全排的有关知识。16节讲了有关邻位对换法的中介数，仅供参考。第17节讲了

---