算法设计与分析 - 总结0

个记录开始扫描序列，在n-i+1个记录中找到关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。 时间复杂性：O(n2) 伪代码：

冒泡排序

算法描述：冒泡排序开始的时候扫描整个序列，在扫描过程中两两比较相邻记录，如果反序则交换，最终，最大记录就能被“沉到”了序列的最后一个位置，第二趟扫描将第二大记录“沉到”了倒数第二个位置，重复上述操作，直到n-1趟扫描后，整个序列就排好序了。 冒泡排序，O(n2)

5、 算法设计题：习题3-3，3-6，3-8，3-11，3-13

3-3 对于KMP算法中求next数组问题，设计一个蛮力算法，并分析其时间性能。

1. voidGetNext(char T[ ], int next[ ]) 2. {

3. next[1]=0; 4. next[2]=1; 5. j=T[0],k=0; 6. for(;j>2;j--){

7. for(n=j-2;n>=1;n--){//n为要比较的前缀的最后一个字符的下标 8. m=j-n;//m为要比较的后缀的第一个字符的下标 9. for(i=1;i<=n;i++) 10. {

11. if(T[i]!=T[m+i-1])break; 12. }

13. if(i==n+1){next[j]=n+1;break;} 14. }

15. if(n==0)next[j]=1; 16. } 17. }

3-4 假设在文本“ababcabccabccacbab”中查找模式 “abccac”,求分别采用BF算法和KMP算法进行串匹配过程中的字符比较次数。

由此可知，用BF算法一共要进行3+1+4+1+1+6+1+1+1+6=25次比较方能匹配出

KMP算法：next[]={,0,1,1,1,1,2};

由此可知，用KMP算法一共要进行3+4+6+5=18次比较方能匹配出

参考代码如下：

排列最终存储在长度为n的阶乘，元素类型为指针的数组中，数组指向一个排列，具体的排列数据存储在数组中。

1. int fabs(int n) 2. {

3. int r=1;

4. for(inti=n;i>1;i--) 5. r=r*i; 6. return r; 7. 8. } 9.

10. //排列存储在数组中

11. void getArrangement(int**&s,int n) 12. {

13. int * p,*q; 14. int * *s1; 15. int i,j,k,l,m,o; 16. s=new int *[1]; 17. s[0]=newint[1]; 18. s[0][0]=1; 19. for(i=2;i<=n;i++)