主方法分析算法复杂度

㈠ 分析个程序的算法时间复杂度

最优二叉树？时间复杂度为：N LogN

㈡ 求下面表达式的时间常数 T(t) = 21 + 0.2*exp(−t/12066 )−1.2*exp(−t/58840 )

难道是用来分析算法的时间复杂度的？但通用表达式T(n)=3/5T(n-1)+4/5T(n-2)和一般的算法时间复杂度的递推式不太一样，一般的递推式是将原问题进行分治后的综合结果，但你这个貌似子问题和原问题的关系更加微妙，所以用代入法、递归树或者主方法貌似都不行，那就用比较传统的微积分中的差分方程的方法吧：式子等价于差分方程T(n)-3/5T(n-1)-4/5T(n-2)=0，边界条件T(0)=T(1)=c；其特征方程是r^2-3/5r+4/5=0，有两个解r1=(3+√89)/10≈1.24,r2=(3-√89)/10≈-0.64，因此T(n)=C1*r1^n+C2*r2^n，根据边界条件可得T(0)=C1+C2=c；T(1)=C1*r1+C2*r2=c；解得C1=c(1-r2)/(r1-r2)≈0.87c，C2=c(r1-1)/(r1-r2)≈0.13c那么T(n)=C1*r1^n+C2*r2^n≈[0.87*1.24^n+0.13*(-0.64)^n]c可以看出，当n很大的时候，(-0.64)^n可以忽略不计，1.24^n起决定性作用，因此该递归式所代表的算法的时间复杂度T(n)是指数级的。

㈢ 编写一个求一元多项式的值Pn(x0)的算法，分析算法的时间复杂度，并在main方法中编写测试代码

技术提示：
若n为偶数：
x^n可以转换为x^(n/2)*x^(n/2)

若n为奇数：
x^n可以转换为x^(n/2)*x^(n/2)*x
所以单项的时间复杂度为log(n)

(就带到这了，作业还是自己动手吧:P)

㈣ 主曲线的算法研究

