编写C++代码随机产生500个1~2000之间的整数并输出,完成以下操作:对给定整数进行直接插入排序,显示排序所用时间;对给定整数进行希尔排序,显示排序所用时间; 对给定整数进行起泡排序,显示排序所用时间;对给定整数进行快速排序,显示排序所用时间。
时间: 2023-12-20 20:07:04 浏览: 66
利用随机函数产生30000个随机整数进行排序,并统计每一种排序上机所花费的时间
5星 · 资源好评率100%
以下是C++代码实现:
```cpp
#include <iostream>
#include <ctime>
using namespace std;
// 直接插入排序
void insertionSort(int arr[], int len) {
int i, j, temp;
clock_t start_time = clock(); // 记录排序开始时间
for (i = 1; i < len; i++) {
temp = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
clock_t end_time = clock(); // 记录排序结束时间
cout << "直接插入排序所用时间:" << double(end_time - start_time) / CLOCKS_PER_SEC << "秒" << endl;
}
// 希尔排序
void shellSort(int arr[], int len) {
int gap, i, j, temp;
clock_t start_time = clock(); // 记录排序开始时间
for (gap = len / 2; gap > 0; gap /= 2) {
for (i = gap; i < len; i++) {
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
clock_t end_time = clock(); // 记录排序结束时间
cout << "希尔排序所用时间:" << double(end_time - start_time) / CLOCKS_PER_SEC << "秒" << endl;
}
// 起泡排序
void bubbleSort(int arr[], int len) {
int i, j, temp;
clock_t start_time = clock(); // 记录排序开始时间
for (i = 0; i < len - 1; i++) {
for (j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
clock_t end_time = clock(); // 记录排序结束时间
cout << "起泡排序所用时间:" << double(end_time - start_time) / CLOCKS_PER_SEC << "秒" << endl;
}
// 快速排序
void quickSort(int arr[], int left, int right) {
if (left >= right) return;
int i = left, j = right, pivot = arr[left];
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
if (i < j) arr[i++] = arr[j];
while (i < j && arr[i] < pivot) i++;
if (i < j) arr[j--] = arr[i];
}
arr[i] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
int main() {
const int N = 500;
int arr[N];
srand((unsigned)time(NULL)); // 随机数种子
for (int i = 0; i < N; i++) {
arr[i] = rand() % 2000 + 1; // 产生1~2000之间的随机整数
}
cout << "排序前的数组:" << endl;
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
if ((i + 1) % 10 == 0) cout << endl;
}
cout << endl;
insertionSort(arr, N); // 直接插入排序
for (int i = 0; i < N; i++) {
arr[i] = rand() % 2000 + 1;
}
shellSort(arr, N); // 希尔排序
for (int i = 0; i < N; i++) {
arr[i] = rand() % 2000 + 1;
}
bubbleSort(arr, N); // 起泡排序
for (int i = 0; i < N; i++) {
arr[i] = rand() % 2000 + 1;
}
clock_t start_time = clock(); // 记录排序开始时间
quickSort(arr, 0, N - 1); // 快速排序
clock_t end_time = clock(); // 记录排序结束时间
cout << "快速排序所用时间:" << double(end_time - start_time) / CLOCKS_PER_SEC << "秒" << endl;
cout << "排序后的数组:" << endl;
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
if ((i + 1) % 10 == 0) cout << endl;
}
cout << endl;
return 0;
}
```
这段代码中,我们首先使用 `srand()` 函数设置随机数种子,然后使用 `rand()` 函数产生随机整数。接着,我们分别调用四个排序函数,并在函数内部记录排序开始和结束的时间,在排序结束后输出排序所用时间。最后,我们输出排序后的数组。
阅读全文