直接插入排序、冒泡排序、快速排序—于—實驗七參考模板

1、寧德師范學(xué)院計算機系實驗報告（2014 201 5學(xué)年 第 一 學(xué)期）課程名稱數(shù)據(jù)結(jié)構(gòu)實驗名稱實驗七數(shù)據(jù)的排序與檢索專 業(yè)計算機科學(xué)與技術(shù)年 級2013級學(xué) 號B2013102141姓名于指導(dǎo)教師毛雁明實驗日期2014-12-21 / 8實驗?zāi)康呐c要求：1、掌握數(shù)據(jù)結(jié)構(gòu)中的幾種常用排序方法：插入排序、快速排序、選擇排序等。2、遇到實際問題能夠選擇適當(dāng)?shù)呐判蚍椒ń鉀Q。實驗設(shè)備（環(huán)境）：微機、C語言編程環(huán)境（VC+）實驗內(nèi)容： 給定的數(shù)組listN=213, 111, 222, 77, 400, 300, 987, 1024, 632, 555，試分別用直接插入排序、冒泡排序、快速排序?qū)ι鲜鰯?shù)據(jù)進

2、行排序。 要求：每種排序算法編寫為獨立的自定義函數(shù)且要求輸出每趟排序后的數(shù)據(jù)排列序列情況。實驗步驟、實驗結(jié)果及分析：(1) 函數(shù)代碼#include<stdio.h># define n 10typedef structint key;RecType;typedef RecType SeqListn+1;void insertSort(SeqList r)int i,j;for(i=2;i<=n;i+)r0=ri;j=i-1;while(r0.key<rj.key)rj+1=rj;j-;rj+1=r0;void bubblesort(SeqList r)int i,j,

3、exchange;for(i=1;i<n;i+)exchange=0;for(j=n-1;j>=i;j-)if(rj+1.key<rj.key)r0=rj+1;rj+1=rj;rj=r0;exchange=1;if(!exchange)break;int partition(SeqList r,int i,int j)RecType pivot=ri;while(i<j)while(i<j&&rj.key>=pivot.key)j-;if(i<j)ri+=rj;while(i<j&&ri.key<=pivot

4、.key)i+;if(i<j)rj-=ri;ri=pivot;return i;void quicksort(SeqList r,int low,int high)int pivotpos;if(low<high)pivotpos=partition(r,low,high);quicksort(r,low,pivotpos-1);quicksort(r,pivotpos+1,high);main(void) int low=1,high=10;SeqList r=0,213, 111, 222, 77, 400, 300, 987, 1024, 632, 555;int i; in

5、sertSort(r);printf("直接插入排序算法：n");for(i=1;i<=n;i+)printf("%-6d",ri);printf("n");bubblesort(r);printf("冒泡排序算法：n");for(i=1;i<=n;i+)printf("%-6d",ri);printf("n"); quicksort(r,low,high);printf("快速排序算法：n");for(i=1;i<=n;i+)print

6、f("%-6d",ri);printf("n");(2) 主函數(shù)流程圖(3) 運行結(jié)果(4) 實驗總結(jié) 本實驗主要考查直接插入排序、冒泡排序、快速排序三項函數(shù)調(diào)用，難度還是有的，需要我們首先理解這三種排序方式，排序?qū)嵸|(zhì)，然后我們就需要寫程序代碼，主函數(shù)還是很好寫的，快速排序算法代碼是個難點，還要嵌套一個調(diào)用函數(shù)需要我們在草稿紙上事先演算下，進行多次調(diào)試，達到要求。直接插入排序的方法是首先在當(dāng)前有序區(qū)ri.i-1中查找人ri的正常插入位置k；然后將rk.i-1中的記錄均后移一個位置，騰出k位置上的空間插入ri。其他方法與這有點不同，畫主函數(shù)流程圖要求我們對代碼整體有個框架認(rèn)識，首先動態(tài)分配空間，建立順序表，然后輸入整數(shù)進行判斷，不符合時繼續(xù)輸入整數(shù)，符合時進行選擇，然后執(zhí)行功能，選擇退出時，整個程序都退出。雖然經(jīng)過上學(xué)期對C語言半年的學(xué)習(xí)可以說掌握的基本可以，但是幾天不練就會手生，甚至不知如何下手，這時我們要查閱課本，通過這次實驗的練習(xí)，我在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的同時也對C語言進行了一次復(fù)習(xí)