本程序定义了主曲线和确定主曲线的实际算法。多边形线算法的基本运算法则是首先确定一条直线段，然后在循环算法中通过不断加入新的顶点来增加线段的数量。在加入一个新的顶点以后，所有的顶点位置在一个内部的环中被更新。由算法所产生的曲线如图1，在这个例子中，PL运算法则和HS运算法则在计算的复杂程度和算法的完善程度上作出了比较。4段和15段，由在半圆上任意两个坐标点加入单独的高斯误差而产生。
PL算法[12]在由NIST19号专有数据库产生的单独数据元构成的图像中得到了测试。我们发现PL算法可以有效的找出没有环和分叉的图像的中间轴。这个在图2中有显示。由于中间轴可能是一些曲线连接而成而不是只有一条曲线，所以在这里我们扩展了PL算法，找出数据元的主曲线。扩展了的算法也包含了实现分段线性骨架的两个原则，一种获取字符图像近似轮廓的初始化方法和一系列用来改善由初始化方法获得的骨架结构质量的更改结构工作。为了避免混淆，我们用术语“骨架”来表示近似性中间轴的二元图像，我们把由PL算法产生出的连接曲线看做模板骨架.
应用
主曲线以前被用在图像处理领域。这种图像用来描述在卫星拍摄下的冰川及其轮廓。其主程序用了一个闭合的曲线来估算冰川的轮廓。专家们除去了HS算法[13]中不合适的部分，并且用更完善的粗略估算冰川轮廓的程序来取代HS算法的初始化步骤。此外，采用数据元集合，而不是HS算法所产生的点或线的集合，向中间轴集中的方式来扩展现有的聚合算法。初始化的曲线由SOM算法[12]的一个变量产生，在SOM算法中相互关系被定义为字符图像的一个最小二叉树。HS算法用来使曲线与模板相对应。下一步的要点与SOM算法的更新规则类似。
利用主曲线实现分段线性骨架的方法被Mahmoud、Datta和Parui[14]等人所提出。同样的方法，在SOM算法中用来最优化分段线性骨架的顶点位置。算法在构建骨架方面采用“自顶向下”的策略：近似性地从一个线性拓扑出发，然后逐步加入环和交叉到骨架中，骨架是由基于SOM算法的当前几何样式得出的。SOM算法涉及到一个获取字符图像分段线性骨架的运算法则。这种运算法则以ISODATA算法[12]为基础，ISODATA算法近似于SOM算法。
目的
主曲线算法的目的是找出与字符图像相对应的光滑的分段线性曲线。这些曲线在某个顶点彼此连接，因而在字符图像的中心平面范围内形成一个欧几里德曲线。一个欧几里德曲线G（V，S）在空间中由变量V和S确定，
主曲线算法从一个基于传统稀释方法的初始化工作开始。初始曲线找出字符图像的近似拓扑结构，然而,它不是平滑的，而且它通常包含许多假的分叉和不适合的结构元素。为了解决这两个问题，在前两步中间增加了更改结构的步骤(图3)使得主曲线算法更加有效。在更改结构步骤中，我们运用一些操作手段来调整曲线骨架结构的不完整的地方。(a)图是在初始化步骤后由主曲线算法生成的曲线骨架；（b）图是经过首次拟合-光滑步骤后生成的曲线骨架；(c)图是经过更改结构后生成的曲线骨架；(d)图是第二次拟合-光滑步骤后产生的曲线骨架(算法输出)。我们重复使用PL算法的扩展版本来构造光滑的骨架曲线，同时保持曲线与字符图像的轮廓的距离近似相等。算法建立在最小能量函数的基础之上
研究动机与意义
自1904年Spearman[13]提出线性主成分分析方法以来，由于这种方法简单且便于使用，至今还是数据统计分析的重要工具之一。线性主成分分析的原理是将数据集合投影到一个矢量，使得投影的均方差最大，由此，将这个矢量称为数据集合的第一主成分。正是这个考虑，在均方差的意义下，这个方法有两个重要的优点：其一，数据集合可以使用一个矢量来描述，从而达到减小信息描述长度的目的，其二，计算第一以及依次主成分，可以变换为求解基于数据自相关矩阵的特征值方程。另外，第一与依次主成分矢量保持正交关系，这意味着，与主成分矢量平行的矢量具有与主成分相同的性质。正是这两个原因，加上在统计上以均方差为保证，主成分分析得到广泛的应用。 由于信息描述长度与信息保持性之间存在矛盾，相对较长的信息描述长度，较短描述长度的信息描述是以损失信息保持性为代价的，而主成分分析的本质是一种在均方差意义下的统计平均。尽管它可以获得较短的信息描述长度，但是，信息保持性的代价相当大，由于信息保持性是对数据分布的规律性认识，因此，对某些问题，这个代价可接受的，但是，另外一些问题，可能就不能接受了。例如，对原始语音信号的分析，单纯的主成分分析就不一定有效。 为了说明信息描述长度与信息保持性之间的关系，下图是一个简单的例子。图5是由300个包含误差的数据点构成的余弦状分布，图5(a)的直线是数据的第一主成分线，其对余弦数据的描述长度显然较图5(b)要短，因为这些数据点将使一个线段描述，因此，只需给出线段起点和终点即可，可以认为图5(a)给出了一个短描述长度的关于数据集合的描述；显然，图5(b)对数据的信息保持性则比图5(a)要好，一方面，它与数据间的距离均方差也要小，另一方面，它勾画出原始信息的轮廓。图5(b)恰恰是本文所讨论的根据主曲线原理所获得的结果。那么，两种描述哪一个更为合理呢？显然，这没有一个一般性的答案，这取决于所需解决问题的需求。
图5 信息描述长度与信息保持之间的关系
图5也说明无监督学习较监督学习困难的原因，问题本身的病态定义导致不得不引入复杂性思想，如统计学习理论中的风险结构最小、贝叶斯学派中的贝叶斯信息准则、Kolmogrov算法[11]复杂度引出的最小描述长度等等，来寻求在信息保持性与数据描述长度之间的折衷。目前，尽管在主曲线的研究中，还存在着大量的数学问题，但是，由于其暗示的广泛应用前景，已引起计算机科学家的关注，现在应用方面已有大量的报道，如线性对撞机中对电子束运行轨迹的控制、图像处理中辨识冰原轮廓、手写体的主曲线模板化、语音识别中对声音数据的约简建模和数据可听化、生态学中寻找种群的有序分布及过程监控。同时，在认知领域Seung[14]提出感知以流形方式存在，并在神经生理学上发现整个神经细胞群的触发率可以由少量的变量组成的函数来描述，如眼的角度和头的方向，这隐含了神经元群体活动性是由其内在的低维结构所控制。主曲线本身是流形的一维形式。
原理、发展脉络以及应用
为了说明主曲线的原理、发展脉络以及应用，首先介绍其原始动机是必要的。Hastie在他关于主曲线的开创性论文中描述了其研究动机，Hastie认为主曲线与非线性回归方法的发展上具有对称性，分别是线性主成分分析与线性回归分析的非线性推广模型，Hastie写到：类似于线性回归方法的非线性推广，使用光滑曲线代替线性主成分总结数据，以求出对称变量之间的曲线，这样的曲线从数据的中部光滑地通过，且不限制于对数据的光滑线性平均，甚至不限制于数据的中部是直线，只希望使得数据点集合到曲线的正交距离最小。这个陈述清晰地指出了他的研究与主成分分析和回归分析的区别，并给出了建模的统计目标。同时，从这个陈述中也可以看出，基于直线的主成分分析只是主曲线的一个特例。因此，主曲线的提出，可以理解为基于线性的主成分分析方法向更精确描述实际世界的非线性分析方法的推广。 应该指出的是，目前，“向非线性”推广是数据统计分析的研究主流，但是，存在着不同的技术路线。
分类
最典型的研究大致可以分为两类：
其一，根据统计学习理论中的核技术，将数据集合映射到特征空间，然后，在特征空间计算数据集合的主成分，称为核主成分分析(KPCA)，这个技术路线的本质还是线性主成分分析。
其二，从数据本身的分布出发，希望找到能最好描述数据内在结构的概率分布模型，如生成式拓扑映射(Generative Topographic Mapping,缩写为GTM)，矢量量化(VQ)及主曲线，以及流形拟合等。提出“主曲线的研究与回归分析有何区别”是自然的，两者的动机都是企望求出一个函数代替数据集合，但是，两者有本质的差别：其一，一般地说，回归分析是假设数据集合的变量有因果关系，换句话说，数据的变量可以表示为一个因果关系的函数，有些是自变量，有些则是因变量。其二，回归分析一般需要给定一个数学基函数，回归分析是根据数据集合中变量的因果关系，计算这个数学基函数待定的参数。这与主曲线的研究动机完全不同。对于前者，主曲线的研究目标是解决数据变量没有必然因果关系的问题，更重要的是后者，认为事先假定数据服从某种分布(如正态分布)的方法(这与给定数学基函数，根据数据确定参数的方法类似)，对某些未知世界的解释是不合理的，因为这个假设可能是错误的，为了保证数据分析不是假设在一个错误结构下，主曲线的研究强调非参数分析。当然，这并不是完全否定了参数法这一经典方法，事实上，参数法在先验知识明确时存在相当大的好处。总之，根据上述讨论的动机，主曲线是寻找一种几何上直观、理论上完备、就解决的问题而言，这个方法与主成分分析一致，但是，主曲线的目标不是仅仅寻找一个数据集合的脊梁骨，而是希望获得数据集合的骨架。数据集合的脊梁骨可以使用线性的方法解决，但骨架就需要借助非线性方法了。应该强调的是，主曲线继承了主成分分析的众多思想，它是主成分分析的非线性推广。另外，尽管这个方法似乎与回归分析的目标类似，都是试图获得对数据集合信息长度更短的表示，但是，这个方法与回归分析完全不同，最大的差别是它不是事先给定一个基函数(或假定一个分布)，从而将问题变换为参数估计问题，而是一种非参数的方法

