快速排序及二分查找-實(shí)驗(yàn)四

...wd......wd......wd...電子科技大學(xué)實(shí)驗(yàn)報告課程名稱：數(shù)據(jù)構(gòu)造與算法學(xué)生姓名：陳*浩學(xué)號：*************點(diǎn)名序號：***指導(dǎo)教師：錢**實(shí)驗(yàn)地點(diǎn)：根基實(shí)驗(yàn)大樓A508實(shí)驗(yàn)時間：2015.6.32014-2015-2學(xué)期信息與軟件工程學(xué)院實(shí)驗(yàn)報告(四)學(xué)生姓名：陳*浩學(xué)號：*************導(dǎo)教師：錢**實(shí)驗(yàn)地點(diǎn)：根基實(shí)驗(yàn)大樓A508實(shí)驗(yàn)時間：2015.6.3實(shí)驗(yàn)室名稱：軟件實(shí)驗(yàn)室實(shí)驗(yàn)工程名稱：數(shù)據(jù)構(gòu)造與算法—快速排序與二分查找實(shí)驗(yàn)學(xué)時：4四、實(shí)驗(yàn)原理：快速排序的根本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩局部，其中一局部的所有數(shù)據(jù)都比另外一不局部的所有數(shù)據(jù)都要小，然后再按次方法對這兩局部數(shù)據(jù)分別進(jìn)展快速排序，整個排序過程可以遞歸進(jìn)展，以此到達(dá)整個數(shù)據(jù)變成有序序列。假設(shè)要排序的數(shù)組是A[1]……A[N]，首先任意選取一個數(shù)據(jù)〔通常選用第一個數(shù)據(jù)〕作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是：1〕設(shè)置兩個變量I、J，排序開場的時候I：=1，J：=N2〕以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A[1]；3〕從J開場向前搜索，即〔J：=J-1〕，找到第一個小于X的值，兩者交換；4〕從I開場向后搜索，即〔I：=I+1〕，找到第一個大于X的值，兩者交換；5〕重復(fù)第3、4步，直到I=J。二分法查找〔折半查找〕的根本思想：〔1〕確定該區(qū)間的中點(diǎn)位置：mid=〔low+high〕/2

