數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)-各種排序算法時(shí)間性能的比較

《數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)-各種排序算法時(shí)間性能的比較》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、學(xué)號(hào)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)說明書題目各種排序算法時(shí)間性能的比較起止日期：2011年12月12日至2011年12月16日學(xué)生姓名班級成績指導(dǎo)教師(簽字)電子與信息工程系2011年12月16日211天津城市建設(shè)學(xué)院課程設(shè)計(jì)任務(wù)書2011—2012學(xué)年第1學(xué)期電子與信息工程系軟件工程專業(yè)班級課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目：各種排序算法時(shí)間性能的比較完成期限：自2011年12月12日至2011年12月16日共1周設(shè)計(jì)依據(jù)、要求及主要內(nèi)容（可另加附頁）：一、設(shè)計(jì)目的熟悉各種數(shù)據(jù)結(jié)構(gòu)和運(yùn)算，會(huì)使用數(shù)據(jù)結(jié)構(gòu)的基本操作解決一些實(shí)際問題。二、設(shè)計(jì)要求（1）重視課程設(shè)計(jì)環(huán)節(jié)，用嚴(yán)

2、謹(jǐn)、科學(xué)和踏實(shí)的工作態(tài)度對待課程設(shè)計(jì)的每一項(xiàng)任務(wù)；（2）按照課程設(shè)計(jì)的題目要求，獨(dú)立地完成各項(xiàng)任務(wù)，嚴(yán)禁抄襲；凡發(fā)現(xiàn)抄襲，抄襲者與被抄襲者皆以零分計(jì)入本課程設(shè)計(jì)成績。凡發(fā)現(xiàn)實(shí)驗(yàn)報(bào)告或源程序雷同，涉及的全部人員皆以零分計(jì)入本課程設(shè)計(jì)成績；（3）學(xué)生在接受設(shè)計(jì)任務(wù)后，首先要按設(shè)計(jì)任務(wù)書的要求編寫設(shè)計(jì)進(jìn)程表；（4）認(rèn)真編寫課程設(shè)計(jì)報(bào)告。三、設(shè)計(jì)內(nèi)容對各種排序方法（直接插入排序、希爾排序、起泡排序、快速排序、直接選擇排序、堆排序和歸并排序）的時(shí)間性能進(jìn)行比較。(1)設(shè)計(jì)并實(shí)現(xiàn)上述各種排序算法；(2)產(chǎn)生正序和逆序的初始排列分別調(diào)用上述排序算法，并比較時(shí)間性能；(3)產(chǎn)生隨機(jī)

3、的初始排列分別調(diào)用上述排序算法，并比較時(shí)間性能。211四、參考文獻(xiàn)1．王紅梅．?dāng)?shù)據(jù)結(jié)構(gòu)．清華大學(xué)出版社2．王紅梅．?dāng)?shù)據(jù)結(jié)構(gòu)學(xué)習(xí)輔導(dǎo)與實(shí)驗(yàn)指導(dǎo)．清華大學(xué)出版社3．嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語言版）．清華大學(xué)出版社211一、需求分析需要對用戶輸入的一組數(shù)據(jù)進(jìn)行排序，并對7種排序的正逆排序進(jìn)行分析，并做出時(shí)間復(fù)雜度的比較，并得出最優(yōu)的排序方法作為結(jié)果。二、問題求解在排序時(shí)，開始做出的任何一個(gè)排序的的逆排序的時(shí)間復(fù)雜度都是一個(gè)定值不會(huì)變，后來經(jīng)過單步調(diào)試，發(fā)現(xiàn)是把正排序放在了起之前，所以逆排序排出來的都是已經(jīng)排好的數(shù)據(jù)，所以不會(huì)變，我通過復(fù)制數(shù)組，做成了兩個(gè)數(shù)組（最后做成

4、的總程序?yàn)槎鄠€(gè)數(shù)組），然后分別對應(yīng)每個(gè)算法做排序。這樣就不會(huì)在顯示后一個(gè)算法的排序是前一個(gè)算法已經(jīng)排序好的數(shù)組，而是用戶輸入的原始數(shù)組。一下是對于每個(gè)排序的分析及所遇見的問題：（排序解釋都用正排序說明）1．冒泡排序該排序沒有什么打的問題，用兩個(gè)for循環(huán)即可做出排序。排序原理是兩兩對比大的放前，小的放后。2．插入排序該排序是以第n個(gè)數(shù)（需排序的數(shù)）直接去與數(shù)組里已經(jīng)排序好的數(shù)做比較。將其插入比它大的數(shù)之前，比它小的數(shù)之后。在做該數(shù)組的時(shí)候我之前以為r[0]的哨兵可以用任意一的變量來代替，從而是數(shù)組從r[0]開始計(jì)數(shù)，結(jié)果表明，并不是這樣，因?yàn)槊恳淮?，最小的?shù)都會(huì)唄覆

5、蓋掉，所以原假設(shè)不成立。3．希爾排序：先把數(shù)組分成等長的兩個(gè)數(shù)組，用r[i]與r[n/2+i]做比較曉得在前，打的在后，然后在一剛剛兩兩一組的兩組做比較，就這樣，每次比較，每組數(shù)的個(gè)數(shù)都是上一次的兩倍，最后完成整個(gè)數(shù)組的排序。4．直接選擇排序該排序是現(xiàn)在無序的數(shù)組中找最值，然后作為第一個(gè)元素，之后就是每次找最值，作為下一個(gè)元素，直至最后一個(gè)元素，排序完成。5．快速排序定義兩個(gè)指針，分別只想第一個(gè)與最后一個(gè)元素，這兩個(gè)元素做比較，大的放前，小的放后，然后移動(dòng)指針，進(jìn)行下一個(gè)比較。兩次這樣比較排序以后，數(shù)組變成為了有序數(shù)列。該算法采用為遞歸算法。6．歸并排序該排序，也是

6、需要調(diào)用遞歸。先把數(shù)組對半分多次，直到每組只有兩個(gè)數(shù)據(jù)時(shí)，進(jìn)行對比、排序。然后再兩兩合并，最后做到整個(gè)數(shù)組的排序完成7．堆排序先是對堆做比較，左子數(shù)小于本數(shù)，右子數(shù)大于本數(shù)，然后不停比較，交換，最后達(dá)到整個(gè)數(shù)組的排序。211三、總體設(shè)計(jì)每一個(gè)排序都給出排序后的數(shù)組及本排序的時(shí)間復(fù)雜度。主程序快速排序冒泡排序插入排序希爾排序直接選擇排序歸并排序堆排序主程序快速排序冒泡排序插入排序希爾排序直接選擇排序歸并排序堆排序雜亂數(shù)組輸出整理排序數(shù)組，并作出分析，得到最有方法四、詳細(xì)設(shè)計(jì)//冒泡排序211voidZmppx(inta[],intn)//正序排序voidNmppx(i

7、nta[],intn)//逆序排序//插入排序voidZcrpx(intr[],intn)//正序排序voidNcrpx(intr[],intn)//逆序排序//希爾排序voidZxepx(intr[],intn)//正序排序voidNxepx(intr[],intn)//逆序排序//直接選擇排序voidZzjxzpx(intr[],intn)//正序排序voidNzjxzpx(intr[],intn)//逆序排序//快速排序voidZkspx(intr[],intleft,intright)//正序排序voidNkspx(intr[],intleft,intr