㈤ 如何做算法研究

一、DSP与TI

为什么提到电机控制很多人首先会联想到DSP？而谈到DSP控制总绕不过TI，首先DSP芯片是一种具有特殊结构的微处理器。该芯片的内部采用程序和数据分开的哈佛结构，具有专门的硬件乘法器，提供特殊的指令，可以用来快速地实现各种数字信号处理算法。基于DSP芯片构成的控制系统事实上是一个单片系统，因此整个控制所需的各种功能都可由DSP芯片来实现。因此，可以减小目标系统的体积，减少外部元件的个数，增加系统的可靠性。优点是稳定性好、精度高、处理速度快，目前在变频器、伺服行业有大量使用。主流的DSP厂家有美国德州仪器（Texas Instruments，TI）、ADI、motorola、杰尔等其他厂商，其中TI的TMS320系列以数字控制和运动控制为主，以价格低廉、简单易用、功能强大很是受欢迎。

二、常见的电机控制算法及研究方法

1、电机控制按工作电源种类划分：可分为直流电机和交流电机。按结构和工作原理可划分：可分为直流电动机、异步电动机、同步电动机。不同的电机所采用的驱动方式也是不相同的，这次主要介绍伺服电机，伺服主要靠脉冲来定位，伺服电机接收到1个脉冲，就会旋转1个脉冲对应的角度，从而实现位移，因此，伺服电机本身具备发出脉冲的功能，所以伺服电机每旋转一个角度，都会发出对应数量的脉冲，同时又与伺服电机接受的脉冲形成了呼应，或者叫闭环，进而很精确的控制电机的转动，从而实现精确的定位，可以达到0.001mm。伺服电机相比较普通电机优势在于控制精度、低频扭矩，过载能力，响应速度等方面，所以被广泛使用于机器人，数控机床，注塑，纺织等行业
三、PWM控制及测试结果

脉冲宽度调制是利用微处理器的数字输出来对模拟电路进行控制的一种非常有效的技术，广泛应用在从测量、通信到功率控制与变换的许多领域中，脉冲宽度调制是一种模拟控制方式，其根据相应载荷的变化来调制晶体管基极或MOS管栅极的偏置，来实现晶体管或MOS管导通时间的改变，从而实现开关稳压电源输出的改变

