常用排序算法課程設(shè)計(jì)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上重慶科技學(xué)院課程設(shè)計(jì)任務(wù)書(shū)設(shè)計(jì)題目：常用排序算法的比較學(xué)生姓名*課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)專(zhuān)業(yè)班級(jí) *地 點(diǎn)計(jì)算機(jī)基礎(chǔ)自主學(xué)習(xí)中心起止時(shí)間 2011.11.16-12.5設(shè)計(jì)內(nèi)容及要求利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)，采用多種方法對(duì)這些數(shù)進(jìn)行排序，然后分析各自的所需的排序時(shí)間找出較快的排序算法。要求：1) 分別采用的排序算法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序，實(shí)現(xiàn)這批數(shù)據(jù)的排序，并把排序后的結(jié)果保存在不同的文件中。2) 統(tǒng)計(jì)每一種排序算法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的算法。注：在完成以上數(shù)據(jù)的同時(shí)，還能

2、采用其它的排序算法，適當(dāng)加分。設(shè)計(jì)參數(shù) 測(cè)試數(shù)據(jù)要求：隨機(jī)產(chǎn)生1000 個(gè)以上的隨機(jī)整數(shù)，并保存在文本文件中。排序后的數(shù)據(jù)和所需的時(shí)間也保存在各自的txt文件中。進(jìn)度要求 參考資料1嚴(yán)蔚敏 吳偉民 著， 數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，2007.32李春葆 著，數(shù)據(jù)結(jié)構(gòu)教程，清華大學(xué)出版社，2005.13. Richard F.Gilberg Behrouz A.Forouzan, 數(shù)據(jù)結(jié)構(gòu)的C+偽碼實(shí)現(xiàn)（英文版），人民郵電出版社，2002.1其它說(shuō)明.本表應(yīng)在每次實(shí)施前一周由負(fù)責(zé)教師填寫(xiě)二份，院系審批后交院系辦備案，一份由負(fù)責(zé)教師留用。.若填寫(xiě)內(nèi)容較多可另紙附后。3.一題多名學(xué)生共用的，在設(shè)計(jì)內(nèi)容

3、、參數(shù)、要求等方面應(yīng)有所區(qū)別。教研室主任： 指導(dǎo)教師： 2011年 11月 16日專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)摘要排序算法是數(shù)據(jù)結(jié)構(gòu)學(xué)科經(jīng)典的內(nèi)容，其中內(nèi)部排序現(xiàn)有的算法有很多種，其中包含冒泡排序，直接插入排序，簡(jiǎn)單選擇排序，希爾排序，快速排序，堆排序等，各有其特點(diǎn)。對(duì)排序算法比較的分析可以遵循若干種不同的準(zhǔn)則，通常以排序過(guò)程所需要的算法步數(shù)作為度量，有時(shí)也以排序過(guò)程中所作的鍵比較次數(shù)作為度量。特別是當(dāng)作一次鍵比較需要較長(zhǎng)時(shí)間，例如，當(dāng)鍵是較長(zhǎng)的字符串時(shí)，常以鍵比較次數(shù)作為排序算法計(jì)算時(shí)間復(fù)雜性的度量。當(dāng)排序時(shí)需要移動(dòng)記錄，且記錄都很大時(shí)，還應(yīng)該考慮記錄的移動(dòng)次數(shù)。究竟采用哪種度量方法比較合適要根據(jù)具體情

4、況而定。本報(bào)告將描述如何利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)，采用多種方法對(duì)這些數(shù)進(jìn)行排序，然后分析各自的所需的排序時(shí)間找出較快的排序算法。關(guān)鍵詞：排序算法 數(shù)據(jù)結(jié)構(gòu) 隨機(jī)函數(shù) 目錄1 設(shè)計(jì)內(nèi)容和要求1.1 設(shè)計(jì)內(nèi)容利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)，采用多種方法對(duì)這些數(shù)進(jìn)行排序，然后分析各自的所需的排序時(shí)間找出較快的排序算法。1.2 設(shè)計(jì)要求1) 分別采用的排序算法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序，實(shí)現(xiàn)這批數(shù)據(jù)的排序，并把排序后的結(jié)果保存在不同的文件中。 2) 統(tǒng)計(jì)每一種排序算法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的算法。2 需求分析2.1

