數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)快速排序

1、學(xué)號 武漢理工大學(xué)華夏學(xué)院 課 程 設(shè) 計(jì) 課程名稱 數(shù)據(jù)結(jié)構(gòu) 題 目:用c語言實(shí)現(xiàn)成績表的快速排序程序設(shè)計(jì) 專 業(yè) 軟件工程 班 級 姓 名 成 績 指導(dǎo)教師 2009 年6月28日至2009年7月3 日 課程設(shè)計(jì)任務(wù)書設(shè)計(jì)題目：用c語言實(shí)現(xiàn)成績表的快速排序程序設(shè)計(jì)設(shè)計(jì)目的1.鞏固和加深課堂所學(xué)知識、學(xué)會分析研究數(shù)據(jù)對象的特性及數(shù)據(jù)的組織方法；2.選擇合適的數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)以及相應(yīng)操作，實(shí)現(xiàn)一個(gè)班的成績統(tǒng)計(jì)3. 提高程序設(shè)計(jì)能力、加強(qiáng)查閱、運(yùn)用資料的能力、算法分析與程序設(shè)計(jì)素質(zhì)培養(yǎng) ；設(shè)計(jì)任務(wù) （在規(guī)定的時(shí)間內(nèi)完成下列任務(wù)）問題描述給出n個(gè)學(xué)生的1門課程的考試成績信息，每條信息由姓名

2、 與分?jǐn)?shù)組成，要求設(shè)計(jì)快速排序算法，進(jìn)行：（1）按成績排序；（2）輸出形式為：張強(qiáng) 張平 曾芽 王華 孫軍 李應(yīng) 程濱 90 88 82 78 70 69 65基本要求 學(xué)生的考試成績必須通過鍵盤輸入，且需對輸出進(jìn)行格式控制；算法提示利用快速排序算法求解； 具體要完成的任務(wù)是： a. 編制完成上述問題的c語言程序、進(jìn)行程序調(diào)試并能得出正確的運(yùn)行結(jié)果。 b. 寫出規(guī)范的課程設(shè)計(jì)報(bào)告書；時(shí)間安排 6月 29日 布置課程設(shè)計(jì)任務(wù)，查閱相關(guān)資料，確定設(shè)計(jì)課題；6月 30日 查閱資料、 準(zhǔn)備程序； 6月307月2日 上機(jī)調(diào)試程序、教師驗(yàn)收程序、書寫課程設(shè)計(jì)報(bào)告； 7月3 日 下午4點(diǎn)前提交課程設(shè)計(jì)報(bào)告及

3、相關(guān)文檔。具體要求1. 課程設(shè)計(jì)報(bào)告按統(tǒng)一通用格式書寫，具體內(nèi)容如下： 設(shè)計(jì)任務(wù)與要求 總體方案與說明 軟件主要模塊的流程圖 源程序清單與注釋 問題分析與解決方案（包括調(diào)式報(bào)告，即在調(diào)式過程中遇到的主要問題、解決方法及改進(jìn)設(shè)想）； 小結(jié)與體會附錄： 源程序（必須有簡單注釋） 使用說明 參考資料2每位學(xué)生應(yīng)獨(dú)立完成各自的任務(wù)且每天至少在設(shè)計(jì)室工作半天；指 導(dǎo) 教 師 簽 名： 09 年 6月 27日教研室主任（或責(zé)任教師）簽名： 09 年 6月 28日 成績表的快速排序程序設(shè)計(jì)一、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康?. 掌握用turbo c 上機(jī)調(diào)試常規(guī)算法的程序；2. 掌握快速排序的基本方法和過程；基本原理與方

4、法：利用快速排序算法原理用c語言編程實(shí)現(xiàn)實(shí)驗(yàn)設(shè)備：pc機(jī)一臺、配置turbo c軟件二、實(shí)驗(yàn)內(nèi)容問題描述 對于用戶輸入的數(shù)據(jù)序列，用快速排序法按從大到小或從小到大兩種順序進(jìn)行排序，并顯示每一趟的排序過程；基本要求 采用遞歸算法和非遞歸算法兩種算法；算法實(shí)現(xiàn) 采用快速排序原理編寫c程序；基本思想 通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩個(gè)區(qū)間，其中左區(qū)間記錄的關(guān)鍵字的值均比右區(qū)間中記錄的關(guān)鍵字的值小，再分別對這兩個(gè)區(qū)間中的記錄進(jìn)行快速排序，以達(dá)到整個(gè)序列有序?yàn)橹埂？焖倥判蛐再|(zhì) 1) 內(nèi)部排序 快速排序是一種內(nèi)部排序方法。也就是說快速排序的排序?qū)ο笫亲x入內(nèi)存的數(shù)據(jù)。2) 比較排序 快速排序確定元素位

