用C语言或C++写1.定义待排序表的长度为n。 2.初始化随机数发生器,产生n个随机数构成的顺序表。 3.创建输出排序表函数,取得系统时间函数,直接插入排序函数,冒泡排序函数,快速排序函数,直接选择排序函数,筛选函数,对排序函数,归并排序函数。 4.主程序调用各个排序函数,输出各排序算法对长度为n的顺序表进行排序所耗费的时间。
时间: 2024-02-06 16:11:09 浏览: 74
非常感谢您的问题,以下是一个用C++实现的基本排序算法程序,满足您的要求:
```c++
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <chrono>
#include <algorithm>
using namespace std;
using namespace std::chrono;
// 定义待排序表的长度为n
const int n = 10;
// 产生n个随机数构成的顺序表
void generate_random_array(int a[], int n) {
srand((unsigned)time(NULL));
for (int i = 0; i < n; i++) {
a[i] = rand() % 100;
}
}
// 输出排序表
void print_array(int a[], int n) {
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
}
// 直接插入排序
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}
// 冒泡排序
void bubble_sort(int a[], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n-i-1; j++) {
if (a[j] > a[j+1]) {
swap(a[j], a[j+1]);
}
}
}
}
// 快速排序
void quick_sort(int a[], int left, int right) {
if (left >= right) {
return;
}
int i = left, j = right;
int pivot = a[left];
while (i < j) {
while (i < j && a[j] >= pivot) {
j--;
}
a[i] = a[j];
while (i < j && a[i] <= pivot) {
i++;
}
a[j] = a[i];
}
a[i] = pivot;
quick_sort(a, left, i-1);
quick_sort(a, i+1, right);
}
// 直接选择排序
void selection_sort(int a[], int n) {
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (a[j] < a[min_idx]) {
min_idx = j;
}
}
swap(a[i], a[min_idx]);
}
}
// 堆排序
void heap_sort(int a[], int n) {
make_heap(a, a+n);
sort_heap(a, a+n);
}
// 归并排序
void merge(int a[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) {
L[i] = a[left+i];
}
for (int i = 0; i < n2; i++) {
R[i] = a[mid+i+1];
}
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
a[k++] = L[i++];
} else {
a[k++] = R[j++];
}
}
while (i < n1) {
a[k++] = L[i++];
}
while (j < n2) {
a[k++] = R[j++];
}
}
void merge_sort(int a[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(a, left, mid);
merge_sort(a, mid+1, right);
merge(a, left, mid, right);
}
}
int main() {
int a[n];
// 产生随机数构成的顺序表
generate_random_array(a, n);
// 输出排序前的顺序表
cout << "排序前的顺序表: ";
print_array(a, n);
// 计算直接插入排序耗费的时间
auto start_time = high_resolution_clock::now();
insertion_sort(a, n);
auto end_time = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(end_time - start_time);
cout << "直接插入排序耗费的时间: " << duration.count() << "us" << endl;
// 输出排序后的顺序表
cout << "直接插入排序后的顺序表: ";
print_array(a, n);
// 产生随机数构成的顺序表
generate_random_array(a, n);
// 输出排序前的顺序表
cout << "排序前的顺序表: ";
print_array(a, n);
// 计算冒泡排序耗费的时间
start_time = high_resolution_clock::now();
bubble_sort(a, n);
end_time = high_resolution_clock::now();
duration = duration_cast<microseconds>(end_time - start_time);
cout << "冒泡排序耗费的时间: " << duration.count() << "us" << endl;
// 输出排序后的顺序表
cout << "冒泡排序后的顺序表: ";
print_array(a, n);
// 产生随机数构成的顺序表
generate_random_array(a, n);
// 输出排序前的顺序表
cout << "排序前的顺序表: ";
print_array(a, n);
// 计算快速排序耗费的时间
start_time = high_resolution_clock::now();
quick_sort(a, 0, n-1);
end_time = high_resolution_clock::now();
duration = duration_cast<microseconds>(end_time - start_time);
cout << "快速排序耗费的时间: " << duration.count() << "us" << endl;
// 输出排序后的顺序表
cout << "快速排序后的顺序表: ";
print_array(a, n);
// 产生随机数构成的顺序表
generate_random_array(a, n);
// 输出排序前的顺序表
cout << "排序前的顺序表: ";
print_array(a, n);
// 计算直接选择排序耗费的时间
start_time = high_resolution_clock::now();
selection_sort(a, n);
end_time = high_resolution_clock::now();
duration = duration_cast<microseconds>(end_time - start_time);
cout << "直接选择排序耗费的时间: " << duration.count() << "us" << endl;
// 输出排序后的顺序表
cout << "直接选择排序后的顺序表: ";
print_array(a, n);
// 产生随机数构成的顺序表
generate_random_array(a, n);
// 输出排序前的顺序表
cout << "排序前的顺序表: ";
print_array(a, n);
// 计算堆排序耗费的时间
start_time = high_resolution_clock::now();
heap_sort(a, n);
end_time = high_resolution_clock::now();
duration = duration_cast<microseconds>(end_time - start_time);
cout << "堆排序耗费的时间: " << duration.count() << "us" << endl;
// 输出排序后的顺序表
cout << "堆排序后的顺序表: ";
print_array(a, n);
// 产生随机数构成的顺序表
generate_random_array(a, n);
// 输出排序前的顺序表
cout << "排序前的顺序表: ";
print_array(a, n);
// 计算归并排序耗费的时间
start_time = high_resolution_clock::now();
merge_sort(a, 0, n-1);
end_time = high_resolution_clock::now();
duration = duration_cast<microseconds>(end_time - start_time);
cout << "归并排序耗费的时间: " << duration.count() << "us" << endl;
// 输出排序后的顺序表
cout << "归并排序后的顺序表: ";
print_array(a, n);
return 0;
}
```
以上是一个基本的排序算法实现过程,您可以根据需要对其进行修改和完善。同时,请注意在实际使用中需要考虑算法的时间复杂度和空间复杂度等因素,选择合适的排序算法来解决实际问题。
阅读全文