快速排序與二分查找

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

2、數(shù)據(jù)分別進(jìn)行快速 排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整 個數(shù)據(jù)變成有序序列。假設(shè)要排序的數(shù)組是A1AN,首先 任意選取一個數(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: =A1；3）從J開始向前搜索，即（J : =J-1），找到 第一個小于X的值，兩者交換；4）從I開始向后搜索，即（I: =1+1），找到 第一個大于X的值，兩者交換；5）重復(fù)第3、4步，直到I=J

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

4、；C）如果Rmid.key=a，則查找成功。（3） 下一次查找針對新的查找區(qū)間，重復(fù)步 驟（1）和（2）（4）在查找過程中，low逐步增加，high逐 步減少，如果highlow，則查找失敗。五、實驗?zāi)康模罕緦嶒炌ㄟ^實現(xiàn)快速排序和折半查找算法，使學(xué)生理解如何實現(xiàn)快速查找和排序的基本算法思想。通過練習(xí)，加強對算法的理解，提高編程能力。六、實驗內(nèi)容：（1）實現(xiàn)數(shù)據(jù)序列的輸入；（2）實現(xiàn)快速排序算法，并對輸入的序列排序后輸出；（3）實現(xiàn)折半查找算法，并在步驟（2）排序后的序列上，進(jìn)行任意地 查找，并輸出查詢結(jié)果。七、實驗器材（設(shè)備、元器件）：PC機一臺，裝有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ù)序列長度while(1)printf(+ 排序與查找 -+n|1:輸入數(shù)據(jù)序列|n|2:序列排序|n

6、|3:查找信息|n|0:退出|n+n 請選擇： ); scanf(%d,&choose);switch(choose)case 1:printf( 請輸入序列數(shù)據(jù)個數(shù)： );scanf(%d,&n);if(nMAX)printf( 數(shù)據(jù)過多 !nn); break;elseprintf( 請輸入數(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( 請輸入待查找的數(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九、程序運行結(jié)果:十、實驗結(jié)論：通過實現(xiàn)快速排序和折半查找算法， 基本達(dá)到了實驗?zāi)康??？焖倥判虻幕?思想是每次確定一個劃分元，將比劃分元大的數(shù)據(jù)存儲到劃分元右邊，比他小 的存儲到他左邊，通過遞歸排序?qū)崿F(xiàn)整個順序表的排序。然而，其中的遞歸調(diào) 用很難，需要思考其中參數(shù)的變化，這需要細(xì)心。十一、總結(jié)及心得體會：1對錯誤輸入的解決方案還有待完善；2快速排序遞歸調(diào)用結(jié)束的條件需要慎重考慮，否則極易陷入死循環(huán)。例 如課本上的while(svt)結(jié)束條件