文章目錄
- 一，實驗目的
- 二，實驗內容
- 1. 數據生成與初始化
- 2. 排序算法實現
- （1）直接插入排序
- （2）二分插入排序
- （3）希爾排序
- （4）冒泡排序
- （5）快速排序
- （6）簡單選擇排序
- （7）堆排序
- （8）二路歸并排序
- 3. 統計與輸出
- 三，實驗要求
- （1）實驗步驟與要求
- （2）注意事項
- 四、數據結構設計
- 五，示例代碼
- 10-1.cpp源代碼
- 六，操作步驟
- 七，運行結果
一，實驗目的
- 深入理解排序原理：掌握排序的基本概念、分類及穩定性等特性，明確不同排序算法的適用場景。
- 熟練實現經典算法：通過編碼實現直接插入、二分插入、希爾、冒泡、快速、簡單選擇、堆、二路歸并等8種排序算法，加深對算法邏輯的理解。
- 提升算法應用能力：運用排序算法解決實際數據處理問題，通過統計比較次數和移動次數量化分析算法效率，增強算法優化思維。
二，實驗內容
1. 數據生成與初始化
- 使用隨機數函數
rand()生成范圍在[1, MAXNUM-1]的隨機整數序列（MAXNUM設為100），確保序列長度可由用戶指定（1~99）。 - 示例序列（假設長度為8）：
[49, 38, 65, 97, 76, 13, 27, 49]。
2. 排序算法實現
（1）直接插入排序
- 思想：從第二個元素開始，將當前元素插入到已排序子序列的合適位置，通過順序比較和移動實現。
- 穩定性：穩定。
（2）二分插入排序
- 優化：利用二分查找確定插入位置，減少比較次數，移動次數與直接插入相同。
- 穩定性：穩定。
（3）希爾排序
- 思想：按增量序列分組，對每組進行直接插入排序，逐步縮小增量至1。
- 增量序列：
5, 3, 1（示例）。 - 穩定性：不穩定。
（4）冒泡排序
- 思想：相鄰元素比較，逆序時交換，每趟將最大元素“冒泡”到末尾。
- 優化：設置標記
change，若某趟無交換則提前終止。 - 穩定性：穩定。
（5）快速排序
- 思想：選擇基準值，通過分區操作將序列分為兩部分，遞歸排序。
- 分區策略：Hoare法（左右指針交替移動）。
- 穩定性：不穩定。
（6）簡單選擇排序
- 思想：每趟選擇未排序部分的最小元素，與當前位置交換。
- 穩定性：不穩定（相同元素相對順序可能改變）。
（7）堆排序
- 思想：構建大頂堆，每次將堆頂元素與末尾元素交換，調整堆結構。
- 步驟：建堆 → 交換堆頂與末尾 → 調整堆。
- 穩定性：不穩定。
（8）二路歸并排序
- 思想：遞歸分割序列，合并兩個有序子序列。
- 輔助空間：需要額外數組存儲臨時合并結果。
- 穩定性：穩定。
3. 統計與輸出
- 比較次數（cp）：記錄關鍵字比較操作的總次數。
- 移動次數（mv）：記錄元素賦值操作的總次數（如交換、插入等）。
- 輸出內容：
- 原始序列與排序后序列；
- 各算法的比較次數和移動次數；
- 算法效率對比表格。
三，實驗要求
（1）實驗步驟與要求
-
代碼補全：
- 參照提供的參考程序，補全各算法中缺失的代碼（如循環條件、指針移動邏輯等），確保算法邏輯正確。
- 示例補全點：
- 快速排序分區函數中左右指針的移動條件（
j--/i++）； - 冒泡排序的交換標記
change初始化與更新。
- 快速排序分區函數中左右指針的移動條件（
-
調試與測試：
- 測試用例：
- 隨機序列（如長度10、50、99）；
- 特殊序列（正序、逆序、重復元素多的序列）。
- 調試要點：
- 確保隨機數生成正確，無越界訪問；
- 驗證各算法排序結果是否正確，統計計數器（
cp、mv）是否準確。
- 測試用例：
-
數據記錄與分析：
- 表格示例：
| 排序算法 | 比較次數（cp） | 移動次數（mv） | 耗時（ms） | 穩定性 |
|---|---|---|---|---|
| 直接插入排序 | 35 | 28 | 12 | 穩定 |
| 快速排序 | 22 | 15 | 5 | 不穩定 |
- 分析方向：
- 比較次數與序列初始有序度的關系（如冒泡排序在正序時比較次數最少）；
- 移動次數與算法特性的關聯（如歸并排序移動次數較多但比較次數穩定）；
- 穩定性對特定場景的影響（如穩定排序適用于多關鍵字排序）。
（2）注意事項
- 空間復雜度：歸并排序需要額外空間（
O(n)），其他算法多為原地排序（O(1)，除堆排序的輔助空間）。 - 時間復雜度對比：
- 最優/平均情況：快速排序、歸并排序（
O(n log n)）； - 最壞情況：直接插入、冒泡、簡單選擇（
O(n2)）。
- 最優/平均情況：快速排序、歸并排序（
- 代碼規范：添加必要注釋，確保變量命名清晰（如
cp為comparison count，mv為movement count）。
四、數據結構設計
#define MAXNUM 100
typedef int KeyType; // 定義關鍵字類型為整型
typedef struct {
KeyType key; // 關鍵字項int other; // 其他數據項
}ElemType; // 元素類型
typedef struct {ElemType r[MAXNUM+1]; // r[0]閑置或用作哨兵int length; // 待排序元素個數
} SqList; // 順序表類型五，示例代碼
10-1.cpp源代碼
#define MAXNUM 100
#define TRUE 1
#define FALSE 0
#include<stdio.h>
#include<stdlib.h>
#include<time.h>typedef int KeyType;
typedef struct { // 定義元素的結構類型KeyType key; int other;
} ElemType;typedef struct { // 定義排序表結構類型ElemType r[MAXNUM+1];int length;
} SqList;//（1）創建隨機數排序表
void CreatList(SqList &L) {int i;do {printf(" 輸入排序表長度(1-%d)==>", MAXNUM-1);scanf("%d", &L.length);} while(L.length<1 || L.length>MAXNUM-1);srand((unsigned)time(NULL));for(i=1; i<=L.length; i++) // 隨機產生排序表L.r[i].key = 1 + rand()%(MAXNUM-1);
}// （2）直接插入排序
void InsertSort(SqList &L, int &cp, int &mv) {int i, j;for(i=2; i<=L.length; i++) {cp++;if (L.r[i].key < L.r[i-1].key) {L.r[0] = L.r[i]; mv++;for(j=i-1; L.r[0].key < L.r[j].key; j--) {L.r[j+1] = L.r[j]; cp++; mv++;}cp++; L.r[j+1] = L.r[0]; mv++;}//if}
}// （3）折半插入排序
void BinSort(SqList &L, int &cp, int &mv) {int i, j, low, high, mid;for(i=2; i<=L.length; i++) {L.r[0] = L.r[i]; mv++;low = 1; high = i-1;while(low <= high) { // 定位插入點mid = (low + high)/2; cp++;if (L.r[0].key < L.r[mid].key) high = mid-1;else low = mid+1;}for(j=i-1; j>=high+1; j--) { L.r[j+1] = L.r[j]; mv++;}L.r[high+1] = L.r[0]; mv++;}
}// （4）希爾排序
void ShellInsert(SqList &L, int dk, int &cp, int &mv) {//對順序表L作一趟希爾排序int i, j;for(i=dk+1; i<=L.length; i++) {cp++;if(L.r[i].key < L.r[i-dk].key) { //需將L.r[i]插入有序增量子表mv++;L.r[0] = L.r[i]; //L.r[i]暫存入L.r[0]for(j=i-dk; j>0 && L.r[0].key < L.r[j].key; j-=dk) { L.r[j+dk] = L.r[j]; //尋找插入位置時記錄后移cp++; mv++;}cp++; mv++; L.r[j+dk] = L.r[0]; //插入}//if}//for
} //ShellInsertSortvoid ShellSort(SqList &L, int &cp, int &mv) {//按增量序列5,3,1進行希爾排序ShellInsert(L, 5, cp, mv); //一趟增量為5的希爾排序ShellInsert(L, 3, cp, mv); //二趟增量為3的希爾排序ShellInsert(L, 1, cp, mv); //三趟增量為1的希爾排序
} //ShellInsertSort//（5）冒泡排序
void BubbleSort(SqList &L, int &cp, int &mv) {int i, j, change;for(i = 1, change = TRUE; i < L.length && change; i++) {change = FALSE;for(j = 1; j < L.length - i + 1; ++j) { cp++;if (L.r[j].key > L.r[j+1].key) {L.r[0] = L.r[j]; L.r[j] = L.r[j+1]; L.r[j+1] = L.r[0]; change = TRUE; mv += 3;}//if} //for }//for
} // BubbleSort//（6）快速排序
int Partition(SqList &L, int low, int high, int &cp, int &mv) {int i, j;KeyType pivotkey;L.r[0] = L.r[low]; mv++; pivotkey = L.r[0].key; i = low; j = high;while (i < j) {while (i < j && L.r[j].key >= pivotkey) {j--; cp++;}if(i < j) cp++;L.r[i] = L.r[j]; mv++;while (i < j && L.r[i].key <= pivotkey) {i++; cp++;}if(i < j) cp++;L.r[j] = L.r[i]; mv++;}L.r[i] = L.r[0]; mv++;return i;
}//Partitionvoid QSort(SqList &L, int low, int high, int &cp, int &mv) {//對L.r[low]～L.r[high]的元素進行快速排序int pivotloc;if (low < high) { pivotloc = Partition(L, low, high, cp, mv); //一趟劃分QSort(L, low, pivotloc-1, cp, mv);QSort(L, pivotloc+1, high, cp, mv);}//if
} //QSort//（7）簡單選擇排序
void SelectSort(SqList &L, int &cp, int &mv) {//對順序表作簡單選擇排序int i, j, k; // j保存剩余元素中最小值元素的下標for(i=1; i<L.length; i++) {for(k=i, j=i; k<=L.length; k++) {cp++;if(L.r[k].key < L.r[j].key) j = k;}if (j != i) {L.r[0] = L.r[i]; L.r[i] = L.r[j]; L.r[j] = L.r[0]; mv += 3;} } //for
} // SelectSort//（8）堆排序
void HeapAdjust(SqList &H, int s, int m, int &cp, int &mv) {// H.r[s .. m]中除H.r[s].key外均滿足堆的定義// 調整H.r[s]的關鍵字，使H.r[s .. m]成為一個大頂堆int j;H.r[0] = H.r[s]; mv++;for(j=2*s; j<=m; j*=2) { //沿key較大的孩子結點向下篩選if(j<m && H.r[j].key < H.r[j+1].key) ++j; //j為key較大的記錄的下標 if(j<m) cp++;cp++; if(H.r[0].key >= H.r[j].key) break; H.r[s] = H.r[j]; //較大的孩子結點值換到父結點位置mv++;s = j;}H.r[s] = H.r[0]; mv++; //H.r[0]應插入的位置在s處
} // HeapAdjustvoid HeapSort(SqList &H, int &cp, int &mv) { //對順序表H進行堆排序int i;for(i=H.length/2; i>0; --i) // 把H建成大頂堆HeapAdjust(H, i, H.length, cp, mv);for(i=H.length; i>1; --i) {H.r[0] = H.r[1]; H.r[1] = H.r[i]; H.r[i] = H.r[0]; mv += 3;//堆頂記錄和當前未排子序列中最后一個記錄相交換HeapAdjust(H, 1, i-1, cp, mv); //將H.r[1 .. i - 1] 重新調整為大頂堆 }
}// HeapSort //（9）二路歸并排序
void Merge(SqList &L, SqList &temp, int i, int m, int n, int &cp, int &mv)
{ // 引入輔助空間tempint b = i, j, k;for(j = m+1, k = 1; i <= m && j <= n; ++k) {if (L.r[i].key < L.r[j].key) temp.r[k] = L.r[i++];else temp.r[k] = L.r[j++];cp++; mv++;}for (; i <= m; ) {temp.r[k++] = L.r[i++]; mv++;}for (; j <= n; ) {temp.r[k++] = L.r[j++]; mv++;}for(i = b, k = 1; i <= n; ) {L.r[i++] = temp.r[k++]; mv++;}
} // Mergevoid MergeSort(SqList &L, SqList &temp, int s, int t, int &cp, int &mv) {//歸并排序int m;if (s < t) {m = (s + t)/2;MergeSort(L, temp, s, m, cp, mv);MergeSort(L, temp, m+1, t, cp, mv);Merge(L, temp, s, m, t, cp, mv); //合并L.r[s]~L.r[m]與L.r[m+1]~L.r[t]}//if
} // MergeSort//（10）輸出排序表
void OutputList(SqList L) {int i;for(i=1; i<=L.length; i++)printf("%3d", L.r[i].key);printf("\n");
}int main() {SqList LL, L; //LL為待排序表，L為排序表SqList temp; //二路歸并算法中所使用的臨時順序表int cp, mv; //cp記錄元素關鍵字比較次數，mv記錄元素移動次數printf("(1)創建隨機數排序表......\n");CreatList(LL); //待排序序列保存在LL表中printf(" 排序表輸出：");OutputList(LL);getchar();printf("(2)直接插入排序......\n");L = LL; cp = mv = 0;InsertSort(L, cp, mv);printf(" 排序結果：");OutputList(L);printf(" 排序效率：比較次數%d，移動次數%d。\n", cp, mv);getchar();printf("(3)折半插入排序......\n");L = LL; cp = mv = 0;BinSort(L, cp, mv);printf(" 排序結果：");OutputList(L);printf(" 排序效率：比較次數%d，移動次數%d。\n", cp, mv);getchar();printf("(4)希爾排序......\n");L = LL; cp = mv = 0;ShellSort(L, cp, mv);printf(" 排序結果：");OutputList(L);printf(" 排序效率：比較次數%d，移動次數%d。\n", cp, mv);getchar();printf("(5)冒泡排序......\n");L = LL; cp = mv = 0;BubbleSort(L, cp, mv);printf(" 排序結果：");OutputList(L);printf(" 排序效率：比較次數%d，移動次數%d。\n", cp, mv);getchar();printf("(6)快速排序......\n");L = LL; cp = mv = 0;QSort(L, 1, L.length, cp, mv);printf(" 排序結果：");OutputList(L);printf(" 排序效率：比較次數%d，移動次數%d。\n", cp, mv);getchar();printf("(7)簡單選擇排序......\n");L = LL; cp = mv = 0;SelectSort(L, cp, mv);printf(" 排序結果：");OutputList(L);printf(" 排序效率：比較次數%d，移動次數%d。\n", cp, mv);getchar();printf("(8)堆排序......\n");L = LL; cp = mv = 0;HeapSort(L, cp, mv);printf(" 排序結果：");OutputList(L);printf(" 排序效率：比較次數%d，移動次數%d。\n", cp, mv);getchar();printf("(9)二路歸并排序......\n");L = LL; cp = mv = 0;MergeSort(L, temp, 1, L.length, cp, mv);printf(" 排序結果：");OutputList(L);printf(" 排序效率：比較次數%d，移動次數%d。\n", cp, mv);return 0;
}
六，操作步驟
1，雙擊Visual Studio程序快捷圖標，啟動程序。
2，之前創建過項目的話，直接打開即可，這里選擇【創建新項目】。
3，單擊選擇【空項目】——單擊【下一步】按鈕。
4，編輯好項目的名稱和存放路徑，然后單擊【創建】按鈕。
5，創建C++程序文件，右擊【源文件】——選擇【添加】——【新建項】。
6，輸入項目名稱10-1.cpp，單擊【添加】按鈕。
7，編寫代碼，單擊運行按鈕，運行程序。
七，運行結果
1，實驗要求的測試結果。
2，編寫代碼測試測試的結果。
)
)
：頻域中的拉普拉斯算子)