深度剖析std::sort

LZZMC • 2025-01-20 14:10 • 编程

一、简介

std::sort是C++ STL的一个排序算法，它可以按照一定规则对一个给定的数组、向量或迭代器范围内的元素进行排序。std::sort是非稳定排序算法，平均时间复杂度为O(nlogn)，最坏情况下时间复杂度为O(n^2)，空间复杂度为O(logn)。

二、语法

template
void sort( RandomIt first, RandomIt last );
template
void sort( RandomIt first, RandomIt last, Compare comp );

sort接受两个迭代器参数，第一个迭代器first表示要排序的范围中的第一个元素，last表示最后一个元素的下一个位置。sort可以通过比较器comp自定义排序规则。

三、排序规则

std::sort默认按照小于号运算符（operator<）进行比较，也就是说，排序后的元素是按照从小到大的顺序排列的。如果想要对元素按照从大到小的顺序排序，可以自定义比较器：

bool cmp(int a, int b) {
    return a > b;
}
std::sort(a.begin(), a.end(), cmp);

上面的代码定义了一个比较器cmp，将a中的元素按照从大到小的顺序进行排序。

四、分区策略

std::sort采用的是快速排序（quicksort）的分区策略。简单来说，快速排序的过程就是先选出一个元素作为基准（pivot），将比pivot小的元素放在左边，比pivot大的元素放在右边，然后递归排序左右两个子序列。

std::sort是一种不稳定排序算法，排序后相等的元素在数组中的相对位置可能会发生变化。这是因为std::sort的分区策略采用的是最后一个元素作为基准，而不是中间的元素或者随机选择的元素。如果存在相等的元素，std::sort在分区时很可能会导致相等的元素被分配到不同的子序列中。

五、优化

1. 优化比较器

std::sort在每一次比较时都要调用比较器函数，因此比较器函数的效率对排序的性能有很大影响。可以采用lambda函数或者函数对象的方式对比较器进行优化：

std::sort(a.begin(), a.end(), [](int a, int b) {
    return a > b;
});

上面的代码使用lambda函数定义了一个比较器，实现了对a的降序排序。

2. 优化部分排序

如果只需要对序列中的一部分进行排序，可以使用partial_sort函数，比直接使用sort要快一些：

std::partial_sort(a.begin(), a.begin() + k, a.end());

上面的代码对a中前k个元素进行排序，后面的元素不保证有序。此时，partial_sort的时间复杂度为O(nlogk)，比sort快了一些。

六、示例

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> a = {3, 1, 2, 5, 4};
    std::sort(a.begin(), a.end());
    for (auto it : a) {
        std::cout << it << " ";
    }
    std::cout << std::endl;

    std::sort(a.begin(), a.end(), [](int a, int b) {
        return a > b;
    });
    for (auto it : a) {
        std::cout << it << " ";
    }
    std::cout << std::endl;

    std::partial_sort(a.begin(), a.begin() + 3, a.end());
    for (auto it : a) {
        std::cout << it << " ";
    }
    std::cout << std::endl;

    return 0;
}

原创文章，作者：LZZMC，如若转载，请注明出处：https://www.506064.com/n/331812.html