第2章：排序与顺序统计量
2.1 排序问题
排序的定义：
- 排序是将一组数据按特定顺序排列，通常是从小到大或从大到小。
- 排序在许多应用中是基础操作，如数据库查询、数据分析、图形学等。
排序算法的设计目标：
时间复杂度：对大规模数据的排序效率。
空间复杂度：算法所需的额外内存。
稳定性：如果两个元素相等，它们在排序后的相对顺序是否保持不变。
2.2 比较排序算法
比较排序的基本思想：
- 排序过程中通过比较元素之间的大小关系来决定元素的相对位置。
- 经典的比较排序算法有：插入排序、归并排序、快速排序、堆排序等。
时间复杂度的下界：
- 在最坏情况下，比较排序的时间复杂度下界为O(n log n)，即任何基于比较的排序算法不能比O(n log n)更快。
- 该下界是通过决策树分析得出的。
2.3 插入排序
算法描述：
- 插入排序通过将每个元素插入到已排序部分的合适位置，逐步构造出最终的有序序列。
- 插入排序是一种简单的排序算法，尤其适用于数据量小或基本有序的情况。
时间复杂度分析：
- 最坏情况下：O(n²)，当输入数据完全逆序时，插入排序需要进行n(n-1)/2次比较。
- 最好情况下：O(n)，当输入数据已经有序时，只需遍历一次列表。
算法稳定性：
- 插入排序是稳定的，因为相等的元素在排序后相对位置保持不变。
空间复杂度：
- O(1)，插入排序只需要常数级的额外空间。
2.4 归并排序
算法描述：
- 归并排序采用分治法的策略，将一个大的问题分解成较小的子问题，递归地排序子问题，并合并结果。
- 归并排序的关键在于合并过程，通过合并两个已排序的子序列，得到一个有序序列。
时间复杂度分析：
- 最坏情况：O(n log n)，归并排序的时间复杂度始终是O(n log n)，无论输入数据如何。
空间复杂度：
- O(n)，归并排序需要额外的空间来存储临时的合并结果。
算法稳定性：
- 归并排序是稳定的，因为在合并时，相等的元素保持其相对顺序。
2.5 快速排序
算法描述：
- 快速排序是一种分治算法，选择一个“基准”元素，通过一轮划分将数组分为两部分，然后递归地对这两部分排序。
- 快速排序的关键在于如何选择基准元素以及如何划分。
时间复杂度分析：
- 最坏情况：O(n²)，当每次选择的基准元素是最小或最大元素时，分割不均衡，导致递归深度过深。
- 最好情况：O(n log n)，当每次划分尽可能平衡时，快速排序的时间复杂度为O(n log n)。
- 平均情况：O(n log n)，由于随机化和均衡分割的可能性，平均情况为O(n log n)。
算法稳定性：
- 快速排序通常不是稳定的，除非做特别的修改。
空间复杂度：
- O(log n)，快速排序是一个原地排序算法，只需要常数级的额外空间来保存递归栈。
2.6 堆排序
算法描述：
- 堆排序通过将待排序的元素构建成一个堆数据结构（通常是二叉堆），然后逐个从堆中取出最大（或最小）元素来形成有序序列。
- 堆排序可以视为一种选择排序，通过堆来高效地找到最大或最小元素。
时间复杂度分析：
- 最坏情况：O(n log n)，无论输入数据如何，堆排序的时间复杂度始终为O(n log n)。
空间复杂度：
- O(1)，堆排序是一个原地排序算法，不需要额外的空间。
算法稳定性：
- 堆排序不是稳定的，因为堆的结构可能打乱相等元素的顺序。
2.7 计数排序、基数排序和桶排序
计数排序：
- 计数排序是非比较排序算法，适用于已知元素范围较小的情况。它通过统计每个元素出现的次数，并根据计数结果进行排序。
- 时间复杂度为O(n+k)，其中n是数据的元素个数，k是元素值的范围。
基数排序：
- 基数排序是通过多次按位进行排序的方式（通常是从最低位到最高位），适用于整数或字符串类型的数据。
- 时间复杂度为O(nk)，其中n是元素个数，k是数字的位数。
桶排序：
- 桶排序是将元素分布到多个桶中，每个桶内部再单独排序，适用于数据均匀分布的情况。
- 时间复杂度为O(n+k)，其中n是元素个数，k是桶的数量。
2.8 顺序统计量
定义：
-
顺序统计量是指在一个数组中，按从小到大的顺序排列，特定位置的元素。例如，第k小的元素。 算法：
-
通过选择算法（如快速选择算法），可以在未完全排序的情况下找到第k小的元素。
- 快速选择算法的时间复杂度为O(n)，比完全排序（如归并排序或堆排序）要高效。
2.9 小结
- 本章详细介绍了常见的排序算法，包括插入排序、归并排序、快速排序和堆排序等。
- 比较排序的下界为O(n log n)，而非比较排序（如计数排序、基数排序、桶排序）在特定条件下可以做到更快。
- 排序算法的选择依赖于数据的特性（如数据大小、是否基本有序、是否需要稳定性等）。
下面是几种常见排序算法的 C++ 实现，包括插入排序、归并排序、快速排序、堆排序以及计数排序、基数排序和桶排序。每个算法都附有注释，帮助理解它们的工作原理。
1. 插入排序 (Insertion Sort)
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
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() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
insertionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
2. 归并排序 (Merge Sort)
#include <iostream>
using namespace std;
void merge(int arr[], 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] = arr[left + i];
for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
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(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // 对左半部分进行归并排序
mergeSort(arr, mid + 1, right); // 对右半部分进行归并排序
merge(arr, left, mid, right); // 合并两个已排序的部分
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
mergeSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
3. 快速排序 (Quick Sort)
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为枢纽
int i = low - 1; // i 是小于 pivot 的元素的分界
for (int j = low; j < high; ++j) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]); // 交换元素
}
}
swap(arr[i + 1], arr[high]); // 将 pivot 放到正确的位置
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[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
4. 堆排序 (Heap Sort)
#include <iostream>
using namespace std;
void heapify(int 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) {
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 >= 1; --i) {
swap(arr[0], arr[i]); // 交换堆顶与当前最后一个元素
heapify(arr, i, 0); // 重新调整堆
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
heapSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
5. 计数排序 (Counting Sort)
#include <iostream>
#include <vector>
using namespace std;
void countingSort(int arr[], int n, int range) {
vector<int> count(range, 0); // 创建计数数组
vector<int> output(n);
// 统计每个元素的出现次数
for (int i = 0; i < n; ++i) {
count[arr[i]]++;
}
// 计算出每个元素的最终位置
for (int i = 1; i < range; ++i) {
count[i] += count[i - 1];
}
// 将元素放到正确的位置
for (int i = n - 1; i >= 0; --i) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// 将排序后的数组拷贝回原数组
for (int i = 0; i < n; ++i) {
arr[i] = output[i];
}
}
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int range = 10; // 假设元素值范围为 0-9
cout << "Original array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
countingSort(arr, n, range);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
排序的稳定性问题
排序的稳定性是指：在排序过程中，如果两个元素相等，排序算法是否会保持它们在排序前的相对顺序。也就是说，如果一个排序算法是稳定的，那么对于两个值相等的元素，它们在排序后的相对顺序应该和原来保持一致。
为什么稳定性很重要？
稳定性对于某些问题来说非常重要，尤其是在多次排序的情况下。例如：
- 多次排序：如果你对一个数据集先按照某个属性排序，再按照另一个属性排序，稳定的排序算法能确保第一次排序时相等元素的顺序不会因为第二次排序而改变。
- 复杂数据结构排序：如果你对一个复杂的数据结构（例如结构体数组）进行排序，可能希望在排序某个字段时，保留其他字段的排序顺序。此时稳定排序非常重要。
常见排序算法的稳定性
| 排序算法 | 稳定性 | 说明 |
|---|---|---|
| 插入排序 | 稳定 | 插入排序在处理相等元素时会保持它们原来的相对顺序，因此它是稳定的。 |
| 归并排序 | 稳定 | 归并排序在合并两个子序列时，如果遇到相等的元素，原序列中的相对顺序不会改变，因此它是稳定的。 |
| 快速排序 | 不稳定 | 快速排序通常不是稳定的，尤其是当相等元素出现在分区边界时，它们可能会改变顺序。 |
| 堆排序 | 不稳定 | 堆排序在排序过程中交换元素，因此通常不是稳定的。 |
| 选择排序 | 不稳定 | 选择排序每次选择最小（或最大）元素并交换，因此它不是稳定的。 |
| 计数排序 | 稳定 | 计数排序在处理相等元素时会确保它们的顺序不变，因此它是稳定的。 |
| 基数排序 | 稳定 | 基数排序在处理每个位上的数字时，会确保相同的数字保持原有顺序，因此它是稳定的。 |
| 桶排序 | 稳定 | 桶排序根据元素的范围将其分组，并在每个桶内进行排序。桶排序是稳定的，前提是桶内排序使用稳定排序算法。 |
稳定排序的实际应用
-
多关键字排序：当对一个数据集进行多次排序时，使用稳定排序算法可以保证第一次排序时相等元素的顺序不会改变。例如，先根据年龄排序，再根据名字排序，如果年龄相等，那么名字排序时相等的元素顺序不变。
-
数据表排序：假设我们有一个表格，其中包含员工的姓名、年龄和薪资。首先，我们可以根据薪资进行排序，然后根据年龄进行排序，最后根据姓名进行排序。如果我们使用稳定排序，则相同薪资的员工在年龄排序后仍然保持相对顺序。
总结：
稳定排序：能保持相等元素的相对顺序，常见的稳定排序算法有插入排序、归并排序、计数排序、基数排序和桶排序（依赖于桶内排序是否稳定）。 不稳定排序：可能会改变相等元素的相对顺序，常见的有快速排序、堆排序、选择排序等。
在选择排序算法时，如果排序的稳定性很重要（如多关键字排序），应优先选择稳定的排序算法，如归并排序、插入排序等。如果稳定性不是问题，且希望优化排序速度，可以选择快速排序或堆排序。
以下是冒泡排序、选择排序和希尔排序的 C++ 实现，并附有详细注释，帮助理解每种算法的工作原理。
1. 冒泡排序 (Bubble Sort)
冒泡排序通过重复地遍历待排序的序列，比较相邻元素并交换位置，直到没有需要交换的元素为止。
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; ++i) { // 外层循环控制遍历次数
bool swapped = false; // 标志变量，检查这一轮是否有交换
for (int j = 0; j < n - 1 - i; ++j) { // 内层循环进行相邻元素比较
if (arr[j] > arr[j + 1]) {
// 如果前一个元素比后一个元素大，交换它们
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
// 如果某一轮没有发生交换，说明数组已经有序，提前结束
if (!swapped) break;
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
2. 选择排序 (Selection Sort)
选择排序通过在未排序部分中找到最小（或最大）元素，将其交换到已排序部分的末尾。
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; ++i) {
int minIndex = i; // 假设当前元素为最小值
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 更新最小值的索引
}
}
// 交换当前元素和最小值元素
swap(arr[i], arr[minIndex]);
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
selectionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
3. 希尔排序 (Shell Sort)
希尔排序是插入排序的一种改进，它通过对间隔递减的元素进行插入排序，从而提高排序效率。
#include <iostream>
using namespace std;
void shellSort(int arr[], int n) {
// 从n/2开始，逐步减小步长，直至步长为1
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个步长进行插入排序
for (int i = gap; i < n; ++i) {
int temp = arr[i];
int j = i;
// 在间隔为gap的情况下，插入排序
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
int main() {
int arr[] = {12, 34, 54, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
shellSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
解释
冒泡排序：通过多次遍历数组，比较相邻元素并交换它们。如果在某一轮遍历中没有发生交换，说明数组已经有序，可以提前退出。最坏时间复杂度是 O(n²)，最好是 O(n)（当数组已经有序时）。
选择排序：每次选择未排序部分中的最小元素，然后交换到已排序部分的末尾。时间复杂度为 O(n²)，并且不依赖于输入数据的顺序，因此它的性能始终是一样的。
希尔排序：基于插入排序的改进，通过减少元素间的间隔进行插入排序。初步排序时，间隔较大，可以将数据尽早调整到大致有序的状态，从而在后续的插入排序过程中提高效率。时间复杂度取决于步长的选择，最坏情况下可能为 O(n²)，但通常可以达到 O(n^1.3) 左右。
总结
冒泡排序：简单易懂，但效率较低，时间复杂度 O(n²)。 选择排序：每次选择最小元素，时间复杂度 O(n²)，且无论输入数据如何，时间复杂度都是 O(n²)。 希尔排序：插入排序的改进，通过使用间隔排序提升效率，通常能比冒泡排序和选择排序更快。时间复杂度依赖于步长序列，最坏情况为 O(n²)，但通常比 O(n²) 更快。
这些排序算法可以帮助你理解不同排序方法的优缺点，并根据数据规模和应用场景选择合适的排序算法。
以下是关于冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、希尔排序、计数排序、基数排序和桶排序的汇总表格，包括它们的时间复杂度、空间复杂度、稳定性、适用场景等信息，便于学习和比较。
| 排序算法 | 时间复杂度 (最好) | 时间复杂度 (平均) | 时间复杂度 (最坏) | 空间复杂度 | 稳定性 | 适用场景 | 备注 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 小规模数据，或数据基本有序时 | 简单实现，但效率较低 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 小规模数据 | 每次选择最小值，不依赖输入顺序 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 小规模数据，或数据基本有序时 | 稳定，适合小规模或部分有序数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 大规模数据，尤其是外部排序 | 需要额外的内存空间 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 | 大规模数据，通常比归并排序更快 | 最常用的排序算法，分治法 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 大规模数据，尤其是需要堆结构时 | 非稳定排序，适用于堆的应用场景 |
| 希尔排序 | O(n log n) | $O(n^{3/2})$ | O(n²) | O(1) | 不稳定 | 中等规模数据，尤其是插入排序优化场景 | 提升了插入排序的效率 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 | 数据范围有限的整数排序 | 适用于小范围的整数排序 |
| 基数排序 | O(nk) | O(nk) | O(nk) | O(n+k) | 稳定 | 数据范围较小的整数或字符串排序 | 适用于整数和固定长度的字符串 |
| 桶排序 | O(n + k) | O(n + k) | O(n²) | O(n) | 稳定 | 数据均匀分布时，或已知数据范围 | 适用于数据均匀分布的情况 |
说明
时间复杂度：表示算法在不同输入下的表现，通常按最好的情况、平均情况和最坏的情况来描述。
最好情况：输入数据已经是最优状态。 平均情况：一般情况下，数据的分布是随机的。 最坏情况：最差的输入数据情况，通常是在已知最坏情况下的运行时间。
空间复杂度：表示算法所需的额外空间，通常用于表示算法的内存消耗。
稳定性：表示排序算法是否能够保持相等元素的相对顺序。如果相等的元素在排序后仍保持原来的相对顺序，则算法是稳定的。
适用场景：根据排序算法的特点，适合处理的数据规模和情况。
总结
稳定排序：冒泡排序、插入排序、归并排序、计数排序、基数排序和桶排序（前提是桶内排序使用稳定排序）。
不稳定排序：选择排序、快速排序、堆排序、希尔排序。
小规模数据或基本有序数据：插入排序、冒泡排序和选择排序适用。
大规模数据：归并排序、快速排序、堆排序、希尔排序适用。
对数据范围有限的情况：计数排序、基数排序、桶排序适用。
根据数据量的大小、排序的稳定性要求以及实现的复杂度，你可以选择最合适的排序算法。
在 C++ 中，std::sort 是一个非常高效的排序函数，定义在 <algorithm> 头文件中。它通常使用 快速排序（quicksort）或类似的排序算法，因此它的时间复杂度通常为 O(n log n)。此外，std::sort 是 不稳定排序，即它不保证相等元素的相对顺序。
std::sort 的基本用法
std::sort 可以对 数组、向量（std::vector）以及任何遵循 随机访问迭代器（Random Access Iterator）的容器进行排序。它的基本用法如下：
#include <algorithm> // 引入sort函数
#include <iostream> // 引入输入输出流
#include <vector> // 引入vector容器
int main() {
std::vector<int> vec = {10, 2, 30, 4, 20};
// 使用默认的升序排序
std::sort(vec.begin(), vec.end());
// 输出排序后的结果
std::cout << "Sorted vector: ";
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
std::sort 函数原型：
template< class RandomAccessIterator >
void sort(RandomAccessIterator first, RandomAccessIterator last);
first: 指向容器第一个元素的迭代器。 last: 指向容器最后一个元素之后的迭代器。
自定义排序方式
默认情况下，std::sort 按照升序对元素进行排序。如果你希望按照 降序 或其他自定义顺序来排序，可以传递一个 比较函数 或 比较函数对象（函数指针、lambda 表达式等）作为第三个参数。
1. 使用自定义比较函数
可以定义一个比较函数来指定排序顺序。例如，下面的代码按降序排序：
#include <algorithm>
#include <iostream>
#include <vector>
bool compare(int a, int b) {
return a > b; // 返回true时，a排在b前面，即降序排列
}
int main() {
std::vector<int> vec = {10, 2, 30, 4, 20};
// 使用自定义比较函数按降序排序
std::sort(vec.begin(), vec.end(), compare);
// 输出排序后的结果
std::cout << "Sorted vector in descending order: ";
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
2. 使用 Lambda 表达式
你也可以直接使用 lambda 表达式作为比较函数，这样代码更加简洁：
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {10, 2, 30, 4, 20};
// 使用lambda表达式按降序排序
std::sort(vec.begin(), vec.end(), [](int a, int b) {
return a > b; // 降序排序
});
// 输出排序后的结果
std::cout << "Sorted vector in descending order: ";
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
对结构体或对象排序
如果你想对自定义类型（如结构体、类）进行排序，可以为该类型定义比较函数或重载 < 操作符。
示例：按年龄排序的结构体
#include <algorithm>
#include <iostream>
#include <vector>
struct Person {
std::string name;
int age;
Person(std::string n, int a) : name(n), age(a) {}
};
// 自定义比较函数，按年龄排序
bool compareAge(const Person &p1, const Person &p2) {
return p1.age < p2.age; // 按年龄升序排列
}
int main() {
std::vector<Person> people = {
Person("Alice", 30),
Person("Bob", 25),
Person("Charlie", 35),
Person("Dave", 28)
};
// 按照年龄排序
std::sort(people.begin(), people.end(), compareAge);
// 输出排序后的结果
std::cout << "Sorted by age: \n";
for (const auto &person : people) {
std::cout << person.name << " (" << person.age << ")\n";
}
return 0;
}
在这个例子中，我们定义了一个 Person 结构体，包含 name 和 age 两个成员。然后，我们使用 std::sort 和自定义的 compareAge 函数按 age 排序。
示例：使用 operator< 排序
如果你希望排序按默认规则进行，可以通过重载 < 操作符：
#include <algorithm>
#include <iostream>
#include <vector>
struct Person {
std::string name;
int age;
Person(std::string n, int a) : name(n), age(a) {}
// 重载<运算符，按年龄升序排列
bool operator<(const Person &p) const {
return age < p.age; // 按年龄升序排序
}
};
int main() {
std::vector<Person> people = {
Person("Alice", 30),
Person("Bob", 25),
Person("Charlie", 35),
Person("Dave", 28)
};
// 使用重载的<运算符进行排序
std::sort(people.begin(), people.end());
// 输出排序后的结果
std::cout << "Sorted by age: \n";
for (const auto &person : people) {
std::cout << person.name << " (" << person.age << ")\n";
}
return 0;
}
这里我们重载了 Person 类的 < 操作符，使得 std::sort 默认按 age 进行升序排序。
总结
std::sort是一个高效的排序算法，默认使用快速排序，时间复杂度为 O(n log n)。- 它通过 随机访问迭代器 工作，可以对数组、
std::vector和其他支持随机访问的容器进行排序。 - 默认排序按升序排列，但你可以通过自定义比较函数或使用 lambda 表达式来实现降序排序或其他自定义排序顺序。
std::sort是 不稳定排序，即它不保证相等元素的相对顺序不变。
常见用途：排序整数、字符串、结构体对象等。适用于需要排序的大多数场景。