快速排序與二分查找

1、快速排序與二分查找實(shí)驗(yàn)四課程名稱： 學(xué)生姓名： 學(xué) 號(hào): 點(diǎn)名序號(hào)： 指導(dǎo)教師： 實(shí)驗(yàn)地點(diǎn)： 實(shí)驗(yàn)時(shí)間：電子科技大學(xué)實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)與算法陳*浩*錢*基礎(chǔ)實(shí)驗(yàn)大樓A5082015632014-2015-2 學(xué)期信息與軟件工程學(xué)院實(shí) 驗(yàn) 報(bào) 告（四）學(xué)生姓名：陳*浩 學(xué)號(hào)：*導(dǎo)教師：錢*實(shí)驗(yàn)地點(diǎn)：基礎(chǔ)實(shí)驗(yàn)大樓 A508實(shí)驗(yàn)時(shí)間：201563一、實(shí)驗(yàn)室名稱：軟件實(shí)驗(yàn)室二、實(shí)驗(yàn)項(xiàng)目名稱：數(shù)據(jù)結(jié)構(gòu)與算法一快速排序與二分查找三、實(shí)驗(yàn)學(xué)時(shí)：4四、實(shí)驗(yàn)原理：快速排序的基本思想是：通過一躺排序?qū)⒁?排序的數(shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的 所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小， 然后再按次方法對(duì)這兩部分

2、數(shù)據(jù)分別進(jìn)行快速 排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整 個(gè)數(shù)據(jù)變成有序序列。假設(shè)要排序的數(shù)組是A1AN,首先 任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為 關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面， 所有比它大的數(shù)都放到它后面，這個(gè)過程稱為一 躺快速排序。一躺快速排序的算法是：1）設(shè)置兩個(gè)變量I、J，排序開始的時(shí)候I : =1，J : =N2） 以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給 X，即 X: =A1；3）從J開始向前搜索，即（J : =J-1），找到 第一個(gè)小于X的值，兩者交換；4）從I開始向后搜索，即（I: =1+1），找到 第一個(gè)大于X的值，兩者交換；5）重復(fù)第3、4步，直到I=J

3、。二分法查找（折半查找）的基本思想：（1） 確定該區(qū)間的中點(diǎn)位置：mid=（low+high ） /2min代表區(qū)間中間的結(jié)點(diǎn)的位置，low代表區(qū)間 最左結(jié)點(diǎn)位置，high代表區(qū)間最右結(jié)點(diǎn)位置（2）將待查a值與結(jié)點(diǎn)mid的關(guān)鍵字（下面 用Rmid.key ）比較，若相等，則查找成功，否 則確定新的查找區(qū)間：A）如果Rmid.keya，則由表的有序性可 知，Rmid.key右側(cè)的值都大于a，所以等于a 的關(guān)鍵字如果存在，必然在 Rmid.key左邊的 表中，這時(shí)high=mid-1;B）如果Rmid.keya,則等于a的關(guān)鍵字如 果存在，必然在 Rmid.key右邊的表中。這時(shí) low=mid

4、；C）如果Rmid.key=a，則查找成功。（3） 下一次查找針對(duì)新的查找區(qū)間，重復(fù)步 驟（1）和（2）（4）在查找過程中，low逐步增加，high逐 步減少，如果highlow，則查找失敗。五、實(shí)驗(yàn)?zāi)康模罕緦?shí)驗(yàn)通過實(shí)現(xiàn)快速排序和折半查找算法，使學(xué)生理解如何實(shí)現(xiàn)快速查找和排序的基本算法思想。通過練習(xí)，加強(qiáng)對(duì)算法的理解，提高編程能力。六、實(shí)驗(yàn)內(nèi)容：（1）實(shí)現(xiàn)數(shù)據(jù)序列的輸入；（2）實(shí)現(xiàn)快速排序算法，并對(duì)輸入的序列排序后輸出；（3）實(shí)現(xiàn)折半查找算法，并在步驟（2）排序后的序列上，進(jìn)行任意地 查找，并輸出查詢結(jié)果。七、實(shí)驗(yàn)器材（設(shè)備、元器件）：PC機(jī)一臺(tái)，裝有C/C+語言集成開發(fā)環(huán)境。八、數(shù)據(jù)結(jié)構(gòu)及程

