C++ STL 算法 sort 的排序稳定性分析
C++ STL 算法 sort 的排序稳定性分析
排序稳定性的基本概念
在探讨 C++ STL 中的 sort 算法的稳定性之前，我们首先要明确什么是排序稳定性。
假设有一个元素序列，其中存在多个具有相同键值的元素。当对这个序列进行排序后，如果这些具有相同键值的元素的相对顺序与排序前保持一致，那么这个排序算法就是稳定的；反之，如果排序后相同键值元素的相对顺序发生了变化，则该排序算法是不稳定的。
例如，有一个序列 (3, a), (2, b), (3, c)，其中括号内的第一个数字为键值，第二个字母为元素标识。经过稳定排序后，序列可能变为 (2, b), (3, a), (3, c)，相同键值 3 的元素 a 和 c 相对顺序保持不变。而不稳定排序可能得到 (2, b), (3, c), (3, a)，此时相同键值元素的相对顺序改变了。
排序稳定性在很多实际应用场景中非常重要。比如，在对学生成绩进行排序时，如果成绩相同，希望保持学生原来的录入顺序，这样稳定排序算法就能满足需求。
C++ STL 中的 sort 算法概述
C++ 标准模板库（STL）中的 sort 算法是一个强大且高效的排序工具，定义在 <algorithm> 头文件中。sort 函数有两种重载形式：
// 第一种形式，使用默认的比较函数（升序）
template<class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);
// 第二种形式，允许用户自定义比较函数
template<class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
第一个参数 first 指向要排序范围的起始位置，last 指向要排序范围的末尾位置（但不包括该位置的元素）。在第二种重载形式中，comp 是一个可调用对象，用于定义比较规则。
sort 算法的实现原理
C++ STL 中的 sort 算法通常采用的是一种混合排序算法，一般是内省排序（Introsort）。内省排序结合了多种排序算法的优点，以达到高效排序的目的。
- 快速排序（Quicksort）：快速排序是内省排序的基础。它的基本思想是通过选择一个基准元素，将序列分为两部分，左边部分的元素都小于基准元素，右边部分的元素都大于基准元素，然后对左右两部分递归地进行排序。快速排序平均情况下的时间复杂度为 $O(nlogn)$，但在最坏情况下（如序列已经有序），时间复杂度会退化为 $O(n^2)$。
// 简单的快速排序示例代码
template <typename T>
void quickSort(T arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
template <typename T>
int partition(T arr[], int low, int high) {
T pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
- 堆排序（Heapsort）：当快速排序递归深度过大（可能导致最坏情况）时，内省排序会切换到堆排序。堆排序是一种基于二叉堆数据结构的排序算法，它的时间复杂度始终为 $O(nlogn)$。堆排序首先将序列构建成一个最大堆（或最小堆），然后每次取出堆顶元素（最大或最小），并调整堆结构，直到整个序列有序。
// 简单的堆排序示例代码
template <typename T>
void heapify(T 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);
}
}
template <typename T>
void heapSort(T 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);
}
}
- 插入排序（Insertion Sort）：当序列规模较小时，内省排序会使用插入排序。插入排序是一种简单的排序算法，对于小规模数据或部分有序的数据表现良好。它的基本思想是将一个数据插入到已经排好序的数组中的适当位置。插入排序在最好情况下（序列已经有序）的时间复杂度为 $O(n)$，平均和最坏情况下的时间复杂度为 $O(n^2)$。
// 简单的插入排序示例代码
template <typename T>
void insertionSort(T arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
内省排序综合利用这三种排序算法，在不同情况下发挥各自的优势，从而实现高效的排序。
sort 算法的稳定性分析
由于 sort 算法采用的内省排序中，快速排序和堆排序本身都是不稳定的排序算法，因此 C++ STL 中的 sort 算法通常是不稳定的。
下面通过代码示例来验证这一点：
#include <iostream>
#include <algorithm>
#include <vector>
struct Data {
int value;
int index;
Data(int v, int i) : value(v), index(i) {}
};
bool operator<(const Data& a, const Data& b) {
return a.value < b.value;
}
void printData(const std::vector<Data>& data) {
for (const auto& d : data) {
std::cout << "(" << d.value << ", " << d.index << ") ";
}
std::cout << std::endl;
}
int main() {
std::vector<Data> data = {
Data(3, 1),
Data(2, 2),
Data(3, 3)
};
std::cout << "Before sorting: ";
printData(data);
std::sort(data.begin(), data.end());
std::cout << "After sorting: ";
printData(data);
return 0;
}
在上述代码中，我们定义了一个 Data 结构体，包含一个整数值 value 和一个索引值 index。我们重载了 < 运算符，使得 Data 对象按照 value 进行比较。在 main 函数中，我们创建了一个 Data 向量，并对其进行 sort 排序。如果 sort 是稳定的，相同 value 的元素在排序后 index 的相对顺序应该保持不变，但实际运行代码会发现，相同 value 的元素相对顺序可能改变。
如何实现稳定排序
虽然 sort 算法本身不稳定，但 C++ STL 提供了 stable_sort 算法来实现稳定排序。stable_sort 同样定义在 <algorithm> 头文件中，也有两种重载形式：
// 第一种形式，使用默认的比较函数（升序）
template<class RandomAccessIterator>
void stable_sort (RandomAccessIterator first, RandomAccessIterator last);
// 第二种形式，允许用户自定义比较函数
template<class RandomAccessIterator, class Compare>
void stable_sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
stable_sort 的实现通常采用归并排序的思想。归并排序是一种稳定的排序算法，它将序列分成两个子序列，对每个子序列递归地进行排序，然后将两个有序的子序列合并成一个有序的序列。在合并过程中，通过适当的处理可以保证相同键值元素的相对顺序不变。
下面是一个简单的归并排序示例代码，以展示稳定排序的过程：
// 合并两个子数组
template <typename T>
void merge(T arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
T 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, 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++;
}
}
// 归并排序主函数
template <typename T>
void mergeSort(T 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);
}
}
使用 stable_sort 的示例代码如下：
#include <iostream>
#include <algorithm>
#include <vector>
struct Data {
int value;
int index;
Data(int v, int i) : value(v), index(i) {}
};
bool operator<(const Data& a, const Data& b) {
return a.value < b.value;
}
void printData(const std::vector<Data>& data) {
for (const auto& d : data) {
std::cout << "(" << d.value << ", " << d.index << ") ";
}
std::cout << std::endl;
}
int main() {
std::vector<Data> data = {
Data(3, 1),
Data(2, 2),
Data(3, 3)
};
std::cout << "Before stable sorting: ";
printData(data);
std::stable_sort(data.begin(), data.end());
std::cout << "After stable sorting: ";
printData(data);
return 0;
}
在上述代码中，我们使用 stable_sort 对 Data 向量进行排序。运行代码可以看到，相同 value 的元素在排序后 index 的相对顺序保持不变，这证明了 stable_sort 是稳定的排序算法。
选择排序算法时稳定性的考量
在实际编程中，选择排序算法时需要考虑稳定性因素。
-
数据特性：如果数据中相同键值的元素相对顺序很重要，比如前面提到的学生成绩排序，保持相同成绩学生的录入顺序，那么必须选择稳定的排序算法，如
stable_sort。 -
性能需求：虽然
stable_sort能保证稳定性，但在某些情况下，sort算法可能性能更优。例如，当数据规模较大且对稳定性没有要求时，sort算法（内省排序）由于综合了多种排序算法的优点，平均性能会更好。 -
空间复杂度：
stable_sort的空间复杂度在某些实现中可能比sort略高，因为归并排序在合并过程中需要额外的空间。如果空间资源有限，这也是需要考虑的因素之一。
在选择排序算法时，需要综合权衡稳定性、性能和空间复杂度等多方面因素，以选择最适合具体应用场景的排序算法。
总结
C++ STL 中的 sort 算法通常采用内省排序，结合了快速排序、堆排序和插入排序的优点，在大多数情况下能提供高效的排序性能，但它是不稳定的排序算法。如果需要保证相同键值元素的相对顺序不变，应使用 stable_sort 算法。在实际应用中，要根据数据特性、性能需求和空间复杂度等因素来合理选择排序算法，以达到最佳的编程效果。通过对 sort 算法稳定性的分析以及与稳定排序算法的对比，希望读者能在实际编程中更加准确地选择和使用排序算法。