5、置的方法基于元素之間關(guān)鍵字大小的比較。 所有基于比較方法的排序方法的時(shí)間下界不會低于o(nlgn)。這個(gè)結(jié)論的具體證明，請參考有關(guān)算法的書籍，例如算法導(dǎo)論（第一版）第8章（第二版在第七章quicksort)。3) 在理想情況下，能嚴(yán)格地達(dá)到o(nlgn)的下界。一般情況下，快速排序 隨機(jī)化快速排序的平均情況性能都達(dá)到了o(nlgn)。4) 不穩(wěn)定性 快速排序是一種不穩(wěn)定的排序方法。簡單地說，元素a1, a2的關(guān)鍵字有a1.key=a2.key，則不穩(wěn)定的排序方法不能保證a1, a2在排序后維持原來的位置先后關(guān)系。5) 原地排序在排序的具體操作過程中，除去程序運(yùn)行實(shí)現(xiàn)的空間消費(fèi)（例如遞歸棧），快

6、速排序算法只需消耗確定數(shù)量的空間（即s(1)，常數(shù)級空間）。 這個(gè)性質(zhì)的意義，在于在內(nèi)存空間受到限制的系統(tǒng)（例如mcu）中，快速排序也能夠很好地工作。排序過程 在待排序的n各記錄中任取一條記錄（通常去第一條記錄），把它作為基準(zhǔn)元素，確定該條記錄的最終位置，即該條記錄左邊的記錄的所有記錄的關(guān)鍵字的值均小于該記錄，右邊的所有記錄的關(guān)鍵字的值均大于等于該記錄。待排序序列以基準(zhǔn)元素為界限被分割成兩個(gè)區(qū)域，這個(gè)過程稱作一次快速排序。之后對所有的區(qū)間分別重復(fù)上述過程，直至每個(gè)區(qū)間只有一條 記錄為止?？焖倥判蚴且粋€(gè)遞歸過程，整個(gè)排序過程中對不同的區(qū)間進(jìn)行 快速排序。 假設(shè)要排序的數(shù)組是a1an，首先任意選取

7、一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過程稱為一躺快速排序。一躺快速排序的算法是： 1）、設(shè)置兩個(gè)變量i、j，排序開始的時(shí)候i：=1，j：=n； 2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給x，即x：=a1； 3）、從j開始向前搜索，即由后開始向前搜索（j：=j-1），找到第一個(gè)小于x的值，兩者交換； 4）、從i開始向后搜索，即由前開始向后搜索（i：=i+1），找到第一個(gè)大于x的值，兩者交換； 5）、重復(fù)第3、4步，直到i=j； 事例模范 例：將數(shù)據(jù)45 53 18 36 72 30 48 93 15 36進(jìn)行快速排序。 圖1

8、快速排序的一次劃分程 45 53 18 36 72 30 48 93 15 36 移動比較i j 36 53 18 36 72 30 48 93 15 45 交換位置并比較 i j 36 45 18 36 72 30 48 93 15 53 交換位置并比較 i j 36 15 18 36 72 30 48 93 45 53 交換位置并比較 i j 36 15 18 36 45 30 48 93 72 53 交換位置并比較 i j 36 15 18 36 30 45 48 93 72 53 交換位置，i=j i j 36 15 18 36 30 45 48 93 72 53 一趟排序的結(jié)果 圖2

9、一次完整的快速排序的排序過程（待排序區(qū)間以中括號括起來） 45 53 18 36 72 30 48 93 15 36 30 36 18 36 15 45 48 93 72 53 18 15 30 36 36 45 48 93 72 53 15 18 30 36 36 45 48 93 72 53 15 18 30 36 36 45 48 93 72 53 15 18 30 36 36 45 48 93 72 53 15 18 30 36 36 45 48 53 72 93 15 18 30 36 36 45 48 53 72 93 參考程序#include <stdio.h> #i

10、nclude <stdlib.h> #define size 35void quick_sort(int data, int x, int y);int pation(int data, int x, int y);int main( ) int i, datasize; for(i=0; i<size; +i) scanf("%d", &datai); quick_sort(data, 0, size-1); for(i=0; i<size; +i) printf("%d ",datai); system("p

11、ause"); void quick_sort(int data,int x,int y) int q; if(x>=y) return; q=pation(data,x,y); quick_sort(data,x,q-1); quick_sort(data,q+1,y); int pation(int data,int x,int y) int n=datax,i=x+1,j=y,temp; while(1) while(datai<n) +i; while(dataj>n) -j; if(i>=j) break; temp=datai;datai=data

