排序實驗報告

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

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

for(i=d+1;i<=n;i++)〃注意類比插入排序；沒有監(jiān)視哨if(arr[i]<arr[i-d]){arr[0]=arr[i];j=i-d；do{arr[j+d]=arr[j];〃每一組內(nèi)向后移動；j=j-d;}while(j>0&&arr[0]<arr[j]);〃由于沒有監(jiān)視哨所以必須設置終止條件;arr[j+d]=arr[0];}〃觀察學習用〃希爾排序〃這里一定注意“1”是否執(zhí)行問題邊界//冒泡排序printarr(arr,10);〃觀察學習用〃希爾排序〃這里一定注意“1”是否執(zhí)行問題邊界//冒泡排序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ù)據(jù)時要比較是否〃快速排序重點的排序?。。。。。。。。?！j>p或i<p，執(zhí)行結束的條件是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("結束一次,Resultis:\n");printarr(data,10);printf(”下一次開始:\n");if(p-left>1)QuickSort(data,left,p-1);if(right-p>1)QuickSort(data,p+1,right);}選擇排序，設定最小值記錄min。〃快速排序重點的排序?。。。。。。。。?！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;注意樞值的選擇是任意的?。。?！語句聲明必須放在最前面注意〃遞歸開始樞值左邊〃遞歸開始樞值左邊//選擇排序arr[0]=arr[i];

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