㈥ 怎么将C语言递归算法转化成“递归方程”该种算法时间的复杂度怎么求有固定的方法吗

不知道你是怎么得出"递归算法可以转化成方程"这个结论的呢? 如果真是这样,那么世界上恐怕很多NP问题都可以解决了. 深度优先搜索很多时候就是递归结构的,但是并没有什么办法将其转化成方程解决.

我猜想也许你说的是很特殊的一类递归问题,这类递归问题可以用数学函数来表达.例如计算阶乘的时候,n! = (n-1)*n. 那这个是怎么的出来的就真没有固定的套路,但是一般的思想是考虑如何把一个问题转化成规模更小的几个问题.

㈦ 递归算法时间复杂度怎么分析

1、递归
是指对一个问题的求解，可以通过同一问题的更简单的形式的求解来表示. 并通过问题的简单形式的解求出复杂形式的解. 递归是解决一类问题的重要方法. 递归程序设计是程序设计中常用的一种方法，它可以解决所有有递归属性的问题，并且是行之有效的. 但对于递归程序运行的效率比较低，无论是时间还是空间都比非递归程序更费，若在程序中消除递归调用，则其运行时间可大为节省. 以下讨论递归的时间效率分析方法，以及与非递归设计的时间效率的比较.
2 时间复杂度的概念及其计算方法
算法是对特定问题求解步骤的一种描述. 对于算法的优劣有其评价准则，主要在于评价算法的时间效率，算法的时间通过该算法编写的程序在计算机中运行的时间来衡量，所花费的时间与算法的规模n有必然的联系，当问题的规模越来越大时，算法所需时间量的上升趋势就是要考虑的时间度量.
算法的时间度量是依据算法中最大语句频度（指算法中某条语句重复执行的次数）来估算的，它是问题规模n的某一个函数f(n). 算法时间度量记作：T（n）=O（f（n））
它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的时间复杂度，简称时间复杂度[2].
例如下列程序段：
（1）x=x+1;（2）for(i=1;i<=n;i++) x=x+1;（3）for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1. 以上三个程序段中，语句x=x+1的频度分别为1，n，n2，则这三段程序的时间复杂度分别为O（1），O（n），O（n2）.
求解过程为：先给出问题规模n的函数的表达式，然后给出其时间复杂度T（n）.
但是在现实程序设计过程中，往往遇到的问题都是比较复杂的算法，就不能很容易地写出规模n的表达式，也比较难总结其时间复杂度. 递归函数就是属于这种情况. 下面举例说明递归函数的时间复杂度的分析方法.

㈧ 排序算法的复杂度