5、 直接插入排序思路:設(shè)有一組關(guān)鍵字K1,K2,.,Kn,排序開(kāi)始變認(rèn)為K1是一個(gè)有序的序列,讓K2插入到表長(zhǎng)為1的有序序列,使之成為一個(gè)表長(zhǎng)為2的有序序列, 讓K3插入到表長(zhǎng)為2的有序序列,使之成為一個(gè)表長(zhǎng)為3的有序序列,依次類(lèi)推,最后讓Kn插入上述表長(zhǎng)為n-1的有序序列,得到一個(gè)表長(zhǎng)為n的有序序列.2.2 希爾排序思路：先取一個(gè)正整數(shù)d1(d1<n),把全部記錄分成d1個(gè)組,所有距離為d1的倍數(shù)的記錄看成是一組,然后在各組內(nèi)進(jìn)行插入排序;然后取d2(d2<d1),重復(fù)上述分組和排序操作,直到取di=1(>=1),即所有記錄成為一個(gè)組為此.一般選d1約為n/2,d2為d1/2

6、,.,di=12.3 快速排序:（遞歸和非遞歸）思路:以第一個(gè)關(guān)鍵字K1為控制字，將K1、K2、.Kn分成兩個(gè)子區(qū)，使左區(qū)的有關(guān)鍵字小于等于K1，右區(qū)所有關(guān)鍵字大于等于K1，最后控制居兩個(gè)子區(qū)中間的適當(dāng)位置。在子區(qū)內(nèi)數(shù)據(jù)尚處于無(wú)序狀態(tài)。將右區(qū)首、尾指針保存入棧，對(duì)左區(qū)進(jìn)行與第（1）步相類(lèi)似的處理，又得到它的左子區(qū)和右子區(qū)，控制字區(qū)中。重復(fù)第（1）、（2）步，直到左區(qū)處理完畢。然后退棧對(duì)一個(gè)個(gè)子區(qū)進(jìn)行相類(lèi)似的處理，直到棧空。分區(qū)處理函數(shù)hoare思路：首先用兩個(gè)指針i、j分別指向首、尾兩個(gè)關(guān)鍵字，i=1，j=8。如對(duì)(46、56、14、43、95、10、19、72)。第一個(gè)關(guān)鍵字46作為控制字，

7、該關(guān)鍵字所屬的記錄另存儲(chǔ)在一個(gè)x變量中。從文件右端元素rj.key開(kāi)始與控制字x.key相比較，當(dāng)rj.key大于等于x.key時(shí)，rj不移動(dòng)，修改指針j，j-，直到rj.key<x.key，把記錄rj移動(dòng)到文件左邊i所指向的位置;然后在文件左邊修改i指針,i+，讓ri.key與x.key相比較，當(dāng)ri.key小于等于x.key時(shí)，ri不移動(dòng)，修改指針i，i-，直到ri.key<x.key, 把記錄ri移動(dòng)到文件右邊j所指向的位置;然后在文件右邊修改j指針j-。重復(fù)上面的步驟.2.4 堆排序思路：把n個(gè)記錄存于向量r之中，把它看成完全二叉樹(shù)，此時(shí)關(guān)鍵字序列不一定滿(mǎn)足堆的關(guān)系。堆排序

