北京郵電大學
資料結構試驗報告
實驗名稱: 實驗四排序
學生姓名:
班級:班內序號:
學號:日期: 2023年1月4日
學習、實現、對比各種排序演算法,掌握各種排序演算法的優劣,以及各種演算法使用的情況。
使用簡單陣列實現下面各種排序演算法,並進行比較。
排序演算法:
1、插入排序
2、希爾排序
3、氣泡排序
4、快速排序
5、簡單選擇排序
6、堆排序(選作)
7、歸併排序(選作)
8、基數排序(選作)
9、其他
要求:1、測試資料分成三類:正序、逆序、隨機資料
2、對於這三類資料,比較上述排序演算法中關鍵字的比較次數和移動次數(其中關鍵字交換計為3次移動)。
3、對於這三類資料,比較上述排序演算法中不同演算法的執行時間,精確到微秒(選作)
4、對2和3的結果進行分析,驗證上述各種演算法的時間複雜度
編寫測試main()函式測試線性表的正確性。
3 程式分析
3.1儲存結構
順序儲存結構——陣列
3.2關鍵演算法分析
1.插入排序:依次將待排序的序列中的每乙個記錄插入到先前排序好的序列中,直到全部記錄排序完畢
void insertsort(int r,int n,int* ***pare,int* move)//插入排序
if(j>=0) (****pare)++;
r[j+1]=x;}}
2.希爾排序:先將整個序列分割成若干個子列,分別在各個子列中運用直接插入排序,待整個序列基本有序時,再對全體記錄進行一次直接插入排序
void shellinsert(int r,int n,int* ***pare,int* move)//希爾排序
if(j>=0) (****pare)++;
r[j+d]=x;
}else (****pare)++;}}
}3.氣泡排序:兩兩比較相鄰記錄的關鍵碼,如果反序則交換,直到沒有反序記錄為止
void bubblesort(int r,int n,int* ***pare,int* move)//交換(冒泡)排序
else (****pare)++;
}}}4.快速排序:首先選擇乙個基準,將記錄分割為兩部分,左支小於或等於基準,右支則大於基準,然後對兩部分重複上述過程,直至整個序列排序完成
int partion(int r,int first,int end,int* ***pare,int* move)//快速排序中的軸定位
if(i
while((i
if(i
}r[i]=zhou;//最後確定軸的位置
return i;
}void qsort(int r,int i,int j,int* ***pare,int* move)//快速排序
}5.選擇排序:從待排序的記錄序列中選擇關鍵碼最小的記錄並將它與序列中的第乙個記錄交換位置;然後從不包括第乙個位置上的記錄序列中選擇關鍵碼最小(或最大)的記錄並將它與序列中的第二個記錄交換位置;如此重複,直到序列中只剩下乙個記錄為止
void selectsort(int r,int n,int* ***pare,int* move)//選擇排序
if(min!=i)
}}4 程式執行結果
4.1主函式流程圖
4.2程式執行框圖
5 實驗心得
1.除錯時出現的問題及解決的方法
在初期構思**的時候,首先構造了各種演算法的基本實現**,封裝成類,已經能夠實現七種排序的基本功能,並且測試無誤。
之後考慮如何能簡化**以實現多達七種排序演算法的簡單呼叫、亂序和順序以及逆序資料的分別排序和效能指標統計(演算法移動次數和比較次數的精確統計)。
2.心得體會
程式的優化是乙個艱辛的過程,如果只是實現一般的功能,將變得容易很多,當加上優化,不論是效率還是結構優化,都需要精心設計。
3.改進
本程式**設計時運用了遞迴的呼叫方式,效率還可以通過將其轉換為棧模擬的方式得以提高。另外還可以進一步考慮演算法時間的精確統計,以便從時間角度比較這幾種排序演算法的優劣。
完整源**
#include
using namespace std;
void insertsort(int r,int n,int* ***pare,int* move);
void shellinsert(int r,int n,int* ***pare,int* move);
void bubblesort(int r,int n,int* ***pare,int* move);
int partion(int r,int first,int end,int* ***pare,int* move);
void qsort(int r,int i,int j,int* ***pare,int* move);
void selectsort(int r,int n,int* ***pare,int* move);
void main()
{int i;
int ***pare=0;
int move=0;
cout<<"先輸入乙個正序陣列~~~" cout<<"請輸入陣列中含有的元素數量:"; cin>>n; int *r=new int[n]; cout<<"請輸入陣列中的元素:"; for(i=0;i>r[i]; int *a=new int[n]; for(i=0;iinsertsort(a,n,&***pare,&move); cout<<"\n插入排序結果為:"; for(i=0;icout<<"\n比較次數為" for(i=0;ishellinsert(b,n,&***pare,&move); cout<<"希爾排序結果為:"; for(i=0;icout<<"\n比較次數為" for(i=0;ibubblesort(c,n,&***pare,&move); cout<<"交換排序結果為:"; for(i=0;icout<<"\n比較次數為" move=0; int *d=new int[n]; for(i=0;iqsort(d,0,n-1,&***pare,&move); 實驗名稱 實驗 2.1 學生姓名 班級 班內序號 學號 日期 1 實驗要求 1.實驗目的 熟悉c 語言的基本程式設計方法,掌握整合編譯環境的除錯方法 學習指標 模板類 異常處理的使用 掌握線性表的操作的實現方法 學習使用線性表解決實際問題的能力。2.實驗內容 完成單鏈表的基本功能,編寫測試main ... 課程資料結構 實驗名稱實驗六 內部排序院系專業班級實驗地點 姓名學號實驗時間 指導老師實驗成績批改日期 一.實驗目的 1.熟悉相關的排序演算法 二.實驗內容及要求 1.實現兩種排序演算法 三.實驗過程及結果 實驗過程 源程式 include void main void charu a i 1 m ... 2008級資料結構實驗報告 實驗名稱 實驗二棧和佇列 學生姓名 班級 2008211113 班內序號 學號 日期 2009年11月8日 1 實驗要求 通過選擇下面五個題目之一進行實現,掌握如下內容 進一步掌握指標 模板類 異常處理的使用 掌握棧的操作的實現方法 掌握佇列的操作的實現方法 學習使用棧解...北郵資料結構實驗報告
資料結構排序實驗報告
北郵資料結構實驗二題目