# 简介在计算机科学中，排序是处理数据时最常见的操作之一。C++作为一种广泛使用的编程语言，提供了多种内置的排序方法，同时也允许开发者自定义实现各种排序算法。本文将详细介绍几种常见的C++排序算法，包括其基本原理、实现方式以及各自的优缺点。# C++中的内置排序函数## std::sort
`std::sort` 是C++标准库中提供的一个非常高效的排序函数，它基于快速排序、堆排序和插入排序的混合算法，适用于大多数情况。### 使用示例
```cpp
#include
#include
#include int main() {std::vector vec = {3, 1, 4, 1, 5, 9};std::sort(vec.begin(), vec.end());for (auto &i : vec) {std::cout << i << " ";}return 0;
}
```### 性能
- 平均时间复杂度：O(n log n)
- 最坏情况时间复杂度：O(n log n)## std::stable_sort
`std::stable_sort` 提供了与 `std::sort` 类似的功能，但保证了稳定性（即相等元素的相对顺序不会改变）。### 使用示例
```cpp
#include
#include
#include struct Data {int value;int id;
};bool compare(const Data& a, const Data& b) {return a.value < b.value;
}int main() {std::vector data = {{3, 1}, {1, 2}, {4, 3}, {1, 4}, {5, 5}, {9, 6}};std::stable_sort(data.begin(), data.end(), compare);for (const auto &d : data) {std::cout << d.value << " ";}return 0;
}
```### 性能
- 平均时间复杂度：O(n log n)
- 最坏情况时间复杂度：O(n log n)# 常见的排序算法实现## 冒泡排序
冒泡排序是一种简单的排序算法，通过重复地遍历列表来比较相邻的元素并交换它们的位置。### 实现示例
```cpp
#include
#include void bubbleSort(std::vector& arr) {bool swapped;for (size_t i = 0; i < arr.size() - 1; ++i) {swapped = false;for (size_t j = 0; j < arr.size() - i - 1; ++j) {if (arr[j] > arr[j + 1]) {std::swap(arr[j], arr[j + 1]);swapped = true;}}if (!swapped) break;}
}int main() {std::vector vec = {64, 34, 25, 12, 22, 11, 90};bubbleSort(vec);for (auto &i : vec) {std::cout << i << " ";}return 0;
}
```### 性能
- 最好情况时间复杂度：O(n)
- 平均时间复杂度：O(n^2)
- 最坏情况时间复杂度：O(n^2)## 快速排序
快速排序是一种分治法策略的排序算法，通过选择一个基准元素，然后将数组分为两部分，使得一部分的所有元素都比另一部分的所有元素小。### 实现示例
```cpp
#include
#include int partition(std::vector& arr, int low, int 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]);return (i + 1);
}void quickSort(std::vector& 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() {std::vector vec = {10, 7, 8, 9, 1, 5};quickSort(vec, 0, vec.size() - 1);for (auto &i : vec) {std::cout << i << " ";}return 0;
}
```### 性能
- 平均时间复杂度：O(n log n)
- 最坏情况时间复杂度：O(n^2)## 归并排序
归并排序也是一种分治法策略的排序算法，通过将数组分成两半，分别对它们进行排序，然后再合并两个已排序的子数组。### 实现示例
```cpp
#include
#include void merge(std::vector& arr, int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;std::vector L(n1), R(n2);for (int i = 0; i < n1; ++i)L[i] = arr[l + i];for (int j = 0; j < n2; ++j)R[j] = arr[m + 1 + j];int i = 0;int j = 0;int 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);}
}int main() {std::vector vec = {12, 11, 13, 5, 6, 7};mergeSort(vec, 0, vec.size() - 1);for (auto &i : vec) {std::cout << i << " ";}return 0;
}
```### 性能
- 平均时间复杂度：O(n log n)
- 最坏情况时间复杂度：O(n log n)# 结论C++提供了丰富的排序工具，从标准库中的高效排序函数到开发者自定义的排序算法，每种方法都有其适用场景。对于不同的需求，开发者可以根据实际情况选择最适合的排序算法。
简介在计算机科学中，排序是处理数据时最常见的操作之一。C++作为一种广泛使用的编程语言，提供了多种内置的排序方法，同时也允许开发者自定义实现各种排序算法。本文将详细介绍几种常见的C++排序算法，包括其基本原理、实现方式以及各自的优缺点。
C++中的内置排序函数
std::sort
`std::sort` 是C++标准库中提供的一个非常高效的排序函数，它基于快速排序、堆排序和插入排序的混合算法，适用于大多数情况。
使用示例
```cpp
include
include
include int main() {std::vector vec = {3, 1, 4, 1, 5, 9};std::sort(vec.begin(), vec.end());for (auto &i : vec) {std::cout << i << " ";}return 0;
}
```
性能
- 平均时间复杂度：O(n log n)
- 最坏情况时间复杂度：O(n log n)
std::stable_sort
`std::stable_sort` 提供了与 `std::sort` 类似的功能，但保证了稳定性（即相等元素的相对顺序不会改变）。
使用示例
```cpp
include
include
include struct Data {int value;int id;
};bool compare(const Data& a, const Data& b) {return a.value < b.value;
}int main() {std::vector data = {{3, 1}, {1, 2}, {4, 3}, {1, 4}, {5, 5}, {9, 6}};std::stable_sort(data.begin(), data.end(), compare);for (const auto &d : data) {std::cout << d.value << " ";}return 0;
}
```
性能
- 平均时间复杂度：O(n log n)
- 最坏情况时间复杂度：O(n log n)
常见的排序算法实现
冒泡排序
冒泡排序是一种简单的排序算法，通过重复地遍历列表来比较相邻的元素并交换它们的位置。
实现示例
```cpp
include
include void bubbleSort(std::vector& arr) {bool swapped;for (size_t i = 0; i < arr.size() - 1; ++i) {swapped = false;for (size_t j = 0; j < arr.size() - i - 1; ++j) {if (arr[j] > arr[j + 1]) {std::swap(arr[j], arr[j + 1]);swapped = true;}}if (!swapped) break;}
}int main() {std::vector vec = {64, 34, 25, 12, 22, 11, 90};bubbleSort(vec);for (auto &i : vec) {std::cout << i << " ";}return 0;
}
```
性能
- 最好情况时间复杂度：O(n)
- 平均时间复杂度：O(n^2)
- 最坏情况时间复杂度：O(n^2)
快速排序
快速排序是一种分治法策略的排序算法，通过选择一个基准元素，然后将数组分为两部分，使得一部分的所有元素都比另一部分的所有元素小。
实现示例
```cpp
include
include int partition(std::vector& arr, int low, int 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]);return (i + 1);
}void quickSort(std::vector& 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() {std::vector vec = {10, 7, 8, 9, 1, 5};quickSort(vec, 0, vec.size() - 1);for (auto &i : vec) {std::cout << i << " ";}return 0;
}
```
性能
- 平均时间复杂度：O(n log n)
- 最坏情况时间复杂度：O(n^2)
归并排序
归并排序也是一种分治法策略的排序算法，通过将数组分成两半，分别对它们进行排序，然后再合并两个已排序的子数组。
实现示例
```cpp
include
include void merge(std::vector& arr, int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;std::vector L(n1), R(n2);for (int i = 0; i < n1; ++i)L[i] = arr[l + i];for (int j = 0; j < n2; ++j)R[j] = arr[m + 1 + j];int i = 0;int j = 0;int 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);}
}int main() {std::vector vec = {12, 11, 13, 5, 6, 7};mergeSort(vec, 0, vec.size() - 1);for (auto &i : vec) {std::cout << i << " ";}return 0;
}
```
性能
- 平均时间复杂度：O(n log n)
- 最坏情况时间复杂度：O(n log n)
结论C++提供了丰富的排序工具，从标准库中的高效排序函数到开发者自定义的排序算法，每种方法都有其适用场景。对于不同的需求，开发者可以根据实际情况选择最适合的排序算法。
