資料結構實驗報告實驗

實驗名稱：實驗四排序（題目1）

學生姓名：

班級：班內序號：

學號：日期： 2023年12月19日

1．實驗要求

實驗目的：學習、實現、對比各種排序演算法，掌握各種排序演算法的優劣，以及各種演算法使用的情況。

實驗內容：

使用簡單陣列實現下面各種排序演算法，並進行比較。

排序演算法：

1、插入排序

2、希爾排序

3、氣泡排序

4、快速排序

5、簡單選擇排序

6、堆排序

7、其他

要求：1、測試資料分成三類：正序、逆序、隨機資料

2、對於這三類資料，比較上述排序演算法中關鍵字的比較次數和移動次數（其中關鍵字交換計為3次移動）。

3、對2的結果進行分析，驗證上述各種演算法的時間複雜度。

編寫測試main()函式測試線性表的正確性。

2. 程式分析

2.1 儲存結構

程式採用的儲存機構是順序儲存，如下圖所示：

2.2 關鍵演算法分析

2.2.1 插入排序

插入排序的基本方法是尋找乙個指定元素在待排序元素中的位置，然後插入。一趟直接插入排序的c++描述過程如下：

①將待插入紀錄賦值給哨兵r[0]：r[0]=r[i];

②從後向前進行順序查詢：for(j=i-1;r[0]③元素後插：r[j+1]=r[j];

④插入記錄：r[j+1]=r[j];

效能分析：

原序列正序時直接插入排序達到最好的時間效能，比較次數為n-1，移動次數為0。原序列逆序時直接插入排序達到最差時間效能，比較次數為，移動次數為。

直接插入排序的平均時間複雜度為，空間複雜度為。

直接插入排序是一種穩定的排序演算法，特別適合於待排序集合基本有序的情況。

2.2.2 希爾排序

希爾排序的基本方法是將待排序的元素集分成多個子集，分別對這些子集進行直接插入排序，待整個序列基本有序時，再對元素進行一次直接插入排序。

希爾排序的整個過程如下：

for(int d=n/2;d>=1;d=d/2) //以d為增量

//在子串行中進行插入排序

for(int i=d+1;i<=n;i++) //一趟希爾排序

if(r[i]

r[0]=r[i];

for(int j=i-d;j>0&&r[0]//每隔d個記錄，進行一次比較和移動，d=1時即是最後一趟直接插入排序

r[j+d]=r[j];

r[j+d]=r[0];

}效能分析：

希爾排序的時間複雜度在和之間，空間複雜度為，是一種不穩定的排序演算法。

2.2.3 氣泡排序

氣泡排序的基本思想是，兩兩比較相鄰的元素，如果反序，則交換位置，知道沒有反序的元素為止。

具體描述如下：

//外迴圈：總共需要遍歷的趟數

for (int i=1;i

//內迴圈：每一趟需要比較的次數

for (int j=1;j<=n-i;j++)

if (r[j]>r[j+1]) //相鄰元素比較

r[0]=r[j];r[j]=r[j+1];r[j+1]=r[0];

若逆序，則交換

}效能分析：

原序列正序時氣泡排序達到最好的時間效能，比較次數為n-1，移動次數為0。原序列逆序時達到最差時間效能，比較次數為，移動次數為。平均時間複雜度為，空間複雜度為。

氣泡排序是一種穩定的排序演算法。

2.2.4 快速排序

快速排序是氣泡排序的改進演算法，快速排序元素的比較和移動是從兩端向中間進行的，因而元素移動的距離較遠。快速排序的基本思想是，在分割槽中選擇乙個元素作為軸值，將待排序元素劃分成兩個分割槽，使得左側元素的關鍵碼均小於或等於軸值，右側元素的關鍵碼均大於或等於軸值，然後分別對這兩個分割槽重複上述過程直到整個序列有序。

經過優化改進的快速排序演算法如下：

//一趟快速排序

int partion(int r,int first,int end)

//快速排序

void qsort(int r,int i,int j)

效能分析：

快速排序的時間複雜度為，棧的深度為。快速排序是一種不穩定的排序方法。

2.2.5 簡單選擇排序

簡單選擇排序的基本思想是：第1趟，在待排序紀錄r[1…n]中選出最小的記錄，將它與r[1]交換；第2趟，在待排序記錄r[2…n]中選出最小的記錄，將它與r[2]交換……以此類推，第i趟將待排序記錄r[i…n]中選出關鍵碼最小的記錄，與r[i]交換，使有序序列不斷增長直到全部排序完畢。第i趟排序的過程如下：

①假設index是最小的：int index=i;

②查詢最小的記錄：for(int j=i+1;j<=n;j++)

效能分析：

簡單選擇排序是移動次數最少的演算法，當原序列為正序時，比較次數為，移動次數為0；當原始序列為逆序時，比較次數為，移動次數為；平均情況下的時間複雜度為，空間複雜度為。簡單選擇排序是不穩定的。

2.2.6 堆排序

堆排序採用堆的儲存結構，即將陣列r存在乙個二叉樹中，根節點存放在r[1]，假設某結點存放在r[i]，則其左孩子存放在r[2i]，右孩子存放在r[2i+1]，非根結點r[i]的雙親結點存放在r[n/2]。每個結點的值都不大於其左右孩子結點的值的堆叫做小根堆，大根堆同里定義。採用小根堆儲存的堆排序的基本思想為小根堆的篩選過程，即：

總是將根結點與左右孩子結點進行比較，若不滿足小根堆條件，則將根結點與較小的結點交換，一直到葉子結點，或所有子樹均為小根堆為止。小根堆的篩選演算法如下：

void sift(int r,int k,int m) //m為編號最大的葉子結點的編號

堆排序的具體過程為：

①將待排序的元素構造成乙個堆；

②輸出堆頂元素；

③將堆中最後乙個元素移至堆頂，並將剩餘元素調整成堆。

反覆執行②和③直到堆中只有乙個元素，**如下：

void heapsort(int r,int n)

}使用小根堆的演算法時，排序結束後從r[1]到r[n]是逆序的。

效能分析：

堆排序可初始建堆的時間複雜度為，第i次建堆的時間複雜度為，一共n-i次輸出堆頂元素，總的時間複雜度為。堆排序是不穩定的排序演算法。

2.3 效能比較

3. 程式執行結果

測試主函式流程：

測試條件：

編譯環境為microsoft visual studio 2010ultimate。

測試結論：程式執行的結果與理論分析基本一致。

4. 總結

通過本次實驗，基本掌握了排序的各種程式設計方法以及中心思想，加深了對概念的理解。提高了動手能力以及思考能力。同時，在程式設計中也遇到了一些問題，通過自己的努力解決這些問題獲得了小小的成就感，對於自信心和興趣的培養都有好處。

改進：可以通過隨機數生成函式來生成隨機數，改進演算法的適用性。同時也可以用相應的時間函式來比較各種排序方法所用時間，比較其效率。

資料結構實驗報告實驗

資料結構實驗報告

資料結構實驗報告

資料結構實驗報告

相關推薦