基于冒泡和直接插入排序的

1、基于冒泡和直接插入排序的二分查找算法实现及复杂度分析1.引言算法语言与程序设计课程设计是算法语言与程序设计的重要组成部分，是为强化算法语言与程序设计课程教学和实验教学的内容、为提高同学们应用算法语言综合编程的能力而进行的针对课程内容的综合性设计训练。此次的设计要求是根据指导老师所给出的一组数据进行排序及分析。第一步是建立一个合适的数据文件；第二步是读入数据；第三步是选择冒泡和直接插入排序算法；第四步是实现二分查找法查找指定关键字对应数据，并输出查找结果。2.算法原理2.1 冒泡排序算法冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放

2、前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到最大数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最大数。如此下去，直至最终完成排序。2.2 直接插入排序算法直接插入排序的基本概念是：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。2.3 二分查找算法二分查找算法的基本原理：

3、首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。3.算法步骤3.1 冒泡排序算法步骤及流程图3.2 直接插入排序算法步骤及流程图3.2 二分查找算法及流程图二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设

4、表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功;否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。4.程序设计4.1 数据文件准备应用Microsoft Excel2010软件建立txt文件4.2 程序总体结构（建议采用模块化程序设计）本程序一共包含7个模块，如图所示：4.3 文件读写打开文件代码：FILE *in; in=fopen("。.txt","r&

5、quot;);if(in = NULL)printf("。.txt can not open!");exit(0);关闭文件代码：fclose(in);4.4 两次直接插入排序算法函数void insertion_sort(data p)int i, j, n, k;for (i = 1; i < 200; i+)data r;j = i - 1;r = pi;n = pi.dileibm;while (j >= 0 && pj.dileibm>n)pj + 1 = pj;j-;pj + 1 = r;if (pj.dileibm = pj

6、+ 1.dileibm)k = j;n = pj + 1.tubanbh;while (k >= 0 && pk.tubanbh > n)pk + 1 = pk;k-;if (pk.dileibm < pk + 1.dileibm)break;pk + 1 = r;4.5 两次冒泡排序算法函数void bubble_sort(data p)int i, j,k,n,a200,b200;data t;for (i = 1; i < 200; i+)for (j = 0; j < 200-i; j+)if (pj.dileibm > pj+1.d

7、ileibm)t = pj;pj = pj+1;pj+1 = t;for(i=0,j=1;i<200;i+) if(pi.dileibm!=pi+1.dileibm) aj=i+1,bj-1=i,j+; n=j; a0=0,bj=200;for(i=0;i<n;i+)for (k=0; k <bi-ai; k+) for (j=ai; j < bi-k; j+)if (pj.tubanbh > pj+1.tubanbh)t = pj;pj = pj+1;pj+1 = t; 4.6 二分查找法对关键词进行查找函数int fun(int arr, int low, i

8、nt high, int key)int mid = low + (high - low) / 2;if (low > high)return -1;if(arrlow=key)return low;if(arrhigh=key)return high;elseif (arrmid = key)return mid;else if (arrmid > key)return fun(arr, low, mid - 1, key);elsereturn fun(arr, mid + 1, high, key);4.6完整程序代码#include<stdio.h>#inclu

9、de<stdlib.h>#include<conio.h>struct dataint biaoshima,dileibm,tubanbh;char s12;double area,c,tuban;struct dateint biaoshima,dileibm,tubanbh;char s12;double area,c,tuban;void insertion_sort(data p)int i, j, n, k;for (i = 1; i < 200; i+)data r;j = i - 1;r = pi;n = pi.dileibm;while (j &g

