排序?qū)嶒?yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告排序小組成員：張家銘2010416648吳建明2010416603劉仕乾2010416682王戰(zhàn)海2010416596

1實(shí)驗(yàn)題目為了更好的學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，理解排序思想，直觀的觀察出每一步所進(jìn)行的操作。進(jìn)行此實(shí)驗(yàn)報(bào)告。主要包含直接插入排序，希爾排序，冒泡排序，快速排序，選擇排序，堆排序。2需求分析在現(xiàn)在的任何pc、mac上均可裝有c-Free或VC6.0上均可編寫調(diào)試。（1）輸入形式，先用種子函數(shù)初始化隨機(jī)生成函數(shù)，然后用隨機(jī)生成函數(shù)生成十個(gè)數(shù)據(jù)。通過(guò)選擇你想選用的排序方式包括：insertSort（arr,10）;//插入排序shellSort（arr,3,10）;//希爾排序bubbleSort（arr,10）;//冒泡排序QuickSort（arr,1,11）;//快速排序selectSort（arr,10）;//選擇排序heapsort（arr,10000）;//堆排序（2）輸出形式，通過(guò)調(diào)用printarr函數(shù)進(jìn)行輸出數(shù)據(jù)，并在排序之中調(diào)用此函數(shù)了來(lái)直觀的查看排序的過(guò)程。（3）程序附加功能，在排序進(jìn)行之前設(shè)計(jì)了開(kāi)始時(shí)間（start=time（NLULL）），在排序結(jié)束之后設(shè)計(jì)了結(jié)束時(shí)間（end=time（NULL）），之后在輸出該排序執(zhí)行的時(shí)間（printf（"執(zhí)行時(shí)間為：％d\n”,（end-start））;）。直觀的看出該程序的優(yōu)劣。PS：執(zhí)行小量數(shù)據(jù)體現(xiàn)不出時(shí)間損耗，可以設(shè)計(jì)大量數(shù)據(jù)看出時(shí)間損耗。（4）測(cè)試數(shù)據(jù)，隨機(jī)生成，數(shù)據(jù)不定。3概要設(shè)計(jì)包含的頭文件#include<stdio.h>#include<stdlib.h>#include<time.h>用于生成隨機(jī)函數(shù)和計(jì)時(shí)用本程序包含的主要函數(shù)：〃輸出列表函數(shù)//插入排序注意監(jiān)視哨作用//希爾排序一趟d為步長(zhǎng)//希爾排序//冒泡排序〃快速排序重點(diǎn)的排序//選擇排序//建堆i為根節(jié)點(diǎn)n為個(gè)數(shù)//堆排序//主函數(shù)voidprintarr(intarr[],intn)voidinsertSort(intarr[],intn)voidshellpass(intarr[],intd,intn)voidshellSort(intarr[],intb,intn)voidbubbleSort(intarr[],intn)voidQuickSort(int〃輸出列表函數(shù)//插入排序注意監(jiān)視哨作用//希爾排序一趟d為步長(zhǎng)//希爾排序//冒泡排序〃快速排序重點(diǎn)的排序//選擇排序//建堆i為根節(jié)點(diǎn)n為個(gè)數(shù)//堆排序//主函數(shù)各函數(shù)之間的關(guān)系如圖3-3：mainO圖3-3程序中各函數(shù)之間的關(guān)系4詳細(xì)設(shè)計(jì)〃插入排序注意監(jiān)視哨作用直接插入排序，arr[0]為監(jiān)視哨的作用。把未排好序的第一個(gè)數(shù)依次與已排好序的比較，尋找到合適位置插入。詳細(xì)設(shè)計(jì)如下：voidinsertSort(intarr[],intn){〃插入排序注意監(jiān)視哨作用inti,j;for(i=2;i<=n;i++){〃安放監(jiān)視哨arr[0]=arr[i];〃安放監(jiān)視哨j=i-1;while(arr[0]<arr[j]){arr[j+1]=arr[j];//j--//j--很重要}arr[j+1]=arr[0];printf("Thatis%dtimesofwhistle%2d:",i-1,arr[0]);//自己學(xué)習(xí)觀察用;printarr(arr,10);}}(2)希爾排序，希爾排序中不需要安放監(jiān)視哨，while(j>0&&arr[0]<arr[j]);為設(shè)置終止條件。//希爾排序一趟d為步長(zhǎng);voidshellpass(intarr[],int//希爾排序一趟d為步長(zhǎng);inti,j;