min代表區(qū)間中間的結(jié)點(diǎn)的位置，low代表區(qū)間最左結(jié)點(diǎn)位置，high代表區(qū)間最右結(jié)點(diǎn)位置〔2〕將待查a值與結(jié)點(diǎn)mid的關(guān)鍵字〔下面用R[mid].key〕比擬，假設(shè)相等，則查找成功，否則確定新的查找區(qū)間：A)如果R[mid].key>a，則由表的有序性可知，R[mid].key右側(cè)的值都大于a，所以等于a的關(guān)鍵字如果存在，必然在R[mid].key左邊的表中,這時high=mid-1;B)如果R[mid].key<a,則等于a的關(guān)鍵字如果存在，必然在R[mid].key右邊的表中。這時low=mid；C)如果R[mid].key=a，則查找成功?！?〕下一次查找針對新的查找區(qū)間，重復(fù)步驟〔1〕和〔2〕〔4〕在查找過程中，low逐步增加，high逐步減少，如果high<low，則查找失敗。五、實(shí)驗(yàn)?zāi)康模罕緦?shí)驗(yàn)通過實(shí)現(xiàn)快速排序和折半查找算法，使學(xué)生理解如何實(shí)現(xiàn)快速查找和排序的根本算法思想。通過練習(xí)，加強(qiáng)對算法的理解，提高編程能力。六、實(shí)驗(yàn)內(nèi)容：〔1〕實(shí)現(xiàn)數(shù)據(jù)序列的輸入;〔2〕實(shí)現(xiàn)快速排序算法,并對輸入的序列排序后輸出；〔3〕實(shí)現(xiàn)折半查找算法,并在步驟(2)排序后的序列上,進(jìn)展任意地查找,并輸出查詢結(jié)果。七、實(shí)驗(yàn)器材〔設(shè)備、元器件〕：PC機(jī)一臺，裝有C/C++語言集成開發(fā)環(huán)境。八、數(shù)據(jù)構(gòu)造及程序/*************************************************************快速查找與二分排序****陳家浩****2015.6.6**********************************************************/#include<stdio.h>#defineMAX100intData[MAX+1]={0};intQuick_Part(intData[],inti,intj);//一趟排序intQuick_Sort(intData[],ints,intt);//遞歸排序intQuick_Find(intData[],intdata,intn);//二分查找intmain(void){ intchoose=-1;//選擇功能 inti,k,data; intn;//數(shù)據(jù)序列長度 while(1) { printf("+-----排序與查找-----+\n" "|1:輸入數(shù)據(jù)序列|\n" "|2:序列排序|\n" "|3:查找信息|\n" "|0:退出|\n" "+-----++++++++++-----+\n" "請選擇："); scanf("%d",&choose); switch(choose) { case1: printf("請輸入序列數(shù)據(jù)個數(shù)："); scanf("%d",&n); if(n>MAX){ printf("數(shù)據(jù)過多!\n\n"); break; } else{ printf("請輸入數(shù)據(jù)序列：\n"); for(i=1;i<=n;i++) scanf("%d",&Data[i]); printf("讀取成功！\n\n"); } break; case2: Quick_Sort(Data,1,n);//快速排序 printf("排序成功！序列如下：\n"); for(i=1;i<=n;i++) printf("%d",Data[i]); printf("\n\n"); break; case3: printf("請輸入待查找的數(shù)據(jù)："); scanf("%d",&data); k=Quick_Find(Data,data,n);//二分法查找 if(k) printf("查找成功！數(shù)據(jù)\"%d\"位于序列第%d位。\n\n",data,k); else printf("查找失?。]有你要查找的數(shù)據(jù)！\n\n"); break; default: return0; } }}intQuick_Part(intData[],inti,intj){//快速排序 Data[0]=Data[i]; while(i<j){ while((i<j)&&(Data[0]<=Data[j])) j--;//右邊目標(biāo)元比劃分元大，j往左移 if(i<j){ Data[i]=Data[j];//比劃分元小的關(guān)鍵字交換到左邊 i++; } while((i<j)&&(Data[0]>=Data[i])) i++;//左邊目標(biāo)元比劃分元小，i往右移 if(i<j){ Data[j]=Data[i];//比劃分元大的關(guān)鍵字交換到右邊 j--; } } Data[i]=Data[0];//劃分元存入正確位置 returni;//返回劃分元的位置}intQuick_Sort(intData[],ints,intt){ inti=Quick_Part(Data,s,t);//調(diào)用劃分過程將順序表分成兩局部 if(i>s) Quick_Sort(Data,s,i-1);//遞歸調(diào)用排序 if(i<t) Quick_Sort(Data,i+1,t);//遞歸調(diào)用排序 return0;}intQuick_Find(intData[],intdata,intn){//二分查找 intlow=1; inthigh=n; intmid; while(low<=high){ mid=(low+high)/2;//中間位置 if(data==Data[mid]) returnmid;//查找成功返回位置 elseif(data>Data[mid]) low=mid+1; else high=mid-1; } return0;//查找失敗返回0}九、程序運(yùn)行結(jié)果：十、實(shí)驗(yàn)結(jié)論：通過實(shí)現(xiàn)快速排序和折半查找算法，根本到達(dá)了實(shí)驗(yàn)?zāi)康?。快速排序的根本思想是每次確定一個劃分元，將比劃分元大的數(shù)據(jù)存儲到劃分元右邊，比他小的存儲到他左邊，通過遞歸排序?qū)崿F(xiàn)整個順序表的排序。然而，其中的遞歸調(diào)用很難，需要思考其中參數(shù)的變化，這需要細(xì)心。十一、總結(jié)及心得體會：1