经典c++编程实例.pdf

经典c++编程实例.pdf

ID:52241074

大小:461.55 KB

页数:54页

时间:2020-03-25

经典c++编程实例.pdf_第1页
经典c++编程实例.pdf_第2页
经典c++编程实例.pdf_第3页
经典c++编程实例.pdf_第4页
经典c++编程实例.pdf_第5页
资源描述:

《经典c++编程实例.pdf》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、1.冒泡法:这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡:#includevoidBubbleSort(int*pData,intCount){intiTemp;for(inti=1;i=i;j--){if(pData[j]

2、eSort(data,7);for(inti=0;i<7;i++)cout<

3、one_turn

4、two_turn

5、three_turn

6、four_turn

7、five_turn

8、six_turn10101010101049999941088884997774888664777754666664555555通过上图可以看出,冒泡法形象的描述来,4这个元素就像一个气泡逐渐冒到上面来了。我们排序的有7个元素,最坏的情况全部倒序,4这个元素要冒上来需要6次。因此,n个元素,最坏的情况,需要

9、移动:1+2+3+...+(n-1)=1/2*n(n-1)次。倒序(最糟情况)第一轮: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次)

10、循环次数: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(

11、n)。所以f(n)=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的有序程度有极大的关系,当数据处于倒序的情况时,交换次数同循环一样(每次循环判断都会交换),复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因,我们通常都是通过循环次数来对比算法。2.交换法:交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。#includevoidExchangeSort

12、(int*pData,intCount){intiTemp;for(inti=0;i

13、one_t

14、urn

15、two_turn

16、three_turn

17、four_turn

18、five_turn

19、six_turn10987654910101010101088999997778888666677755555664444445从上面的算法来看,基本和冒泡法的效率一样。倒序(最糟情况)第一轮: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,

20、10,7,9->7,10

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。