12、j;dataj=temp; datax=dataj; dataj=n; return j; 算法實(shí)現(xiàn)流程圖 快速排序算法流程圖w=a1 i<j i=1;j=nw<ajai=wai=aji=i+1w>aii=i+1aj=ai j=j-1j=j-1+輸入數(shù)據(jù)+end 調(diào)試過程 1. 首先打開桌面上的軟件。2. 將事先寫好的程序逐條輸入正文中，注意英文與中文符號間的區(qū)別。3. 用鼠標(biāo)單擊工具欄中的“編譯連接”按鈕。4. 若顯示的消息框?yàn)椤肮?，編譯成功”，則程序輸入正確。若顯示“編譯失敗，您需要檢查錯(cuò)誤”，則根據(jù)窗口下邊提示的錯(cuò)誤依次改正，直至編譯成功為止。 5. 當(dāng)?shù)谒牟酵瓿珊螅?/p>

13、單擊工具攔上的“編譯連接并運(yùn)行”按鈕，先出現(xiàn)第四步中的“恭喜，編譯成功”，然后顯示程序輸入框（如圖3）。 圖3程序數(shù)據(jù)輸入框 6在第四步的窗口中隨意輸入一組數(shù)據(jù)，查看結(jié)果。如圖4 圖4三、實(shí)驗(yàn)結(jié)果與分析。例1：若輸入的數(shù)據(jù)序列為：56 75 65 78 45 88 76 59 66 60 85 71 44 90 68 75 62 54 84 65 35 91 47 65 73 49 85 64 92 49 67程序執(zhí)行結(jié)果是：35 44 45 47 49 49 54 57 59 60 62 64 65 65 65 66 67 68 71 73 75 75 76 78 84 85 85 88 9

14、0 91 92 結(jié)果分析：由事例容易得出快速排序的的平均實(shí)際復(fù)雜度為o（n）。但是，在待排序的記錄已經(jīng)有的情況下，排序工作反而最長?？焖倥判蜻f歸算法需要堆棧來實(shí)現(xiàn)，棧中存放待排序記錄序列的首尾位置，一般情況下需要?？臻go（）：在最壞的情況下，需要的?？臻g為o（n）?？焖倥判蚴遣环€(wěn)定的?？焖倥判虿皇褂糜谟涗浕居行虻膱龊稀?例2：輸入學(xué)生成績并排序： 張強(qiáng) 張平 曾芽 王華 孫軍 李應(yīng) 程濱 90 88 82 78 70 69 65 結(jié)果如圖5 圖5四、課程設(shè)計(jì)體會 課程設(shè)計(jì)是對我們平時(shí)學(xué)習(xí)的一種考察，我們要正確地對待。不斷地鍛煉自己動手動腦的能力、把知識賦予實(shí)踐就是我們學(xué)習(xí)的目標(biāo)！ 既然學(xué)校給

15、我們這么好的機(jī)會，讓我們自己在實(shí)驗(yàn)室作操作，我們應(yīng)該好好抓住機(jī)會，把我們平時(shí)學(xué)習(xí)的東西用自己的作品展現(xiàn)出來。這次，我做的是學(xué)生成績：快速排序的設(shè)計(jì)，這給了我充分鍛煉的機(jī)會。我會用自己學(xué)到的東西的設(shè)計(jì)出一副好的作品。 通過四天的制作，我以基本完成了自己的作品。從中我明白：要學(xué)好數(shù)據(jù)結(jié)構(gòu)，首先要有一顆堅(jiān)毅的心，有恒心，有信心，在學(xué)習(xí)過程中，坎坷是避免不了的，但千萬不要灰心，不要?dú)怵H，要繼續(xù)努力，剛開始是會感到很無助的，也許會產(chǎn)生放棄的念頭，千萬頂住，只要克服了開始的難關(guān)，以后的路才會充滿陽光，充滿快樂。 而且，在程序算法設(shè)計(jì)過程中我也遇到了很多問題。但是在老師和同學(xué)的幫助下，我一次次將難題解決。對此，我由衷地感謝那些在我制作表格過程中幫助過我的人。 我相信通過我以后很加刻苦的學(xué)習(xí)，我會更加熱愛我的專業(yè)課程。五、問題答辯設(shè)計(jì)過程中質(zhì)疑（或答辯）記載： 問題一：如何將學(xué)生成績的排序數(shù)進(jìn)行增加或減少