# C++排序方法有哪几种## 简介
在C++编程中，排序是处理数据时最常见的需求之一。高效的排序算法能够显著提升程序的运行效率和性能。C++标准库提供了多种排序方法，同时开发者也可以通过自定义函数实现特定需求的排序。本文将详细介绍C++中的主要排序方法及其应用场景。---## 1. 标准库提供的排序方法### 1.1 `std::sort`
`std::sort` 是C++标准库提供的一个通用排序函数，位于头文件 `` 中。它基于快速排序、堆排序和插入排序的混合实现，适用于大多数场景。#### 使用示例：
```cpp
#include
#include
#include int main() {std::vector nums = {5, 2, 9, 1, 7};std::sort(nums.begin(), nums.end());for (auto num : nums) {std::cout << num << " ";}return 0;
}
```#### 特点：
- 时间复杂度：平均 O(n log n)，最坏情况为 O(n²)。
- 空间复杂度：O(1)（原地排序）。
- 灵活可定制：可以通过第三个参数指定自定义比较函数。---### 1.2 `std::stable_sort`
`std::stable_sort` 是另一种标准库排序函数，与 `std::sort` 类似，但它保证了排序后相同元素的相对顺序不变。#### 使用示例：
```cpp
#include
#include
#include struct Student {int age;std::string name;
};bool compareByAge(const Student& a, const Student& b) {return a.age < b.age;
}int main() {std::vector students = {{20, "Tom"}, {19, "Jerry"}, {20, "Alice"}};std::stable_sort(students.begin(), students.end(), compareByAge);for (const auto& student : students) {std::cout << student.age << " " << student.name << "\n";}return 0;
}
```#### 特点：
- 时间复杂度：平均 O(n log n)，最坏情况为 O(n²)。
- 空间复杂度：通常需要额外的空间。---## 2. 手动实现的排序方法### 2.1 冒泡排序
冒泡排序是一种简单的排序算法，通过多次交换相邻元素来完成排序。#### 使用示例：
```cpp
#include
#include void bubbleSort(std::vector& arr) {int n = arr.size();for (int i = 0; i < n - 1; ++i) {for (int j = 0; j < n - i - 1; ++j) {if (arr[j] > arr[j + 1]) {std::swap(arr[j], arr[j + 1]);}}}
}int main() {std::vector nums = {64, 34, 25, 12, 22, 11, 90};bubbleSort(nums);for (auto num : nums) {std::cout << num << " ";}return 0;
}
```#### 特点：
- 时间复杂度：O(n²)。
- 空间复杂度：O(1)。---### 2.2 插入排序
插入排序通过逐步构建有序序列，每次将一个新元素插入到已排序部分的适当位置。#### 使用示例：
```cpp
#include
#include void insertionSort(std::vector& arr) {int n = arr.size();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;}
}int main() {std::vector nums = {12, 11, 13, 5, 6};insertionSort(nums);for (auto num : nums) {std::cout << num << " ";}return 0;
}
```#### 特点：
- 时间复杂度：平均 O(n²)，最好情况为 O(n)。
- 空间复杂度：O(1)。---## 3. 高效的排序方法### 3.1 快速排序
快速排序是一种分而治之的算法，通过选择基准值并分区来实现排序。#### 使用示例：
```cpp
#include
#include 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);}
}int main() {std::vector nums = {10, 7, 8, 9, 1, 5};quickSort(nums, 0, nums.size() - 1);for (auto num : nums) {std::cout << num << " ";}return 0;
}
```#### 特点：
- 时间复杂度：平均 O(n log n)，最坏情况为 O(n²)。---### 3.2 堆排序
堆排序利用二叉堆结构进行排序，时间复杂度稳定为 O(n log n)。#### 使用示例：
```cpp
#include
#include
#include void heapify(std::vector& arr, int n, int i) {int largest = i;int left = 2
i + 1;int right = 2
i + 2;if (left < n && arr[left] > arr[largest])largest = left;if (right < n && arr[right] > arr[largest])largest = right;if (largest != i) {std::swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(std::vector& arr) {int n = arr.size();// Build heap (rearrange array)for (int i = n / 2 - 1; i >= 0; --i)heapify(arr, n, i);// One by one extract an element from heapfor (int i = n - 1; i > 0; --i) {std::swap(arr[0], arr[i]);heapify(arr, i, 0);}
}int main() {std::vector nums = {12, 11, 13, 5, 6, 7};heapSort(nums);for (auto num : nums) {std::cout << num << " ";}return 0;
}
```#### 特点：
- 时间复杂度：O(n log n)。
- 空间复杂度：O(1)。---## 总结
C++提供了丰富的排序方法，从标准库的高效实现到手动编写的简单算法，开发者可以根据具体需求选择合适的排序方式。无论是在性能要求较高的场景下使用 `std::sort` 和 `std::stable_sort`，还是在学习阶段手动实现基础排序算法，都对掌握排序知识至关重要。
C++排序方法有哪几种
简介
在C++编程中，排序是处理数据时最常见的需求之一。高效的排序算法能够显著提升程序的运行效率和性能。C++标准库提供了多种排序方法，同时开发者也可以通过自定义函数实现特定需求的排序。本文将详细介绍C++中的主要排序方法及其应用场景。---
1. 标准库提供的排序方法
1.1 `std::sort`
`std::sort` 是C++标准库提供的一个通用排序函数，位于头文件 `` 中。它基于快速排序、堆排序和插入排序的混合实现，适用于大多数场景。
使用示例：
```cpp
include
include
include int main() {std::vector nums = {5, 2, 9, 1, 7};std::sort(nums.begin(), nums.end());for (auto num : nums) {std::cout << num << " ";}return 0;
}
```
特点：
- 时间复杂度：平均 O(n log n)，最坏情况为 O(n²)。
- 空间复杂度：O(1)（原地排序）。
- 灵活可定制：可以通过第三个参数指定自定义比较函数。---
1.2 `std::stable_sort`
`std::stable_sort` 是另一种标准库排序函数，与 `std::sort` 类似，但它保证了排序后相同元素的相对顺序不变。
使用示例：
```cpp
include
include
include struct Student {int age;std::string name;
};bool compareByAge(const Student& a, const Student& b) {return a.age < b.age;
}int main() {std::vector students = {{20, "Tom"}, {19, "Jerry"}, {20, "Alice"}};std::stable_sort(students.begin(), students.end(), compareByAge);for (const auto& student : students) {std::cout << student.age << " " << student.name << "\n";}return 0;
}
```
特点：
- 时间复杂度：平均 O(n log n)，最坏情况为 O(n²)。
- 空间复杂度：通常需要额外的空间。---
2. 手动实现的排序方法
2.1 冒泡排序
冒泡排序是一种简单的排序算法，通过多次交换相邻元素来完成排序。
使用示例：
```cpp
include
include void bubbleSort(std::vector& arr) {int n = arr.size();for (int i = 0; i < n - 1; ++i) {for (int j = 0; j < n - i - 1; ++j) {if (arr[j] > arr[j + 1]) {std::swap(arr[j], arr[j + 1]);}}}
}int main() {std::vector nums = {64, 34, 25, 12, 22, 11, 90};bubbleSort(nums);for (auto num : nums) {std::cout << num << " ";}return 0;
}
```
特点：
- 时间复杂度：O(n²)。
- 空间复杂度：O(1)。---
2.2 插入排序
插入排序通过逐步构建有序序列，每次将一个新元素插入到已排序部分的适当位置。
使用示例：
```cpp
include
include void insertionSort(std::vector& arr) {int n = arr.size();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;}
}int main() {std::vector nums = {12, 11, 13, 5, 6};insertionSort(nums);for (auto num : nums) {std::cout << num << " ";}return 0;
}
```
特点：
- 时间复杂度：平均 O(n²)，最好情况为 O(n)。
- 空间复杂度：O(1)。---
3. 高效的排序方法
3.1 快速排序
快速排序是一种分而治之的算法，通过选择基准值并分区来实现排序。
使用示例：
```cpp
include
include 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);}
}int main() {std::vector nums = {10, 7, 8, 9, 1, 5};quickSort(nums, 0, nums.size() - 1);for (auto num : nums) {std::cout << num << " ";}return 0;
}
```
特点：
- 时间复杂度：平均 O(n log n)，最坏情况为 O(n²)。---
3.2 堆排序
堆排序利用二叉堆结构进行排序，时间复杂度稳定为 O(n log n)。
使用示例：
```cpp
include
include
include void heapify(std::vector& arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest])largest = left;if (right < n && arr[right] > arr[largest])largest = right;if (largest != i) {std::swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(std::vector& arr) {int n = arr.size();// Build heap (rearrange array)for (int i = n / 2 - 1; i >= 0; --i)heapify(arr, n, i);// One by one extract an element from heapfor (int i = n - 1; i > 0; --i) {std::swap(arr[0], arr[i]);heapify(arr, i, 0);}
}int main() {std::vector nums = {12, 11, 13, 5, 6, 7};heapSort(nums);for (auto num : nums) {std::cout << num << " ";}return 0;
}
```
特点：
- 时间复杂度：O(n log n)。
- 空间复杂度：O(1)。---
总结
C++提供了丰富的排序方法，从标准库的高效实现到手动编写的简单算法，开发者可以根据具体需求选择合适的排序方式。无论是在性能要求较高的场景下使用 `std::sort` 和 `std::stable_sort`，还是在学习阶段手动实现基础排序算法，都对掌握排序知识至关重要。
