C++ 语言排序算法性能对比示例
在计算机科学中，排序算法是基础且重要的算法之一。C++ 作为一种高性能的编程语言，提供了多种排序算法的实现。本文将围绕 C++ 语言中的几种常见排序算法，通过代码示例进行性能对比，以帮助读者了解不同排序算法的特点和适用场景。
常见排序算法
在 C++ 中，常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。以下是这些算法的基本介绍：
1. 冒泡排序（Bubble Sort）：通过比较相邻元素并交换位置，逐步将最大（或最小）元素“冒泡”到序列的一端。
2. 选择排序（Selection Sort）：每次从剩余未排序的元素中找到最小（或最大）元素，放到序列的起始位置。
3. 插入排序（Insertion Sort）：将未排序的元素插入到已排序序列中的合适位置。
4. 快速排序（Quick Sort）：通过一个基准元素将序列分为两部分，然后递归地对这两部分进行排序。
5. 归并排序（Merge Sort）：将序列分为两半，递归地对这两半进行排序，最后合并排序好的两半。
6. 堆排序（Heap Sort）：利用堆这种数据结构，通过调整堆来达到排序的目的。
性能对比示例
为了对比这些排序算法的性能，我们将使用 C++ 编写一个简单的测试程序。该程序将生成一个随机数组，然后对数组进行排序，并记录每种算法的执行时间。
cpp
include
include
include
include
// 冒泡排序
void bubbleSort(std::vector& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
// 选择排序
void selectionSort(std::vector& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
std::swap(arr[i], arr[min_idx]);
}
}
// 插入排序
void insertionSort(std::vector& arr) {
int n = arr.size();
for (int i = 1; i = 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// 快速排序
void quickSort(std::vector& arr, int low, int high) {
if (low < high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
int pi = i + 1;
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 归并排序
void merge(std::vector& arr, int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
std::vector L(n1), R(n2);
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(std::vector& arr, int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
// 堆排序
void heapify(std::vector& arr, int n, int i) {
int largest = i;
int l = 2 i + 1;
int r = 2 i + 2;
if (l arr[largest])
largest = l;
if (r arr[largest])
largest = r;
if (largest != i) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(std::vector& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
// 测试排序算法性能
void testSortAlgorithm(std::vector& arr, void (sortFunc)(std::vector&)) {
std::vector copy = arr;
auto start = std::chrono::high_resolution_clock::now();
sortFunc(copy);
auto stop = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast(stop - start);
std::cout << "Time taken by function " << sortFunc << " is " << duration.count() << " microseconds" << std::endl;
}
int main() {
std::vector arr = {64, 34, 25, 12, 22, 11, 90};
std::cout << "Original array: ";
for (int i : arr) {
std::cout << i << " ";
}
std::cout << std::endl;
testSortAlgorithm(arr, bubbleSort);
testSortAlgorithm(arr, selectionSort);
testSortAlgorithm(arr, insertionSort);
testSortAlgorithm(arr, quickSort);
testSortAlgorithm(arr, mergeSort);
testSortAlgorithm(arr, heapSort);
return 0;
}
性能分析
运行上述程序，我们可以得到不同排序算法的执行时间。以下是对这些结果的简要分析：
- 冒泡排序：时间复杂度为 O(n^2)，在数据量较大时性能较差。
- 选择排序：时间复杂度同样为 O(n^2)，性能与冒泡排序相似。
- 插入排序：时间复杂度为 O(n^2)，但在部分情况下（如部分已排序的数组）性能较好。
- 快速排序：平均时间复杂度为 O(n log n)，在大多数情况下性能优于其他 O(n^2) 算法。
- 归并排序：时间复杂度始终为 O(n log n)，但需要额外的内存空间。
- 堆排序：时间复杂度为 O(n log n)，且空间复杂度为 O(1)，适用于内存受限的情况。
结论
通过对 C++ 中几种常见排序算法的性能对比，我们可以得出以下结论：
- 对于小规模数据，插入排序和冒泡排序可能更合适。
- 对于大规模数据，快速排序、归并排序和堆排序是更好的选择，因为它们的时间复杂度较低。
- 选择排序和冒泡排序在数据量较大时性能较差，不推荐使用。
在实际应用中，应根据具体需求和场景选择合适的排序算法。
Comments NOTHING