8、大體分為兩步處理：初建堆，從堆的定義出發(fā)，當(dāng)i=1、2、。、2/n時(shí)應(yīng)滿(mǎn)足ki<=k2i和ki<=k2i+1.所以先取i=n/2(它一定是第n個(gè)結(jié)點(diǎn)的雙親編號(hào)),將以i結(jié)點(diǎn)為根的子樹(shù)調(diào)整為堆，然后令i=i-1，將以不結(jié)點(diǎn)為根的子樹(shù)調(diào)整為堆。此時(shí)可能會(huì)反復(fù)調(diào)整某些結(jié)點(diǎn)，直到i=1為止，堆初步建成。堆排序，首先輸出堆頂元素（一般是最小值）,讓堆中最后一個(gè)元素上移到原堆頂位置，然后恢復(fù)堆。因?yàn)榻?jīng)過(guò)第一步輸出堆頂元素的操作后，往往破壞了堆關(guān)系，所以要恢復(fù)堆；重復(fù)執(zhí)行輸出堆頂元素、堆尾元素上移和恢復(fù)堆的步驟。3 概要設(shè)計(jì)3.1 頭文件#include<stdio.h>#inclu

9、de<stdlib.h>#include<cstdlib>#include<time.h>3.2 ADT struct element int key;list20;struct rnodeint key;int point;3.3 各種操作函數(shù)：（1）創(chuàng)建一個(gè)數(shù)組函數(shù)：int creat()；（2）輸出數(shù)組函數(shù)：void print(struct element a20,int n)；（3）保存函數(shù)：void save(struct element aSIZE,int n, char fileName ) （4）直接插入排序函數(shù)：void insert_s

10、ort(element a, int n)（5）希爾排序函數(shù)：void shell(struct element a20,int n)；（6）快速排序函數(shù)（分區(qū)處理函數(shù)）：int hoare(struct element a20,int l,int h)；（7）非遞歸的快速排序函數(shù)：void quick1(struct element a20,int n)；（8）遞歸的快速排序函數(shù)：void quick2(struct element a20,int l,int h)；（9）堆排序（調(diào)整堆的函數(shù)）：void heap(struct element a20,int i,int m)；（10）堆排

11、序（主體函數(shù)）：void heapsort(struct element a20,int n)；（11）時(shí)間函數(shù)：start = clock();end = clock();3.4 主函數(shù)Void main()接受命令（選擇要執(zhí)行的操作）；處理命令；輸出結(jié)果； 4 詳細(xì)設(shè)計(jì)4.1 主函數(shù)如下：為程序主函數(shù)。#include<stdio.h>#include<stdlib.h>#include<cstdlib>#include<time.h>#define SIZE struct element int key;listSIZE;/創(chuàng)建一個(gè)數(shù)組/i

12、nt creat() int i,n; int num;n=0;printf("請(qǐng)輸入元素個(gè)數(shù):");scanf("%d",&num);for( i = 0;i < num; i+ )listn.key = rand() % 10000;n+;return(n);/輸出數(shù)組/void print(struct element aSIZE,int n) int i;for(i=0;i<n;i+) printf("%5d",ai .key); printf("n");/保存到文件/void save

13、(struct element aSIZE,int n, char fileName ) int m_wr=0; / 寫(xiě)入TXT文件變量 FILE *fp;if ( ( fp = fopen ( fileName, "w" ) ) = NULL ) printf("File writer errorn"); for (int m=0; m<n; m+ )m_wr = am.key; fprintf ( fp, "%d ", m_wr ); / 寫(xiě)入TXT中 fclose ( fp );4.2 直接插入排序 如下：為直接插入排序的

14、算法。void InsertClass:InsertSort ( SqList *L ) / 對(duì)順序表L作直接插入排序int key = 0; / 關(guān)鍵字 int m_wr = 0; / 寫(xiě)入TXT文件變量 unsigned long i, j, n;FILE *fp;if ( !L->elem ) / 如果線性表為空exit ( ERROR ); for ( i=2; i<L->Length; +i) key = L->elemi; / 設(shè)定關(guān)鍵字if ( key < L->elemi-1 ) / 與前一個(gè)數(shù)字比較，是否“<” L->elemi

15、 = L->elemi-1;L->elemi-1 = key;for ( j=i-2; key < L->elemj ; -j ) L->elemj+1 = L->elemj; / 數(shù)據(jù)后移L->elemj+1 = key; / 插入到正確位置if ( ( fp = fopen ( "D:順序表直接插入排序.txt", "a+" ) ) = NULL ) exit ( ERROR ); for ( n=0; n<L->Length; n+ )m_wr = L->elemn; / 獲取線性表元素f