由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。 这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： #include<iostream>usingnamespacestd;voidBubbleSort(int*pData,intCount){intiTemp;for(inti=0;i<Count;i++){for(intj=Count-1;j>i;j--){if(pData[j]<pData[j-1]){iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp;}}}}voidmain(){intdata[7]={10,9,8,7,6,5,4};BubbleSort(data,7）;for(inti=0;i<7;i++){cout<<data[i]<<;}cout<<endl;system(PAUSE);}倒序（最糟情况)
第一轮：10，9，8，7->10，9，7，8->10，7，9，8->7，10，9，8（交换3次)
第二轮：7，10，9，8->7，10，8，9->7，8，10，9（交换2次)
第一轮：7，8，10，9->7，8，9，10（交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8，10，7，9->8，10，7，9->8，7，10，9->7，8，10，9（交换2次)
第二轮：7，8，10，9->7，8，9，10->7，8，10，9（交换1次)
（这是原撰写人的--7，8，10，9->7，8，10，9->7，8，10，9（交换0次)，第二轮应该是这样的）
第三轮：7，8，9，10->7，8，9，10（交换1次)
循环次数：6次
交换次数：3次
上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，
显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。
写成公式就是1/2*(n-1）*n。
现在注意，我们给出O方法的定义：
若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n)，则f(n) = O(g(n))。（呵呵，不要说没学好数学呀，对于编程数学是非常重要的！！！）
现在我们来看1/2*(n-1）*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1）*n<=1/2*n*n=K*g(n)。所以f(n)
=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。
再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的
有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），
复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的
原因，我们通常都是通过循环次数来对比算法。 交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。 #include<iostream.h>voidExchangeSort(int*pData，intCount){intiTemp;for(inti=0;i<Count-1;i++){//共（count-1）轮，每轮得到一个最小值for(intj=i+1;j<Count;j++){//每次从剩下的数字中寻找最小值，于当前最小值相比，如果小则交换if(pData[j]<pData[i]){iTemp=pData[i];pData[i]=pData[j];pData[j]=iTemp;}}}}voidmain(){intdata[]={10,9,8,7,6,5,4};ExchangeSort(data,sizeof(data)/sizeof(int));for(inti=0;i<sizeof(data)/sizeof(int);i++){cout<<data[i]<<;}cout<<endl;system(PAUSE);}第一轮： 9，10，8，7->8，10，9，7->7，10，9，8（交换3次)
第二轮：7，10，9，8->7，9，10，8->7，8，10，9（交换2次)
第一轮：7，8，10，9->7，8，9，10（交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8，10，7，9->8，10，7，9->7，10，8，9->7，10，8，9（交换1次)
第二轮：7，10，8，9->7，8，10，9->7，8，10，9（交换1次)
第一轮：7，8，10，9->7，8，9，10（交换1次)
循环次数：6次
交换次数：3次
从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样
也是1/2*(n-1）*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以
只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。 现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）
这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从剩下的部分中
选择最小的与第二个交换，这样往复下去。 #include<iostream.h>voidSelectSort(int*pData，intCount){intiTemp;intiPos;for(inti=0;i<Count-1;i++){iTemp=pData[i];iPos=i;for(intj=i+1;j<Count;j++){if(pData[j]<iTemp){iTemp=pData[j];iPos=j;}}pData[iPos]=pData[i];pData[i]=iTemp;}}voidmain(){intdata[]={10，9，8，7，6，5，4};SelectSort(data，7）;for(inti=0;i<7;i++)cout<<data[i]<<;cout<< ;}倒序（最糟情况)
第一轮：10，9，8，7->(iTemp=9）10，9，8，7->(iTemp=8）10，9，8，7->(iTemp=7）7，9，8，10（交换1次)
第二轮：7，9，8，10->7，9，8，10(iTemp=8）->(iTemp=8）7，8，9，10（交换1次)
第一轮：7，8，9，10->(iTemp=9）7，8，9，10（交换0次)
循环次数：6次
交换次数：2次
其他：
第一轮：8，10，7，9->(iTemp=8）8，10，7，9->(iTemp=7）8，10，7，9->(iTemp=7）7，10，8，9（交换1次)
第二轮：7，10，8，9->(iTemp=8）7，10，8，9->(iTemp=8）7，8，10，9（交换1次)
第一轮：7，8，10，9->(iTemp=9）7，8，9，10（交换1次)
循环次数：6次
交换次数：3次
遗憾的是算法需要的循环次数依然是1/2*(n-1）*n。所以算法复杂度为O(n*n)。
我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n
所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。 插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张 #include<iostream.h>voidInsertSort(int*pData，intCount){intiTemp;intiPos;for(inti=1;i<Count;i++){iTemp=pData[i];//保存要插入的数iPos=i-1;//被插入的数组数字个数while((iPos>=0)&&(iTemp<pData[iPos])){//从最后一个（最大数字）开始对比，大于它的数字往后移位pData[iPos+1]=pData[iPos];iPos--;}pData[iPos+1]=iTemp;//插入数字的位置}}voidmain(){intdata[]={10，9，8，7，6，5，4};InsertSort(data，7);for(inti=0;i<7;i++)cout<<data<<;cout<< ;}其他：
第一轮：8，10，7，9->8，10，7，9(交换0次)(循环1次)
第二轮：9，10，8，7->8，9，10，7（交换1次)（循环2次)
第一轮：8，9，10，7->7，8，9，10（交换1次)（循环3次)
循环次数：6次
交换次数：3次
其他：
第一轮：8，10，7，9->8，10，7，9（交换0次)（循环1次)
第二轮：8，10，7，9->7，8，10，9（交换1次)（循环2次)
第一轮：7，8，10，9->7，8，9，10（交换1次)（循环1次)
循环次数：4次
交换次数：2次
上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，
因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)<=
1/2*n*(n-1）<=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单
排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似
选择法），但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’
而这里显然多了一些，所以我们浪费了时间。
最终，我个人认为，在简单排序算法中，选择法是最好的。 高级排序算法中我们将只介绍这一种，同时也是目前我所知道（我看过的资料中）的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值，然后
把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使
用这个过程（最容易的方法——递归）。
1.快速排序：//这段代码编译可以通过，一运行就出错，内部的细节有些问题，我还没找到解决方法。 #include<iostream.h>voidrun(int*pData，intleft，intright){inti，j;intmiddle，iTemp;i=left;j=right;middle=pData[left];do{while((pData[i]<middle)&&(i<right))//从左扫描大于中值的数i++；while((pData[j]>middle)&&(j>left))//从右扫描大于中值的数j--;if(i<=j)//找到了一对值{//交换iTemp=pData[i];pData[i]=pData[j];pData[j]=iTemp;i++;j--;}}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）//当左边部分有值（left<j)，递归左半边if(left<j)run(pData，left，j);//当右边部分有值（right>i)，递归右半边if(right>i)run(pData，i，right);}voidQuickSort(int*pData，intCount){run(pData，0，Count-1）;}voidmain(){intdata[]={10，9，8，7，6，5，4};QuickSort(data，7）;for(inti=0;i<7;i++)cout<<data[i]<<;//原作者此处代码有误，输出因为date[i],date数组名输出的是地址cout<< ;}这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2*(n/2）......
所以共有n+2(n/2）+4(n/4）+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法复杂度为O(log2(n)*n)
其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变
成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？？呵呵，你完全
不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。
如果你担心这个问题，你可以使用堆排序，这是一种不稳定的O(log2(n)*n)算法，但是通常情况下速度要慢
于快速排序（因为要重组堆）。 双向冒泡
通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。 #include<iostream.h>inlinevoidexchange(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}voidbubblesort(int*array,intnum){inti,j,k,flag=0;for(i=0;i<num;i++){printf(%d,array[i]);}printf( );for(i=0;i<num;i++){//所有数的个数为num个flag=0;for(j=i;j<num-i-1;j++){//每循环一次最底端的数的顺序都会排好，所以初始时j=i;if(array[j]>array[j+1]){exchange(&array[j],&array[j+1]);flag=1;}}for(k=num-1-i-1;k>i;k--){//每循环一次最顶端的数据的顺序也会排好，所以初始时k=num-i-2if(array[k]<array[k-1]){exchange(&array[k],&array[k-1]);flag=1;}}if(flag==0){//如果flag未发生改变则说明未发生数据交换，则排序完成return;}}}voidmain(){intdata[]={10，9，8，7，6，5，4，3，2，1，-10，-1};bubblesort(data，12）;for(inti=0;i<12;i++)cout<<data<<;cout<< ;} 这个程序我想就没有分析的必要了，大家看一下就可以了。不明白可以在论坛上问。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index，char* strData);
CMyData();
virtual ~CMyData();
int m_iIndex;
int GetDataSize(){ return m_iDataSize; };
const char* GetData(){ return m_strDatamember; };
//这里重载了操作符：
CMyData& operator =(CMyData &SrcData);
bool operator <(CMyData& data );
bool operator >(CMyData& data );
private:
char* m_strDatamember;
int m_iDataSize;
};
////////////////////////////////////////////////////////
MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember != NULL)
delete[] m_strDatamember;
m_strDatamember = NULL;
}
CMyData::CMyData(int Index，char* strData):
m_iIndex(Index)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
m_iDataSize = strlen(strData);
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember，strData);
}
CMyData& CMyData::operator =(CMyData &SrcData)
{
m_iIndex = SrcData.m_iIndex;
m_iDataSize = SrcData.GetDataSize();
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember，SrcData.GetData());
return *this;
}
bool CMyData::operator <(CMyData& data )
{
return m_iIndex<data.m_iIndex;
}
bool CMyData::operator >(CMyData& data )
{
return m_iIndex>data.m_iIndex;
}
///////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//主程序部分
#include <iostream.h>
#include MyData.h
template <class T>
void run(T* pData，int left，int right)
{
int i，j;
T middle，iTemp;
i = left;
j = right;
//下面的比较都调用我们重载的操作符函数
middle = pData[(left+right)/2]; //求中间值
do{
while((pData<middle) && (i<right))//从左扫描大于中值的数
i++；
while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{
//交换
iTemp = pData;
pData = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值（left<j)，递归左半边
if(left<j)
run(pData，left，j);
//当右边部分有值（right>i)，递归右半边
if(right>i)
run(pData，i，right);
}
template <class T>
void QuickSort(T* pData，int Count)
{
run(pData，0，Count-1）;
}
void main()
{
CMyData data[] = {
CMyData（8，xulion)，
CMyData（7，sanzoo)，
CMyData（6，wangjun)，
CMyData（5，VCKBASE)，
CMyData（4，jacky2000)，
CMyData（3，cwally)，
CMyData（2，VCUSER)，
CMyData（1，isdong)
};
QuickSort(data，8）;
for (int i=0;i<8;i++)
cout<<data.m_iIndex<< <<data.GetData()<< ;
cout<< ;

㈨ 数据结构和算法方面的问题。关于时间复杂度的求法。关于代入法和主定理，谢谢！ 问题可能有点多，

在我看来主定理并没什么大的用处, 不仅条件需要仔细验证, 而且三种情况之间还有真空地带, 还不如掌握些常用的解递推的方法更实用.

当然, 从你的叙述来看, 你连主定理都没有理解, 所以你的首要任务是先学会用主定理.

粗略地讲, 主定理的基本思想是对
T(n)=aT(n/b)+f(n)
型的递推, 到底是 aT(n/b) 这项大还是 f(n) 这项大, 所以引出分水岭 g(n)=n^{ln b/ln a}.

对于第三题, 取 ε=ln6/ln5-1>0, 那么 f(n)=n^1=n^{ln6/ln5-ε}, 比 g(n) 低 n^ε, 然后代主定理就得到 T(n)=Θ(n^{ln6/ln5})

对于第二题, f(n)=nln n, g(n)=n, 两者间没有多项式的鸿沟, 就不能直接用主定理. 这也就是我说主定理其实没啥大用的道理.

一般来讲掌握下面的方法就可以解决这一大类递推, 其实主定理也是这样推出来的.

对于第二题, 只考虑 n=2^k 的子列, 换元之后把 T(2^k) 记成 S(k), 那么
S(k) = 2S(k-1) + 2^k * k
S(k-1) = 2S(k-1) + 2^{k-1} * (k-1)
...
S(1) = 2S(0) + 2
把左端为 S(k-j) 的式子乘上 2^j 之后全加起来就消去了所有中间项得到
S(k) = 2^k S(0) + 2^k[k+(k-1)+...+1] = 2^k*O(1) + 2^k*Θ(k^2) = Θ(2^k*k^2)
写成 T(n) 的形式就是 T(n)=Θ(n*(ln n)^2)
由于 T(n) 是单调的, 考虑上述子列足够推出渐进量级了

对于第三题, 同样的方法, 令 n=5^k, S(k) = T(5^k), 那么
S(k) = 6S(k-1) + 5^k
S(k-1) = 6S(k-2) + 5^{k-1}
...
S(1) = 6S(0) + 5
把左端为 S(k-j) 的式子乘上 6^j 之后全加起来就消去了所有中间项得到
S(k) = 6^k S(0) + [5^k + 6*5^{k-1} + ... + 6^{k-1}*5]
= 6^k*Θ(1) + 5*Θ(6^k) = Θ(6^k)
注意后面那堆求和是等比数列求和
换回去就得到 T(n) = Θ(n^{ln6/ln5})

一般方法大致就是这样, 当然你得会选择合适的变量代换, 也得掌握一些基本的求和, 有时候求和不易求可以用积分来代替, 不影响渐进量级

㈩ C++中排序的算法分析(文字分析)

排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。
而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。
对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。
我将按照算法的复杂度，从简单到难来分析算法。
第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N*N)（因为没有使用word,所以无法打出上标和下标）。
第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念，所以这里不于讨论。
第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。
第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序（抱歉，里面使用了一些论坛专家的呢称）。

