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

1、基于冒泡和直接插入排序的二分查找算法實(shí)現(xiàn)及復(fù)雜度分析1.引言算法語(yǔ)言與程序設(shè)計(jì)課程設(shè)計(jì)是算法語(yǔ)言與程序設(shè)計(jì)的重要組成部分，是為強(qiáng)化算法語(yǔ)言與程序設(shè)計(jì)課程教學(xué)和實(shí)驗(yàn)教學(xué)的內(nèi)容、為提高同學(xué)們應(yīng)用算法語(yǔ)言綜合編程的能力而進(jìn)行的針對(duì)課程內(nèi)容的綜合性設(shè)計(jì)訓(xùn)練。此次的設(shè)計(jì)要求是根據(jù)指導(dǎo)老師所給出的一組數(shù)據(jù)進(jìn)行排序及分析。第一步是建立一個(gè)合適的數(shù)據(jù)文件；第二步是讀入數(shù)據(jù)；第三步是選擇冒泡和直接插入排序算法；第四步是實(shí)現(xiàn)二分查找法查找指定關(guān)鍵字對(duì)應(yīng)數(shù)據(jù)，并輸出查找結(jié)果。2.算法原理2.1 冒泡排序算法冒泡排序的基本概念是：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放

2、前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。重復(fù)以上過程，仍從第一對(duì)數(shù)開始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到最大數(shù)前的一對(duì)相鄰數(shù)，將小數(shù)放前，大數(shù)放后，第二趟結(jié)束，在倒數(shù)第二個(gè)數(shù)中得到一個(gè)新的最大數(shù)。如此下去，直至最終完成排序。2.2 直接插入排序算法直接插入排序的基本概念是：將數(shù)組分為無序區(qū)和有序區(qū)兩個(gè)區(qū)，然后不斷將無序區(qū)的第一個(gè)元素按大小順序插入到有序區(qū)中去，最終將所有無序區(qū)元素都移動(dòng)到有序區(qū)完成排序。2.3 二分查找算法二分查找算法的基本原理：

3、首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。3.算法步驟3.1 冒泡排序算法步驟及流程圖3.2 直接插入排序算法步驟及流程圖3.2 二分查找算法及流程圖二分查找又稱折半查找，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好;其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。首先，假設(shè)

4、表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功;否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。4.程序設(shè)計(jì)4.1 數(shù)據(jù)文件準(zhǔn)備應(yīng)用Microsoft Excel2010軟件建立txt文件4.2 程序總體結(jié)構(gòu)（建議采用模塊化程序設(shè)計(jì)）本程序一共包含7個(gè)模塊，如圖所示：4.3 文件讀寫打開文件代碼：FILE *in; in=fopen("。.txt","r&

5、quot;);if(in = NULL)printf("。.txt can not open!");exit(0);關(guān)閉文件代碼：fclose(in);4.4 兩次直接插入排序算法函數(shù)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 兩次冒泡排序算法函數(shù)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 二分查找法對(duì)關(guān)鍵詞進(jìn)行查找函數(shù)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雙號(hào)數(shù)據(jù)資料.txt","r");out=fopen("排序后數(shù)據(jù).txt", "w"); en=fopen("第一個(gè)關(guān)鍵后數(shù)據(jù).txt", "w");char tit720="標(biāo)識(shí)碼","地類編碼"

14、;,"地類名稱","圖斑編號(hào)","面積","周長(zhǎng)","圖斑面積"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("請(qǐng)選擇排序方法：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("請(qǐng)輸入要查找對(duì)象的地類編碼：");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("第一個(gè)關(guān)鍵后數(shù)據(jù).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