for(i=d+1;i<=n;i++)〃注意類比插入排序；沒(méi)有監(jiān)視哨if(arr[i]<arr[i-d]){arr[0]=arr[i];j=i-d；do{arr[j+d]=arr[j];〃每一組內(nèi)向后移動(dòng)；j=j-d;}while(j>0&&arr[0]<arr[j]);〃由于沒(méi)有監(jiān)視哨所以必須設(shè)置終止條件;arr[j+d]=arr[0];}〃觀察學(xué)習(xí)用〃希爾排序〃這里一定注意“1”是否執(zhí)行問(wèn)題邊界//冒泡排序printarr(arr,10);〃觀察學(xué)習(xí)用〃希爾排序〃這里一定注意“1”是否執(zhí)行問(wèn)題邊界//冒泡排序doshellpass(arr,b,n);b=b/2;}while(b>=1);//printarr(arr,10);}冒泡排序：voidbubbleSort(intarr[],intn){inti,j;for(i=n;i>=1;i--){for(j=1;j<=i;j++){if(arr[j]>arr[j+1]){arr[0]=arr[j];arr[j]=arr[j+1];arr[j+1]=arr[0];}}}}快速排序，重要的是設(shè)置樞值，樞值的選擇是任意的，每一次交換數(shù)據(jù)時(shí)要比較是否〃快速排序重點(diǎn)的排序?。。。。。。。。?！j>p或i<p，執(zhí)行結(jié)束的條件是i=j。voidQuickSort(intdata[],intleft,intright){

intp=left;//p為樞值inti=left,j=right;data[0]=data[left];//data[0]類似監(jiān)視哨作用while(i<=j){while(data[j]>=data[0]&&j>=p)j--;if(j>=p){data[p]=data[j];p=j;}printarr(data,10);while(data[i]<=data[0]&&i<=p)i++;if(i<=p){data[p]=data[i];p=i;}printarr(data,10);}data[p]=data[0];printf("結(jié)束一次,Resultis:\n");printarr(data,10);printf(”下一次開(kāi)始:\n");if(p-left>1)QuickSort(data,left,p-1);if(right-p>1)QuickSort(data,p+1,right);}選擇排序，設(shè)定最小值記錄min。〃快速排序重點(diǎn)的排序?。。。。。。。。?！voidselectSort(intarr[],intn){inti,j,min;for(i=1;i<n;i++){min=i;for(j=i+1;j<=n;j++)if(arr[min]>arr[j])min=j;注意樞值的選擇是任意的！?。?！語(yǔ)句聲明必須放在最前面注意〃遞歸開(kāi)始樞值左邊〃遞歸開(kāi)始樞值左邊//選擇排序arr[0]=arr[i];

arr[i]=注意樞值的選擇是任意的！?。?！語(yǔ)句聲明必須放在最前面注意〃遞歸開(kāi)始樞值左邊〃遞歸開(kāi)始樞值左邊//選擇排序}}(5)堆排序，建堆是重點(diǎn)，巧妙的利用了根節(jié)點(diǎn)與孩子節(jié)點(diǎn)的關(guān)系child=2*i或者child=2*i+i在比較是否越界時(shí)與利用child<=n和child<n&&arr[child+1]>arr[child].這個(gè)思想很值得學(xué)習(xí)。voidshift(intarr[],inti,intn)//i為根節(jié)點(diǎn)n為一共有的個(gè)數(shù)建堆{intchild;child=2*i;//i的左孩子為2*i,右孩子為2*i+1arr[0]=arr[i];while(child<=n){if(child<n&&arr[child+1]>arr[child])//讓child指向孩子中較大的一個(gè){child=child+1;}if(arr[0]<arr[child])〃如果孩子節(jié)點(diǎn)大{arr[i]=arr[child];〃交換孩子節(jié)點(diǎn)和根節(jié)點(diǎn)i=child;child=2*i;}elsebreak;}arr[i]=arr[0];〃將根放在合適位置}//堆排序?qū)[1...n]進(jìn)行排序//將a[1...n]//堆排序?qū)[1...n]進(jìn)行排序//將a[1...n]建成大根堆//進(jìn)行n-1趟排序〃交換堆頂元素和最后一個(gè)元素//將a[1...i-1]重建為堆inti;for(i=n/2;i>=1;i--){shift(arr,i,n);}for(i=n;i>=2;i--){arr[0]=arr[1];arr[1]=arr[i];arr[i]=arr[0];shift(arr,1,i-1);}5調(diào)試分析（1）采用在關(guān)鍵位置插入輸出語(yǔ)句進(jìn)行查看，自我感覺(jué)這種方法很好，直觀。（2）在進(jìn)行快速排序時(shí)，自我感覺(jué)沒(méi)錯(cuò)，編譯時(shí)報(bào)錯(cuò)，檢查之后是把賦值語(yǔ)句放在聲明語(yǔ)句之前，（data[0]=data[left];intp=leftinti=left,j=right;正確應(yīng)是intp=leftinti=left,j=right;data[0]=data[left];）聲明在前。（3）自己注意的是以后選擇變量最好見(jiàn)名知意的，會(huì)減少很多錯(cuò)誤，避免把自己繞進(jìn)去，整糊涂了。（4）在進(jìn)行堆排序時(shí)花費(fèi)了很長(zhǎng)時(shí)間，主要是在建堆的時(shí)候，沒(méi)有體會(huì)全面，