16、printf ( fp, "%d ", m_wr ); / 寫(xiě)入TXT中 fclose ( fp );4.3 希爾排序如下：為希爾排序算法。void shell(struct element aSIZE,int n)int i,j,k;for(i=n;i>=1;i-)ai.key=ai-1.key;k=n/2;while(k>=1)for(i=k+1;i<=n;i+)a0.key=ai.key;j=i-k;while(aj.key>a0.key)&&(j>=0)aj+k.key=aj.key;j=j-k;aj+k=a0;k=k/

17、2;for(i=0;i<n;i+) ai.key=ai+1.key;printf("輸出希爾排序的結(jié)果:n");4.4 起泡排序如下：為起泡排序算法void InsertClass:BubbleSort ( SqList *L )/ 對(duì)順序表L作冒泡排序int key = 0; / 設(shè)定關(guān)鍵字int m_wr = 0; unsigned long i, j, n;FILE *fp;if ( !L->elem ) exit ( ERROR ); for ( j=1; j<L->Length; j+ ) / j控制排序長(zhǎng)度 for ( i=0; i<

18、;L->Length-j; i+ ) / 每趟排序長(zhǎng)度減1 if ( L->elemi < L->elemi+1 ) / 順序不變key = L->elemi+1; / 將較大值賦給keyelse / 如果小于，順序交換key = L->elemi; / 利用關(guān)鍵字L->elemi = L->elemi+1; L->elemi+1 = key;if ( ( fp = fopen ( "D:順序表冒泡排序.txt", "a+" ) ) = NULL ) exit ( ERROR );for ( n=0;

19、 n<L->Length; n+ )m_wr = L->elemn; fprintf(fp, "%d ", m_wr ); fclose ( fp );4.5 快速排序如下：為快速排序算法。int InsertClass:Partition ( SqList *L, int low, int high )/ 交換子表中記錄int key = 0;if ( !L->elem ) exit ( ERROR ); key = L->elemlow; / 將子表的第一個(gè)做為記錄的關(guān)鍵字while ( low < high ) / 從表的兩端交替向

20、中間掃描 while ( low<high && L->elemhigh >= key ) -high; L->elemlow = L->elemhigh; / 將比樞軸記錄小的記錄移到低端while ( low<high && L->elemlow<=key )+low;L->elemhigh = L->elemlow; / 將比樞軸記錄大的記錄移到高端L->elemlow = key; / 樞軸記錄到位return low; / 反回low的位置void InsertClass:QSort (

21、 SqList *L, int low, int high )/ 對(duì)子表進(jìn)行快速排序int pivotloc=0; if ( low < high ) / 長(zhǎng)度大于1 pivotloc = Partition ( L, low, high ); / 將L->elemlow.high一分為二QSort ( L, low, pivotloc-1 ); / 低子表遞歸排序QSort ( L, pivotloc+1, high ); / 高子表遞歸排序void InsertClass:QuickSort ( SqList *L )/對(duì)順序表L作快速排序int m_wr = 0;unsign

22、ed long n; FILE *fp; QSort ( L, 0, L->Length-1 ); / 調(diào)用遞歸函數(shù)進(jìn)行排序if ( ( fp = fopen ( "D:順序表快速排序.txt", "a+" ) ) = NULL ) exit (ERROR );for ( n=0 ; n<L->Length ; n + )m_wr = L->elemn; fprintf ( fp, "%d ", m_wr ); fclose ( fp );4.6 選擇排序如下：為選擇排序算法void InsertClass:T

