實驗1 排序算法的效率分析
一、【實驗目的】
（1）復習排序算法的實現過程；
（2）設計平均與最壞情況下時間復雜度的數據環境并理解相關含義；
（3）初步了解算法時間復雜度的分析方法。
二、【實驗內容】
至少選擇3種排序算法，要求對每種排序算法設計2組數據，其中一組為最壞情況，一組為一般情況（隨機），數據規模不能少于10000。
記錄不同情況下算法的實際運行時間，同時分析算法最壞情況與平均情況的運行次數。
三、【實驗源代碼】
#include <stdio.h>
#include <stdlib.h>
#include <time.h>// 冒泡排序
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交換arr[j]和arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}// 快速排序
void quickSort(int arr[], int low, int high);// 快速排序中的分區操作
int partition(int arr[], int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;
}// 快速排序遞歸函數
void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}// 歸并排序中的合并操作
void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;int L[n1], R[n2];for (int i = 0; i < n1; i++) {L[i] = arr[l + i];}for (int j = 0; j < n2; j++) {R[j] = arr[m + 1 + j];}int i = 0, j = 0;int k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}
}// 歸并排序遞歸函數
void mergeSort(int arr[], int l, int r) {if (l < r) {int m = (l + r) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);merge(arr, l, m, r);}
}int main() {const int n = 10000;int nums[n];srand(time(NULL));for (int i = 0; i < n; i++) {nums[i] = rand();}int copy[n];for (int i = 0; i < n; i++) {copy[i] = nums[i];}clock_t startTime, endTime;double duration;startTime = clock();bubbleSort(copy, n);endTime = clock();duration = ((double) (endTime - startTime)) * 1000 / CLOCKS_PER_SEC;printf("冒泡排序 %.1f ms\n", duration);for (int i = 0; i < n; i++) {copy[i] = nums[i];}startTime = clock();mergeSort(copy, 0, n - 1);endTime = clock();duration = ((double) (endTime - startTime)) * 1000 / CLOCKS_PER_SEC;printf("歸并排序 %.1f ms\n", duration);for (int i = 0; i < n; i++) {copy[i] = nums[i];}startTime = clock();quickSort(copy, 0, n - 1);endTime = clock();duration = ((double) (endTime - startTime)) * 1000 / CLOCKS_PER_SEC;printf("快速排序 %.1f ms\n", duration);return 0;
}
四、實驗結果
奇了怪了
)