C++编译冒泡排序,快速排序和堆排序算法,并要求比较三个排序算法的运行速度
时间: 2023-07-18 21:32:45 浏览: 46
好的,我可以帮你编写C++代码来实现冒泡排序、快速排序和堆排序算法,并比较它们的运行速度。
首先,让我们看看冒泡排序的实现。冒泡排序是一种简单的排序算法,它通过不断交换相邻的元素来排序。以下是C++代码:
```c++
#include <iostream>
using namespace std;
void bubbleSort(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]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
int arr[] = { 5, 2, 6, 1, 3, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
return 0;
}
```
接下来是快速排序算法的实现。快速排序使用分治策略来排序,它将一个大问题分解成较小的子问题,然后解决这些子问题。以下是C++代码:
```c++
#include <iostream>
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 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);
}
}
int main() {
int arr[] = { 5, 2, 6, 1, 3, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
return 0;
}
```
最后是堆排序算法的实现。堆排序使用堆数据结构来排序,它将元素插入堆中,然后不断从堆中取出最大元素,直到堆为空。以下是C++代码:
```c++
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; --i) {
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; --i) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int arr[] = { 5, 2, 6, 1, 3, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
return 0;
}
```
现在我们来比较这三个排序算法的运行速度。我们可以使用C++的chrono库来计时。以下是比较运行速度的代码:
```c++
#include <iostream>
#include <chrono>
#include <random>
using namespace std;
void bubbleSort(int arr[], int n);
void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
void heapify(int arr[], int n, int i);
void heapSort(int arr[], int n);
int main() {
const int n = 10000;
int arr1[n], arr2[n], arr3[n];
// 生成随机数
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1, n);
for (int i = 0; i < n; ++i) {
int num = dis(gen);
arr1[i] = num;
arr2[i] = num;
arr3[i] = num;
}
// 测量冒泡排序的时间
auto start = chrono::high_resolution_clock::now();
bubbleSort(arr1, n);
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
cout << "Bubble sort: " << duration.count() << " microseconds" << endl;
// 测量快速排序的时间
start = chrono::high_resolution_clock::now();
quickSort(arr2, 0, n - 1);
end = chrono::high_resolution_clock::now();
duration = chrono::duration_cast<chrono::microseconds>(end - start);
cout << "Quick sort: " << duration.count() << " microseconds" << endl;
// 测量堆排序的时间
start = chrono::high_resolution_clock::now();
heapSort(arr3, n);
end = chrono::high_resolution_clock::now();
duration = chrono::duration_cast<chrono::microseconds>(end - start);
cout << "Heap sort: " << duration.count() << " microseconds" << endl;
return 0;
}
void bubbleSort(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]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
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);
}
}
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 heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; --i) {
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; --i) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
```
注意,这里我们使用了C++的random库来生成随机数。我们还使用了chrono库来计时。输出的时间以微秒为单位。
希望这可以帮助你比较这三个排序算法的运行速度。