23、reeSort ( SqList *L ) / 對(duì)順序表L進(jìn)行樹(shù)形選擇排序 int m_wr = 0;unsigned long floor, crunode,crunode1;unsigned long i, j, j1, m, n; ElemType *t; FILE *fp;if ( !L->elem ) exit ( ERROR );m = L->Length; floor = ( unsigned long ) ceil ( log(m) / log(2) ) + 1; / 完全二叉樹(shù)的層數(shù) crunode = ( unsigned long ) pow ( 2, flo

24、or ) - 1; / floor層完全二叉樹(shù)的結(jié)點(diǎn)總數(shù) crunode1 = ( unsigned long ) pow ( 2, floor - 1 ) - 1; / floor-1層完全二叉樹(shù)的結(jié)點(diǎn)總數(shù) t = (ElemType*) malloc ( crunode * sizeof ( ElemType ) ); / 二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu) / 創(chuàng)建完全二叉樹(shù) for ( i=0; i<=m; i+ ) / 將L->elem賦給葉子結(jié)點(diǎn) tcrunode1+i = L->elemi; for ( i=crunode1+m; i<crunode; i+ ) /

25、給多余的葉子的關(guān)鍵字賦無(wú)窮大 ti = INT_MAX; / 頭文件中的 j1 = crunode1; j = crunode; / 給非葉子結(jié)點(diǎn)賦值 while ( j1 ) for ( i=j1; i<j; i+=2 ) ti < ti+1 ? (t(i+1)/2-1=ti) : (t(i+1)/2-1 = ti+1); / 條件？表達(dá)式：表達(dá)式 j = j1; j1 = (j1-1) / 2; for ( i=0; i<m; i+ ) / 從ti中選取最小給L->elemi L->elemi = t0; / 將當(dāng)前最小值賦給L->elemi j1 =

26、0; for ( j=1; j<floor; j+ ) / 沿樹(shù)根找結(jié)點(diǎn)t0在葉子中的序號(hào)j1 t2*j1+1 = tj1 ? (j1=2*j1+1) : (j1=2*j1+2); /if-else語(yǔ)句 tj1 = INT_MAX; while ( j1 ) j1 = (j1+1) / 2 - 1; / 序號(hào)為j1的結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號(hào) t2*j1+1 <= t2*j1+2 ? (tj1=t2*j1+1) : (tj1=t2*j1+2); if ( (fp = fopen ( "D:順序表樹(shù)形選擇排序.txt", "a+" ) ) = NULL

27、 ) exit ( ERROR );for ( n=0; n<L->Length; n+ )m_wr = L->elemn; fprintf ( fp, "%d ", m_wr ); fclose ( fp ); free ( t );4.7 堆排序如下：為堆排序算法void InsertClass:InitHeap ( SqList *L, int n )/ 初始化大頂堆int key = 0; int i, j, k; for( i=(n-1)/2; i>=0; i- ) / 從編號(hào)最大的終端節(jié)點(diǎn)開(kāi)始 j = 2 * i + 1; / 編號(hào)為j的

28、節(jié)點(diǎn)是i的左孩子 k = i; if( L->elemj < L->elemj+1 && j+1<n ) / 編號(hào)為i的左孩子小于i的右孩子比較j+; / 找出左右孩子中較小的節(jié)點(diǎn) while( L->elemj > L->elemk && 2*k+1 < n) / 編號(hào)為i的左孩子與i比較 key = L->elemk; / 如果大于，則交換 L->elemk = L->elemj; L->elemj = key;k = j; j = 2 * k + 1;if( L->elemj+1

29、 > L->elemj && j+1 < n) / 交換以后可能造成堆的破壞,需要從交換的節(jié)點(diǎn)往后調(diào)整j+;/ 大頂堆調(diào)整void InsertClass:AdjustHeap(SqList *L,int n) int key = 0; int i = 0;int j = 0; while ( 2*i+1 < n ) / 從樹(shù)頂往后找 j = 2 * i + 1; if ( L->elemj < L->elemj+1 && j+1<=n ) / 找出左右孩子中較小的節(jié)點(diǎn) j+ ; / 如果左孩子小于右孩子，則選擇右