现在，让我们开始吧：

一、简单排序算法
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。
1.冒泡法：
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：
#include <iostream.h>
void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
for(int j=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp = pData[j-1];
pData[j-1] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)
第二轮：7,10,9,8->7,10,8,9->7,8,10,9(交换2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)
第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，
显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。
写成公式就是1/2*(n-1)*n。
现在注意，我们给出O方法的定义：
若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。（呵呵，不要说没
学好数学呀，对于编程数学是非常重要的！！！）
现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)
=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。
再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因，我们通常都是通过循环次数来对比算法。

2.交换法：
交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=i+1;j<Count;j++)
{
if(pData[j]<pData[i])
{
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次)
第二轮：7,10,9,8->7,9,10,8->7,8,10,9(交换2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次)
第二轮：7,10,8,9->7,8,10,9->7,8,10,9(交换1次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。
3.选择法：
现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中选择最小的与第二个交换，这样往复下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=0;i<Count-1;i++)
{
iTemp = pData[i];
iPos = i;
for(int j=i+1;j<Count;j++)
{
if(pData[j]<iTemp)
{
iTemp = pData[j];
iPos = j;
}
}
pData[iPos] = pData[i];
pData[i] = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次)
第二轮：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)
第一轮：7,8,9,10->(iTemp=9)7,8,9,10(交换0次)
循环次数：6次
交换次数：2次
其他：
第一轮：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次)
第二轮：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)
第一轮：7,8,10,9->(iTemp=9)7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。
我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n
所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。

