1.随机产生500个1~2000之间的整数并输出,完成以下操作: (1)对给定整数进行直接插入排序,显示排序所用时间; (2)对给定整数进行希尔排序,显示排序所用时间; (3)对给定整数进行起泡排序,显示排序所用时间; (4)对给定整数进行快速排序,显示排序所用时间。 部分参考代码如下: #include<ctime> //使用函数库ctime …… int main() { clock_t start,finish; //定义查找开始时间和结束时间变量 …… start=clock(); //记录查找算法的开始时间 查找算法 finish=clock(); //记录查找算法的结束时间 …… }
时间: 2024-02-06 11:04:31 浏览: 28
以下是完整的代码实现:
```c++
#include <iostream>
#include <ctime>
using namespace std;
// 直接插入排序
void insertSort(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 shellSort(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 bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool flag = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
flag = true;
}
}
if (!flag) {
break;
}
}
}
// 快速排序
int partition(int arr[], int low, int high) {
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
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);
}
}
// 随机生成n个1~2000之间的整数
void generateRandomArray(int arr[], int n) {
srand(time(NULL));
for (int i = 0; i < n; i++) {
arr[i] = rand() % 2000 + 1;
}
}
// 输出数组
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
const int n = 500;
int arr[n];
generateRandomArray(arr, n);
// 直接插入排序
int arr1[n];
copy(arr, arr + n, arr1);
clock_t start1 = clock();
insertSort(arr1, n);
clock_t finish1 = clock();
cout << "直接插入排序所用时间:" << (double)(finish1 - start1) / CLOCKS_PER_SEC << "秒" << endl;
// 希尔排序
int arr2[n];
copy(arr, arr + n, arr2);
clock_t start2 = clock();
shellSort(arr2, n);
clock_t finish2 = clock();
cout << "希尔排序所用时间:" << (double)(finish2 - start2) / CLOCKS_PER_SEC << "秒" << endl;
// 冒泡排序
int arr3[n];
copy(arr, arr + n, arr3);
clock_t start3 = clock();
bubbleSort(arr3, n);
clock_t finish3 = clock();
cout << "冒泡排序所用时间:" << (double)(finish3 - start3) / CLOCKS_PER_SEC << "秒" << endl;
// 快速排序
int arr4[n];
copy(arr, arr + n, arr4);
clock_t start4 = clock();
quickSort(arr4, 0, n - 1);
clock_t finish4 = clock();
cout << "快速排序所用时间:" << (double)(finish4 - start4) / CLOCKS_PER_SEC << "秒" << endl;
return 0;
}
```
其中,通过 `generateRandomArray` 函数生成随机数组,通过 `copy` 函数将数组复制到不同的排序算法中,然后对每种排序算法计时并输出所用时间。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)