c++以int作为待排序数据类型,从下列排序算法中选择2-3种实现: 直接插入排序(或折半插入排序) 冒泡排序 简单选择排序 堆排序 快速排序 希尔排序 统计不同排序算法的运行时间,对比性能: 同一次实验,三种方法的输入数据应该一样 同样数据同样方法的实验,需要重复多次统计平均时间 将结果绘制成折线图(可利用Excel) 观察同一算法的执行时间随数据规模的变化情况 分析不同算法的性能差异。把代码给我
时间: 2024-03-13 07:42:55 浏览: 14
好的,以下是选择的三种排序算法的代码实现。需要注意的是,为了方便统计运行时间,我将每个算法封装成了一个函数,并且在每个函数中都加入了计时功能。
1. 直接插入排序
```c++
#include <iostream>
#include <ctime>
using namespace std;
void insert_sort(int arr[], int n) {
clock_t start_time, end_time;
start_time = clock();
for (int i = 1; i < n; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
end_time = clock();
cout << "Insertion Sort: " << double(end_time - start_time) / CLOCKS_PER_SEC << "s" << endl;
}
```
2. 快速排序
```c++
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
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++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quick_sort(int arr[], int low, int high) {
clock_t start_time, end_time;
start_time = clock();
if (low < high) {
int pivot = partition(arr, low, high);
quick_sort(arr, low, pivot - 1);
quick_sort(arr, pivot + 1, high);
}
end_time = clock();
cout << "Quick Sort: " << double(end_time - start_time) / CLOCKS_PER_SEC << "s" << endl;
}
```
3. 希尔排序
```c++
#include <iostream>
#include <ctime>
using namespace std;
void shell_sort(int arr[], int n) {
clock_t start_time, end_time;
start_time = clock();
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
end_time = clock();
cout << "Shell Sort: " << double(end_time - start_time) / CLOCKS_PER_SEC << "s" << endl;
}
```
以上是三个排序算法的代码实现,您可以根据需要进行调整。在主函数中,您可以按照以下方式进行调用:
```c++
int main() {
int arr[] = {5, 2, 8, 3, 9, 4, 1, 7, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insert_sort(arr, n);
quick_sort(arr, 0, n - 1);
shell_sort(arr, n);
return 0;
}
```
这个程序将会输出每个排序算法的运行时间。您可以根据需要修改输入数据的大小和内容,并将结果导出到 Excel 中进行绘制折线图和性能分析。