30、孩子與父結(jié)點(diǎn)比較 if ( L->elemj > L->elemi ) / 交換 key = L->elemi; / 利用關(guān)鍵字做中間保介質(zhì) L->elemi = L->elemj; L->elemj = key; i = j; / 對(duì)順序表L進(jìn)行堆排序void InsertClass:HeapSort(SqList *L)int key = 0;int m_wr = 0; int i = 0;unsigned long n;FILE *fp;if ( !L->elem ) exit ( ERROR ); InitHeap ( L, L->

31、Length ); / 初始化大頂堆 for ( i=L->Length-1; i>0; i- ) / 輸出堆頂元素,不斷調(diào)整堆if ( L->elem1 > L->elem0 ) / 此句極其重要break;key = L->elemi; / 利用關(guān)鍵字L->elemi = L->elem0;L->elem0 = key;AdjustHeap ( L, i-1 ); / 調(diào)整if ( ( fp = fopen ( "D:順序表堆排序.txt", "a+" ) )=NULL ) exit ( ERRO

32、R );for ( n=0; n<L->Length; n+ )m_wr = L->elemn; fprintf ( fp, "%d ", m_wr ); fclose ( fp );4.8 歸并排序如下：為歸并排序算法int b;void InsertClass:Merge ( int a, int low, int middle, int high )/ 將相鄰兩個(gè)子表合并 int h, i, j, k; h = low; i = low; j = middle+1; while ( h<=middle && j<=high

33、 ) / 前段子表 if ( ah<=aj ) / 排序后的值放入到b前段中 bi = ah; h+; else / 將較小的值放入前段子表 bi = aj; j+; i+; if ( h>middle ) / 后段子表 for ( k=j; k<=high; k+ ) / 排序后的值放入到b后段中 bi = ak; i+; else for ( k=h; k<=middle; k+ ) bi = ak; i+; for ( k=low; k<=high; k+ ) ak = bk; void InsertClass:Msort(int a,int low,int

34、 high)/ 利用遞歸進(jìn)行歸并排序 int middle = 0; / 兩子表的分隔點(diǎn) if ( low<high ) middle = (low+high) / 2; Msort ( a, low, middle ); / 前段子表排序 Msort ( a, middle+1, high ); / 后段子表排序 Merge ( a, low, middle, high ); void InsertClass:MergeSort ( SqList *L ) / 對(duì)順序表L作歸并排序 int m_wr = 0;unsigned long n;FILE *fp; Msort ( (*L).

35、elem, 0, (*L).Length-1 ); if ( ( fp = fopen ( "D:順序表歸并排序.txt", "a+" ) ) = NULL ) exit (ERROR );for ( n=0; n<L->Length; n+ )m_wr = L->elemn; fprintf(fp, "%d ", m_wr ); fclose ( fp );5 系統(tǒng)測(cè)試它的的任務(wù)是盡可能徹底地檢查出程序中的錯(cuò)誤，提高軟件系統(tǒng)的可靠性，其目的是檢驗(yàn)系統(tǒng)"做得怎樣？"。這階段又可分為三個(gè)步驟：模塊測(cè)試，測(cè)試每個(gè)模塊的程序是否有錯(cuò)誤；組裝測(cè)試，測(cè)試模塊之間的接口是否正確；確認(rèn)測(cè)試，測(cè)試整個(gè)軟件系統(tǒng)是否滿(mǎn)足用戶(hù)功能和性能的要求。該階段結(jié)束應(yīng)交付測(cè)試報(bào)告，說(shuō)明測(cè)試數(shù)據(jù)的選擇，測(cè)試用例以及測(cè)試結(jié)果是否符合預(yù)期結(jié)果。測(cè)試發(fā)現(xiàn)問(wèn)題之后要經(jīng)過(guò)調(diào)試找出錯(cuò)誤原因和位置，然后進(jìn)行改正。是基于系統(tǒng)整體需求說(shuō)明書(shū)的黑盒類(lèi)測(cè)試，應(yīng)覆蓋系統(tǒng)所有聯(lián)合的部件。系統(tǒng)測(cè)試是針對(duì)整個(gè)產(chǎn)品系統(tǒng)進(jìn)行的測(cè)試，目的是驗(yàn)證系統(tǒng)是否滿(mǎn)足了需求規(guī)格的定義，找出與需求規(guī)格不相符合或與