快速排序與二分查找

本文格式為Word版，下載可任意編輯——快速排序與二分查找電子科技大學(xué)信息與軟件工程學(xué)院試驗(yàn)報(bào)告

電子科技大學(xué)

實(shí)驗(yàn)報(bào)告

課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)與算法

學(xué)生姓名：陳*浩學(xué)號(hào)：*************點(diǎn)名序號(hào)：***指導(dǎo)教師：錢(qián)**試驗(yàn)地點(diǎn)：基礎(chǔ)試驗(yàn)大樓A508試驗(yàn)時(shí)間：2023.6.3

2023-2023-2學(xué)期信息與軟件工程學(xué)院

第1頁(yè)

電子科技大學(xué)信息與軟件工程學(xué)院試驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告(四)

學(xué)生姓名：陳*浩學(xué)號(hào)：*************導(dǎo)教師：錢(qián)**試驗(yàn)地點(diǎn)：基礎(chǔ)試驗(yàn)大樓A508試驗(yàn)時(shí)間：2023.6.3一、試驗(yàn)室名稱(chēng)：軟件試驗(yàn)室

二、試驗(yàn)項(xiàng)目名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)與算法—快速排序與二分查找三、試驗(yàn)學(xué)時(shí)：4四、試驗(yàn)原理：

快速排序的基本思想是：通過(guò)一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

假設(shè)要排序的數(shù)組是A[1]……A[N]，首先任意選取一個(gè)數(shù)據(jù)（尋常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱(chēng)為一躺快速排序。一躺快速排序的算法是：

1）設(shè)置兩個(gè)變量I、J，排序開(kāi)始的時(shí)候I：=1，J：=N

2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A[1]；3）從J開(kāi)始向前探尋，即（J：=J-1），找到第一個(gè)小于X的值，兩者交換；4）從I開(kāi)始向后探尋，即（I：=I+1），找到第一個(gè)大于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）比較，若相等，則查找成功，否則確定新的查找區(qū)間：

A)假使R[mid].key>a，則由表的有序性可知，R[mid].key右側(cè)的值都大于a，所以等于a的關(guān)鍵字假使存在，必然在R[mid].key左邊的表中,這時(shí)high=mid-1;

B)假使R[mid].keyC)假使R[mid].key=a，則查找成功。

（3）下一次查找針對(duì)新的查找區(qū)間，重復(fù)步驟（1）和（2）

（4）在查找過(guò)程中，low逐步增加，high逐步減少，假使high#defineMAX100

intData[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ù)序列長(zhǎng)度while(1){printf(\排序與查找+\\n\\1:輸入數(shù)據(jù)序列|\\n\\2:序列排序|\\n\\3:查找信息|\\n\\0:退出|\\n\\\請(qǐng)選擇：\

第3頁(yè)

PC機(jī)一臺(tái)，裝有C/C++語(yǔ)言集成開(kāi)發(fā)環(huán)境。

電子科技大學(xué)信息與軟件工程學(xué)院試驗(yàn)報(bào)告

scanf(\switch(choose){case1:printf(\請(qǐng)輸入序列數(shù)據(jù)個(gè)數(shù)：\scanf(\if(n>MAX){printf(\數(shù)據(jù)過(guò)多!\\n\\n\break;}else{printf(\請(qǐng)輸入數(shù)據(jù)序列：\\n\for(i=1;is)Quic