10、t;= 0 && pj.dileibm>n)pj + 1 = pj;j-;pj + 1 = r;if (pj.dileibm = pj + 1.dileibm)k = j;n = pj + 1.tubanbh;while (k >= 0 && pk.tubanbh > n)pk + 1 = pk;k-;if (pk.dileibm < pk + 1.dileibm)break;pk + 1 = r;void bubble_sort(data p)int i, j,k,n,a200,b200;data t;for (i = 1; i <

11、; 200; i+)for (j = 0; j < 200-i; j+)if (pj.dileibm > pj+1.dileibm)t = pj;pj = pj+1;pj+1 = t;for(i=0,j=1;i<200;i+)if(pi.dileibm!=pi+1.dileibm)aj=i+1,bj-1=i,j+;n=j;a0=0,bj=200;for(i=0;i<n;i+)for (k=0; k <bi-ai; k+)for (j=ai; j < bi-k; j+)if (pj.tubanbh > pj+1.tubanbh)t = pj;pj = p

12、j+1;pj+1 = t;int fun(int arr, int low, int high, int key)int mid = low + (high - low) / 2;if (low > high)return -1;if(arrlow=key)return low;if(arrhigh=key)return high;elseif (arrmid = key)return mid;else if (arrmid > key)return fun(arr, low, mid - 1, key);elsereturn fun(arr, mid + 1, high, key

13、);int main()FILE *in,*out,*en;char c;data dat200;date dat1200;int i,j,n,m,x200,y200,N=200,M=200,t1=0;in=fopen("2015070202双号数据资料.txt","r");out=fopen("排序后数据.txt", "w"); en=fopen("第一个关键后数据.txt", "w");char tit720="标识码","地类编码"

14、;,"地类名称","图斑编号","面积","周长","图斑面积"for(i=0;i<200;i+)fscanf(in,"%d %d %s %d %lf %lf %lf",&dati.biaoshima,&dati.dileibm,dati.s,&dati.tubanbh,&dati.area,&dati.c,&dati.tuban);printf("请选择排序方法：n1.插入排序n2.冒泡排序n");c

15、 = getch();switch (c)case '1':insertion_sort(dat); break;case '2':bubble_sort(dat); break;default:printf("输入有误！"); exit(0);printf("%-10s %-8s %-8s %-8s %-16s %-14s %-10s",tit0,tit1,tit2,tit3,tit4,tit5,tit6);fprintf(out,"%12s %12s %12s %8s %16s %16s %16sn"

16、;,tit0,tit1,tit2,tit3,tit4,tit5,tit6);for (i = 0; i<200; i+)xi = dati.dileibm;printf("%-10d %-8d %-8s %-8d %-16lf %-14lf %-10.2lf", dati.biaoshima,dati.dileibm,dati.s,dati.tubanbh,dati.area,dati.c,dati.tuban);fprintf(out, "%12d %12d %12s %8d %16lf %16lf %16.2lfn",dati.biaoshim

17、a,dati.dileibm,dati.s,dati.tubanbh,dati.area,dati.c,dati.tuban);printf("请输入要查找对象的地类编码：");scanf("%d", &n);for (i = 0; i <200; i+)yi = fun(x, 0, M-1-i, n);if (yi = -1)break;if (yi>=0)printf("%-10d %-8d %-8s %-8d %-16lf %-14lf %-10.2lf", datyi.biaoshima, datyi.di

18、leibm, datyi.s, datyi.tubanbh, datyi.area, datyi.c, datyi.tuban);fprintf(en,"%-10d %-8d %-8s %-8d %-16lf %-14lf %-10.2lfn",datyi.biaoshima, datyi.dileibm, datyi.s, datyi.tubanbh, datyi.area, datyi.c, datyi.tuban);t1+;for (j = yi; j < N - 1-i; j+)datj = datj + 1;xj = xj + 1;fclose(en);en=fopen("第一个关键后数据.txt", "r");for(i=0;i<t1;i+)fscanf(en,"%d %d %s %d %lf %lf %lf",&dat1i.biaoshima,&dat1i.dileibm,dat1i.s,&dat1i.tubanbh,&dat1i.area,&dat1i.c,&dat1i.tuban); print