4.插入法：
插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=1;i<Count;i++)
{
iTemp = pData[i];
iPos = i-1;
while((iPos>=0) && (iTemp<pData[iPos]))
{
pData[iPos+1] = pData[iPos];
iPos--;
}
pData[iPos+1] = iTemp;
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->9,10,8,7(交换1次)(循环1次)
第二轮：9,10,8,7->8,9,10,7(交换1次)(循环2次)
第一轮：8,9,10,7->7,8,9,10(交换1次)(循环3次)
循环次数：6次
交换次数：3次
其他：
第一轮：8,10,7,9->8,10,7,9(交换0次)(循环1次)
第二轮：8,10,7,9->7,8,10,9(交换1次)(循环2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)(循环1次)
循环次数：4次
交换次数：2次
上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，
因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)<=
1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单
排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似
选择法），但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’
而这里显然多了一些，所以我们浪费了时间。
最终，我个人认为，在简单排序算法中，选择法是最好的。

二、高级排序算法：
高级排序算法中我们将只介绍这一种，同时也是目前我所知道（我看过的资料中）的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值，然后
把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使
用这个过程（最容易的方法——递归）。
1.快速排序：
#include <iostream.h>
void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //求中间值
do{
while((pData[i]<middle) && (i<right))//从左扫描大于中值的数
i++;
while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{
//交换
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left<j)，递归左半边
if(left<j)
run(pData,left,j);
//当右边部分有值(right>i)，递归右半边
if(right>i)
run(pData,i,right);
}
void QuickSort(int* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
QuickSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法复杂度为O(log2(n)*n)
其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变
成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？？呵呵，你完全
不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。
如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。
三、其他排序
1.双向冒泡：
通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。
代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。
写这段代码的作者认为这样可以在冒泡的基础上减少一些交换（我不这么认为，也许我错了）。
反正我认为这是一段有趣的代码，值得一看。
#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
int iTemp;
int left = 1;
int right =Count -1;
int t;
do
{
//正向的部分
for(int i=right;i>=left;i--)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
left = t+1;
//反向的部分
for(i=left;i<right+1;i++)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
right = t-1;
}while(left<=right);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
Bubble2Sort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
2.SHELL排序
这个排序非常复杂，看了程序就知道了。
首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。
工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序
以次类推。
#include <iostream.h>
void ShellSort(int* pData,int Count)
{
int step[4];
step[0] = 9;
step[1] = 5;
step[2] = 3;
step[3] = 1;
int iTemp;
int k,s,w;
for(int i=0;i<4;i++)
{
k = step[i];
s = -k;
for(int j=k;j<Count;j++)
{
iTemp = pData[j];
w = j-k;//求上step个元素的下标
if(s ==0)
{
s = -k;
s++;
pData[s] = iTemp;
}
while((iTemp<pData[w]) && (w>=0) && (w<=Count))
{
pData[w+k] = pData[w];
w = w-k;
}
pData[w+k] = iTemp;
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
ShellSort(data,12);
for (int i=0;i<12;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
呵呵，程序看起来有些头疼。不过也不是很难，把s==0的块去掉就轻松多了，这里是避免使用0
步长造成程序异常而写的代码。这个代码我认为很值得一看。
这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法：“由于复杂的数学原因
避免使用2的幂次步长，它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并
“超出本书讨论范围”的原因（我也不知道过程），我们只有结果了。

四、基于模板的通用排序：
这个程序我想就没有分析的必要了，大家看一下就可以了。不明白可以在论坛上问。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index,char* strData);
CMyData();
virtual ~CMyData();
int m_iIndex;
int GetDataSize(){ return m_iDataSize; };
const char* GetData(){ return m_strDatamember; };
//这里重载了操作符：
CMyData& operator =(CMyData &SrcData);
bool operator <(CMyData& data );
bool operator >(CMyData& data );
private:
char* m_strDatamember;
int m_iDataSize;
};
////////////////////////////////////////////////////////
MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0),
m_iDataSize(0),
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember != NULL)
delete[] m_strDatamember;
m_strDatamember = NULL;
}
CMyData::CMyData(int Index,char* strData):
m_iIndex(Index),
m_iDataSize(0),
m_strDatamember(NULL)
{
m_iDataSize = strlen(strData);
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,strData);
}
CMyData& CMyData::operator =(CMyData &SrcData)
{
m_iIndex = SrcData.m_iIndex;
m_iDataSize = SrcData.GetDataSize();
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,SrcData.GetData());
return *this;
}
bool CMyData::operator <(CMyData& data )
{
return m_iIndex<data.m_iIndex;
}
bool CMyData::operator >(CMyData& data )
{
return m_iIndex>data.m_iIndex;
}
///////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//主程序部分
#include <iostream.h>
#include "MyData.h"
template <class T>
void run(T* pData,int left,int right)
{
int i,j;
T middle,iTemp;
i = left;
j = right;
//下面的比较都调用我们重载的操作符函数
middle = pData[(left+right)/2]; //求中间值
do{
while((pData[i]<middle) && (i<right))//从左扫描大于中值的数
i++;
while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{
//交换
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left<j)，递归左半边
if(left<j)
run(pData,left,j);
//当右边部分有值(right>i)，递归右半边
if(right>i)
run(pData,i,right);
}
template <class T>
void QuickSort(T* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
CMyData data[] = {
CMyData(8,"xulion"),
CMyData(7,"sanzoo"),
CMyData(6,"wangjun"),
CMyData(5,"VCKBASE"),
CMyData(4,"jacky2000"),
CMyData(3,"cwally"),
CMyData(2,"VCUSER"),
CMyData(1,"isdong")
};
QuickSort(data,8);
for (int i=0;i<8;i++)
cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n";
cout<<"\n";
}