5、序/*快速查找與二分排序* 陳 家 浩*2015.6.6*#include#define MAX 100int DataMAX+1 = 0;intQuick_Part(intData,inti,int j);/一趟排序intQuick_Sort(intData,ints,int t);/遞歸排序intQuick_Find(intData,intdata,intn);/二分查找int main(void)Iint choose = -1 int i,k,data; / 選擇功能int n; /數(shù)據(jù)序列長(zhǎng)度while(1)printf(+ 排序與查找 -+n|1:輸入數(shù)據(jù)序列|n|2:序列排序|n

6、|3:查找信息|n|0:退出|n+n 請(qǐng)選擇： ); scanf(%d,&choose);switch(choose)case 1:printf( 請(qǐng)輸入序列數(shù)據(jù)個(gè)數(shù)： );scanf(%d,&n);if(nMAX)printf( 數(shù)據(jù)過多 !nn); break;elseprintf( 請(qǐng)輸入數(shù)據(jù)序列： n);for(i = 1;i = n;i+) scanf(%d,&Datai);printf( 讀取成功！ nn);break;case 2:Quick_Sort(Data,1,n);/ 快速排序printf( 排序成功！序列如下： n); for(i = 1;i = n;i+)printf

7、(%d ,Datai); printf(nn); break;case 3: printf( 請(qǐng)輸入待查找的數(shù)據(jù)： ); scanf(%d,&data);k = Quick_Find(Data,data,n);/ 二分法查找if(k)printf( 查找成功！數(shù)據(jù) %d 位于序 列第 %d 位。 nn,data,k);elseprintf( 查找失?。]有你要查找的數(shù) 據(jù)！ nn);break; default:return 0;int Quick_Part(int Data,int i,int j)/ 快速排序Data0 = Datai;while(i j)while(i j) & (Dat

8、a0 = Dataj)j -;/ 右邊目標(biāo)元比劃分元大， j 往左移if(i j)Datai = Dataj; /比劃分元小的關(guān)鍵 字交換到左邊i +; while(i = Datai)i +;/ 左邊目標(biāo)元比劃分元小， i 往右移if(i s)Quick_Sort(Data,s,i-1);/遞歸調(diào)用排序if(it)Quick_Sort(Data,i+1,t);/ 遞歸調(diào)用排序return 0;/二分查int Quick_Find(int Data,int data,int n) 找int low = 1; int high = n;int mid;/中間位置/查找成功返回while(low Datamid) low = mid +1;elsehigh = mid -1;II查找失敗return 0;返回0九、程序運(yùn)行結(jié)果:十、實(shí)驗(yàn)結(jié)論：通過實(shí)現(xiàn)快速排序和折半查找算法， 基本達(dá)到了實(shí)驗(yàn)?zāi)康摹？焖倥判虻幕?思想是每次確定一個(gè)劃分元，將比劃分元大的數(shù)據(jù)存儲(chǔ)到劃分元右邊，比他小 的存儲(chǔ)到他左邊，通過遞歸排序?qū)崿F(xiàn)整個(gè)順序表的排序。然而，其中的遞歸調(diào) 用很難，需要思考其中參數(shù)的變化，這需要細(xì)心。十一、總結(jié)及心得體會(huì)：1對(duì)錯(cuò)誤輸入的解決方案還有待完善；2快速排序遞歸調(diào)用結(jié)束的條件需要慎重考慮，否則極易陷入死循環(huán)。例 如課本上的while(svt)結(jié)束條件