生成c++代码(A数组中存储500个2000以内的随机整数,完成以下操作:对A数组中的元素进行直接插入排序,显示排序所用时间;对A数组中的元素进行希尔排序,显示排序所用时间;对A数组中的元素进行起泡排序,显示排序所用时间;对A数组中的元素进行快速排序,显示排序所用时间。)
时间: 2024-03-22 11:42:37 浏览: 51
C++实现希尔、快速、堆排序、归并排序算法
5星 · 资源好评率100%
好的,以下是您需要的 C++ 代码:
```c++
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
// 直接插入排序
void insert_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 希尔排序
void shell_sort(int arr[], int n) {
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
// 冒泡排序
void bubble_sort(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]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 快速排序
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 quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
int main() {
const int n = 500;
int arr[n];
srand(time(NULL));
for (int i = 0; i < n; i++) {
arr[i] = rand() % 2000;
}
// 直接插入排序
clock_t start = clock();
insert_sort(arr, n);
clock_t end = clock();
cout << "直接插入排序用时:" << (double)(end - start) / CLOCKS_PER_SEC << "秒\n";
// 希尔排序
start = clock();
shell_sort(arr, n);
end = clock();
cout << "希尔排序用时:" << (double)(end - start) / CLOCKS_PER_SEC << "秒\n";
// 冒泡排序
start = clock();
bubble_sort(arr, n);
end = clock();
cout << "冒泡排序用时:" << (double)(end - start) / CLOCKS_PER_SEC << "秒\n";
// 快速排序
start = clock();
quick_sort(arr, 0, n - 1);
end = clock();
cout << "快速排序用时:" << (double)(end - start) / CLOCKS_PER_SEC << "秒\n";
return 0;
}
```
该代码使用了 C++ 标准库中的 `iostream` 和 `ctime`,其中 `srand(time(NULL))` 用于生成随机数种子,以保证每次运行程序生成的随机数不同。代码中的四个排序算法分别为直接插入排序、希尔排序、冒泡排序和快速排序,其中快速排序使用了递归实现。
在 `main` 函数中,我们先生成了一个长度为 500 的随机整数数组,然后依次对其进行四种排序算法,并使用 `clock` 函数计算排序所用的时间。最后将排序所用的时间输出到控制台中。
阅读全文