当前位置：
  1. 首页
  2. 互联网
  3. 正文
本文介绍: 本文介绍了QT中的几种常用的排序函数，包括qSort，qStableSort，qPartialSort，qHeapSort，qLowerBound和qUpperBound，它们可以对QT中的一些容器类中的元素进行排序或者查找。qSort函数是一个通用的排序函数，它使用快速排序算法，可以对任何可随机访问的序列进行排序。它的优点是，它的平均时间复杂度是O(nlogn)，空间复杂度是O(logn)，效率较高。它的缺点是，它的最坏情况下的时间复杂度是O(n^2)，效率较低。

第一章：排序函数的概述

排序函数是一种在编程中常用的函数，它可以对一个序列（如数组，列表，向量等）中的元素进行排序，使其按照一定的顺序排列。排序函数可以根据不同的排序算法，如冒泡排序，选择排序，插入排序，快速排序，归并排序，堆排序等，实现不同的排序效果。排序函数的作用有以下几点：

QT是一个跨平台的应用程序开发框架，它提供了一些常用的排序函数，可以对QT中的一些容器类（如QList，QVector，QMap，QSet等）中的元素进行排序。QT中提供的排序函数有以下几种：

  • qSort：这是一个通用的排序函数，它使用快速排序算法，可以对任何可随机访问的序列进行排序。它可以指定一个比较函数或者一个比较对象，来自定义排序的规则。它的排序结果是不稳定的，也就是说，如果序列中有相等的元素，它们的相对位置可能会改变。
  • qStableSort：这是一个稳定的排序函数，它使用归并排序算法，可以对任何可随机访问的序列进行排序。它可以指定一个比较函数或者一个比较对象，来自定义排序的规则。它的排序结果是稳定的，也就是说，如果序列中有相等的元素，它们的相对位置不会改变。
  • qPartialSort：这是一个部分排序函数，它使用堆排序算法，可以对任何可随机访问的序列进行部分排序。它可以指定一个范围，只对序列中的这个范围内的元素进行排序，而不影响其他元素。它可以指定一个比较函数或者一个比较对象，来自定义排序的规则。它的排序结果是不稳定的。
  • qHeapSort：这是一个堆排序函数，它使用堆排序算法，可以对任何可随机访问的序列进行排序。它可以指定一个比较函数或者一个比较对象，来自定义排序的规则。它的排序结果是不稳定的。它的特点是，它可以在不使用额外空间的情况下，对序列进行原地排序，也就是说，它不需要创建一个新的序列来存储排序结果，而是直接在原序列上进行操作。
  • qLowerBound和qUpperBound：这不是排序函数，而是查找函数，它们可以在一个有序的序列中，查找一个给定的元素的下界和上界。下界是指序列中第一个不小于给定元素的位置，上界是指序列中第一个大于给定元素的位置。它们可以指定一个比较函数或者一个比较对象，来自定义查找的规则。它们的查找效率是对数级别的，也就是说，它们使用二分查找算法，每次查找都可以将查找范围缩小一半。

第二章：qSort函数

qSort函数是QT中提供的一个通用的排序函数，它使用快速排序算法，可以对任何可随机访问的序列进行排序。快速排序算法的基本思想是，选择一个基准元素，将序列分为两个子序列，一个子序列中的元素都小于或等于基准元素，另一个子序列中的元素都大于基准元素，然后对这两个子序列递归地进行快速排序，最后将两个子序列合并成一个有序的序列。快速排序算法的平均时间复杂度是O(nlogn)，最坏情况下的时间复杂度是O(n^2)，空间复杂度是O(logn)。

qSort函数的函数原型如下

template <typename RandomAccessIterator&gt;
void qSort(RandomAccessIterator begin, RandomAccessIterator end);

template <typename RandomAccessIterator, typename LessThan&gt;
void qSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan);

qSort函数的功能参数

对从begin到end（不包括end）的元素进行排序。

第一个参数begin是指向序列开始位置的迭代器

第二个参数end是指向序列结束位置的迭代器

第三个参数lessThan是一个比较函数或者一个比较对象，它可以自定义排序的规则，它接受两个元素作为参数，返回一个布尔值，表示第一个元素是否小于第二个元素。如果没有指定第三个参数，qSort函数会使用默认的比较规则，即使用元素的<运算符进行比较。

qSort函数的用法示例

int arr[] = {5, 3, 7, 1, 9, 4, 6, 8, 2};
qSort(arr, arr + 9); // 对arr数组进行升序排序
  • 如果要对一个QList或者QVector进行排序，可以使用它们的begin()和end()方法来获取迭代器，例如：
QList<int&gt; list;
list << 5 << 3 << 7 << 1 << 9 << 4 << 6 << 8 << 2;
qSort(list.begin(), list.end()); // 对list进行升序排序
  • 如果要对一个QMap或者QSet进行排序，可以使用它们的keys()或者values()方法来获取一个QList，然后对QList进行排序，例如：
QMap<QString, int&gt; map;
map["Alice"] = 90;
map["Bob"] = 80;
map["Charlie"] = 85;
map["David"] = 95;
QList<QString> names = map.keys(); // 获取map的键的列表
qSort(names.begin(), names.end()); // 对names进行升序排序
  • 如果要自定义排序的规则，可以传入一个比较函数或者一个比较对象作为第三个参数，例如：
// 定义一个比较函数，按照字符串的长度进行比较
bool compareByLength(const QString &amp;a, const QString &amp;b)
{
    return a.length() < b.length();
}

// 定义一个比较对象，按照学生的成绩进行比较
struct compareByScore
{
    bool operator()(const Student &amp;a, const Student &amp;b)
    {
        return a.score > b.score; // 降序排序
    }
};

QList<QString> words;
words << "apple" << "banana" << "orange" << "pear" << "grape";
qSort(words.begin(), words.end(), compareByLength); // 按照单词的长度进行升序排序

QList<Student> students;
students << Student("Alice", 90) << Student("Bob", 80) << Student("Charlie", 85) << Student("David", 95);
qSort(students.begin(), students.end(), compareByScore()); // 按照学生的成绩进行降序排序

qSort函数注意事项

  • begin和end必须指向同一个序列，否则会导致未定义的行为。
  • begin和end之间的元素必须能够被交换，否则会导致编译错误。
  • begin和end之间的元素必须能够被比较，否则会导致编译错误或者运行时错误。
  • lessThan必须是一个严格弱序关系，也就是说，它必须满足以下条件：
    • 对于任何元素x，lessThan(x, x)必须返回false。
    • 如果lessThan(x, y)返回true，那么lessThan(y, x)必须返回false。
    • 如果lessThan(x, y)和lessThan(y, z)都返回true，那么lessThan(x, z)也必须返回true。
  • qSort函数的排序结果是不稳定的，也就是说，如果序列中有相等的元素（即lessThan(x, y)和lessThan(y, x)都返回false），它们的相对位置可能会改变。

以上就是qSort函数的介绍，下面我们将介绍qStableSort函数。

第三章：qStableSort函数

qStableSort函数是QT中提供的一个稳定的排序函数，它使用归并排序算法，可以对任何可随机访问的序列进行排序。归并排序算法的基本思想是，将序列分为两个子序列，对这两个子序列分别进行归并排序，然后将两个有序的子序列合并成一个有序的序列。归并排序算法的时间复杂度是O(nlogn)，空间复杂度是O(n)。

qStableSort函数的函数原型如下

template <typename RandomAccessIterator>
void qStableSort(RandomAccessIterator begin, RandomAccessIterator end);

template <typename RandomAccessIterator, typename LessThan>
void qStableSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan);

qStableSort函数的功能参数

对从begin到end（不包括end）的元素进行排序

第一个参数begin是指向序列开始位置的迭代器

第二个参数end是指向序列结束位置的迭代器

第三个参数lessThan是一个比较函数或者一个比较对象，它可以自定义排序的规则，它接受两个元素作为参数，返回一个布尔值，表示第一个元素是否小于第二个元素。如果没有指定第三个参数，qStableSort函数会使用默认的比较规则，即使用元素的<运算符进行比较。

qStableSort函数的用法示例

qStableSort函数的用法和qSort函数的用法基本相同，只是qStableSort函数的排序结果是稳定的，也就是说，如果序列中有相等的元素（即lessThan(x, y)和lessThan(y, x)都返回false），它们的相对位置不会改变。这一点在一些场景中是很重要的，例如，如果要对一个学生的列表按照姓名进行排序，然后再按照成绩进行排序，如果使用qSort函数，那么姓名相同的学生的成绩顺序可能会被打乱，而如果使用qStableSort函数，那么姓名相同的学生的成绩顺序会保持不变。

代码示例：

#include <QList>
#include <QString>
#include <QDebug>

// 定义一个学生类，包含姓名和成绩两个属性
class Student
{
public:
    Student(const QString &name, int score) : name(name), score(score) {}
    QString name; // 姓名
    int score; // 成绩
};

// 定义一个比较函数，按照姓名进行升序排序
bool compareByName(const Student &a, const Student &b)
{
    return a.name < b.name;
}

// 定义一个比较函数，按照成绩进行降序排序
bool compareByScore(const Student &a, const Student &b)
{
    return a.score > b.score;
}


// 创建一个学生的列表
    QList<Student> students;
    students << Student("Alice", 90) << Student("Bob", 80) << Student("Charlie", 85) << Student("David", 95) << Student("Alice", 88) << Student("Bob", 82);

    // 使用qStableSort函数按照姓名进行排序
    qStableSort(students.begin(), students.end(), compareByName);

    // 打印排序后的结果
    qDebug() << "Sorted by name:";
    for (const Student &s : students)
    {
        qDebug() << s.name << s.score;
    }

    // 使用qStableSort函数按照成绩进行排序
    qStableSort(students.begin(), students.end(), compareByScore);

    // 打印排序后的结果
    qDebug() << "Sorted by score:";
    for (const Student &s : students)
    {
        qDebug() << s.name << s.score;
    }

运行这段代码，可以得到以下输出：

Sorted by name:
Alice 90
Alice 88
Bob 80
Bob 82
Charlie 85
David 95
Sorted by score:
David 95
Alice 90
Alice 88
Charlie 85
Bob 82
Bob 80

可以看到，qStableSort函数的排序结果是稳定的，也就是说，姓名相同的学生的成绩顺序没有改变，而是保持了原来的顺序。这样就可以方便地对数据进行分组或者分析。

qStableSort函数注意事项

  • begin和end必须指向同一个序列，否则会导致未定义的行为。
  • begin和end之间的元素必须能够被交换，否则会导致编译错误。
  • begin和end之间的元素必须能够被比较，否则会导致编译错误或者运行时错误。
  • lessThan必须是一个严格弱序关系，也就是说，它必须满足以下条件：
    • 对于任何元素x，lessThan(x, x)必须返回false。
    • 如果lessThan(x, y)返回true，那么lessThan(y, x)必须返回false。
    • 如果lessThan(x, y)和lessThan(y, z)都返回true，那么lessThan(x, z)也必须返回true。
  • qStableSort函数的排序结果是稳定的，也就是说，如果序列中有相等的元素，它们的相对位置不会改变。

以上就是qStableSort函数的介绍，下面我们将介绍qPartialSort函数

第四章：qPartialSort函数

qPartialSort函数是QT中提供的一个部分排序函数，它使用堆排序算法，可以对任何可随机访问的序列进行部分排序。堆排序算法的基本思想是，将序列视为一个完全二叉树，然后构建一个最大堆或者最小堆，也就是说，每个节点的值都大于或者小于它的子节点的值。然后，将堆的根节点（也就是最大或者最小的元素）与堆的最后一个节点交换，然后将堆的大小减一，再调整堆的结构，重复这个过程，直到堆的大小等于指定的范围。堆排序算法的时间复杂度是O(nlogn)，空间复杂度是O(1)。

qPartialSort函数的函数原型

template <typename RandomAccessIterator>
void qPartialSort(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end);

template <typename RandomAccessIterator, typename LessThan>
void qPartialSort(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, LessThan lessThan);

qPartialSort函数的功能参数

对从begin到end（不包括end）的元素进行部分排序，使得从begin到middle（不包括middle）的元素是最小的或者最大的，而且是有序的，而从middle到end的元素是无序的。

第一个参数begin是指向序列开始位置的迭代器

第二个参数middle是指向序列中间位置的迭代器

第三个参数end是指向序列结束位置的迭代器

第四个参数lessThan是一个比较函数或者一个比较对象，它可以自定义排序的规则，它接受两个元素作为参数，返回一个布尔值，表示第一个元素是否小于第二个元素。如果没有指定第四个参数，qPartialSort函数会使用默认的比较规则，即使用元素的<运算符进行比较。

qPartialSort函数的用法示例

  • 如果要对一个数组进行部分排序，可以直接传入数组的首地址，中间地址和尾地址作为参数，例如：
int arr[] = {5, 3, 7, 1, 9, 4, 6, 8, 2};
qPartialSort(arr, arr + 3, arr + 9); // 对arr数组进行部分排序，使得前三个元素是最小的，并且是有序的
  • 如果要对一个QList或者QVector进行部分排序，可以使用它们的begin()和end()方法来获取迭代器，例如：
QList<int> list;
list << 5 << 3 << 7 << 1 << 9 << 4 << 6 << 8 << 2;
qPartialSort(list.begin(), list.begin() + 3, list.end()); // 对list进行部分排序，使得前三个元素是最小的，并且是有序的
  • 如果要对一个QMap或者QSet进行部分排序，可以使用它们的keys()或者values()方法来获取一个QList，然后对QList进行部分排序，例如：
QMap<QString, int> map;
map["Alice"] = 90;
map["Bob"] = 80;
map["Charlie"] = 85;
map["David"] = 95;
QList<int> scores = map.values(); // 获取map的值的列表
qPartialSort(scores.begin(), scores.begin() + 2, scores.end()); // 对scores进行部分排序，使得前两个元素是最小的，并且是有序的
  • 如果要自定义排序的规则，可以传入一个比较函数或者一个比较对象作为第四个参数，例如：
// 定义一个比较函数，按照字符串的长度进行比较
bool compareByLength(const QString &a, const QString &b)
{
    return a.length() < b.length();
}

// 定义一个比较对象，按照学生的成绩进行比较
struct compareByScore
{
    bool operator()(const Student &a, const Student &b)
    {
        return a.score > b.score; // 降序排序
    }
};

QList<QString> words;
words << "apple" << "banana" << "orange" << "pear" << "grape";
qPartialSort(words.begin(), words.begin() + 2, words.end(), compareByLength); // 按照单词的长度进行部分排序，使得前两个元素是最短的，并且是有序的

QList<Student> students;
students << Student("Alice", 90) << Student("Bob", 80) << Student("Charlie", 85) << Student("David", 95);
qPartialSort(students.begin(), students.begin() + 2, students.end(), compareByScore()); // 按照学生的成绩进行部分排序，使得前两个元素是最高的，并且是有序的

qPartialSort函数注意事项

  • begin，middle和end必须指向同一个序列，否则会导致未定义的行为。
  • begin，middle和end之间的元素必须能够被交换，否则会导致编译错误。
  • begin，middle和end之间的元素必须能够被比较，否则会导致编译错误或者运行时错误。
  • lessThan必须是一个严格弱序关系，也就是说，它必须满足以下条件：
    • 对于任何元素x，lessThan(x, x)必须返回false。
    • 如果lessThan(x, y)返回true，那么lessThan(y, x)必须返回false。
    • 如果lessThan(x, y)和lessThan(y, z)都返回true，那么lessThan(x, z)也必须返回true。
  • qPartialSort函数的排序结果是不稳定的，也就是说，如果序列中有相等的元素，它们的相对位置可能会改变。

以上就是qPartialSort函数的介绍，下面我们将介绍qHeapSort函数。

第五章：qHeapSort函数

qHeapSort函数是QT中提供的一个堆排序函数，它使用堆排序算法，可以对任何可随机访问的序列进行排序。堆排序算法的基本思想是，将序列视为一个完全二叉树，然后构建一个最大堆或者最小堆，也就是说，每个节点的值都大于或者小于它的子节点的值。然后，将堆的根节点（也就是最大或者最小的元素）与堆的最后一个节点交换，然后将堆的大小减一，再调整堆的结构，重复这个过程，直到堆的大小为零。堆排序算法的时间复杂度是O(nlogn)，空间复杂度是O(1)。

qHeapSort函数的函数原型

template <typename RandomAccessIterator>
void qHeapSort(RandomAccessIterator begin, RandomAccessIterator end);

template <typename RandomAccessIterator, typename LessThan>
void qHeapSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan);

qHeapSort函数的功能是参数

对从begin到end（不包括end）的元素进行排序。

第一个参数begin是指向序列开始位置的迭代器

第二个参数end是指向序列结束位置的迭代器

第三个参数lessThan是一个比较函数或者一个比较对象，它可以自定义排序的规则，它接受两个元素作为参数，返回一个布尔值，表示第一个元素是否小于第二个元素。如果没有指定第三个参数，qHeapSort函数会使用默认的比较规则，即使用元素的<运算符进行比较。

qHeapSort函数的用法示例

qSort函数的用法基本相同，只是qHeapSort函数的特点是，它可以在不使用额外空间的情况下，对序列进行原地排序，也就是说，它不需要创建一个新的序列来存储排序结果，而是直接在原序列上进行操作。这样就可以节省空间，提高效率。

代码示例：

#include <QList>
#include <QString>
#include <QDebug>

// 定义一个学生类，包含姓名和成绩两个属性
class Student
{
public:
    Student(const QString &name, int score) : name(name), score(score) {}
    QString name; // 姓名
    int score; // 成绩
};

// 定义一个比较函数，按照姓名进行升序排序
bool compareByName(const Student &a, const Student &b)
{
    return a.name < b.name;
}

// 定义一个比较函数，按照成绩进行降序排序
bool compareByScore(const Student &a, const Student &b)
{
    return a.score > b.score;
}


    // 创建一个学生的列表
    QList<Student> students;
    students << Student("Alice", 90) << Student("Bob", 80) << Student("Charlie", 85) << Student("David", 95);

    // 使用qHeapSort函数按照姓名进行排序
    qHeapSort(students.begin(), students.end(), compareByName);

    // 打印排序后的结果
    qDebug() << "Sorted by name:";
    for (const Student &s : students)
    {
        qDebug() << s.name << s.score;
    }

    // 使用qHeapSort函数按照成绩进行排序
    qHeapSort(students.begin(), students.end(), compareByScore);

    // 打印排序后的结果
    qDebug() << "Sorted by score:";
    for (const Student &s : students)
    {
        qDebug() << s.name << s.score;
    }

 运行这段代码，可以得到以下输出：

Sorted by name:
Alice 90
Bob 80
Charlie 85
David 95
Sorted by score:
David 95
Alice 90
Charlie 85
Bob 80

可以看到，qHeapSort函数的排序结果是不稳定的，也就是说，姓名相同的学生的成绩顺序可能会改变，而且它可以在不使用额外空间的情况下，对序列进行原地排序，也就是说，它不需要创建一个新的序列来存储排序结果，而是直接在原序列上进行操作。

qHeapSort函数的注意事项

  • begin和end必须指向同一个序列，否则会导致未定义的行为。
  • begin和end之间的元素必须能够被交换，否则会导致编译错误。
  • begin和end之间的元素必须能够被比较，否则会导致编译错误或者运行时错误。
  • lessThan必须是一个严格弱序关系，也就是说，它必须满足以下条件：
    • 对于任何元素x，lessThan(x, x)必须返回false。
    • 如果lessThan(x, y)返回true，那么lessThan(y, x)必须返回false。
    • 如果lessThan(x, y)和lessThan(y, z)都返回true，那么lessThan(x, z)也必须返回true。
  • qHeapSort函数的排序结果是不稳定的，也就是说，如果序列中有相等的元素，它们的相对位置可能会改变。

以上就是qHeapSort函数的介绍，下面我们将介绍qLowerBound和qUpperBound函数。

第六章：qLowerBound和qUpperBound函数

qLowerBound和qUpperBound函数是QT中提供的两个查找函数，它们可以在一个有序的序列中，查找一个给定的元素的下界和上界。下界是指序列中第一个不小于给定元素的位置，上界是指序列中第一个大于给定元素的位置。它们可以指定一个比较函数或者一个比较对象，来自定义查找的规则。它们的查找效率是对数级别的，也就是说，它们使用二分查找算法，每次查找都可以将查找范围缩小一半。

qLowerBound和qUpperBound函数的函数原型

template <typename ForwardIterator, typename T>
ForwardIterator qLowerBound(ForwardIterator begin, ForwardIterator end, const T &value);

template <typename ForwardIterator, typename T, typename LessThan>
ForwardIterator qLowerBound(ForwardIterator begin, ForwardIterator end, const T &value, LessThan lessThan);

template <typename ForwardIterator, typename T>
ForwardIterator qUpperBound(ForwardIterator begin, ForwardIterator end, const T &value);

template <typename ForwardIterator, typename T, typename LessThan>
ForwardIterator qUpperBound(ForwardIterator begin, ForwardIterator end, const T &value, LessThan lessThan);

qLowerBound和qUpperBound函数的功能和参数

分别在从begin到end（不包括end）的元素中，查找value的下界和上界。

第一个参数begin是指向序列开始位置的迭代器

第二个参数end是指向序列结束位置的迭代器

第三个参数value是要查找的元素

第四个参数lessThan是一个比较函数或者一个比较对象，它可以自定义查找的规则，它接受两个元素作为参数，返回一个布尔值，表示第一个元素是否小于第二个元素。如果没有指定第四个参数，qLowerBound和qUpperBound函数会使用默认的比较规则，即使用元素的<运算符进行比较。

qLowerBound和qUpperBound函数的用法示例

  • 如果要在一个数组中查找一个元素的下界和上界，可以直接传入数组的首地址和尾地址作为参数，例如：
int arr[] = {1, 2, 3, 3, 3, 4, 5};
int *lower = qLowerBound(arr, arr + 7, 3); // 查找3的下界
int *upper = qUpperBound(arr, arr + 7, 3); // 查找3的上界
qDebug() << "Lower bound of 3 is" << lower - arr; // 输出3的下界的索引
qDebug() << "Upper bound of 3 is" << upper - arr; // 输出3的上界的索引
  • 如果要在一个QList或者QVector中查找一个元素的下界和上界，可以使用它们的begin()和end()方法来获取迭代器，例如：
QList<int> list;
list << 1 << 2 << 3 << 3 << 3 << 4 << 5;
QList<int>::iterator lower = qLowerBound(list.begin(), list.end(), 3); // 查找3的下界
QList<int>::iterator upper = qUpperBound(list.begin(), list.end(), 3); // 查找3的上界
qDebug() << "Lower bound of 3 is" << lower - list.begin(); // 输出3的下界的索引
qDebug() << "Upper bound of 3 is" << upper - list.begin(); // 输出3的上界的索引
  • 如果要在一个QMap或者QSet中查找一个元素的下界和上界，可以使用它们的keys()或者values()方法来获取一个QList，然后在QList中查找，例如：
QMap<QString, int> map;
map["Alice"] = 90;
map["Bob"] = 80;
map["Charlie"] = 85;
map["David"] = 95;
QList<int> scores = map.values(); // 获取map的值的列表
qSort(scores.begin(), scores.end()); // 对scores进行排序
QList<int>::iterator lower = qLowerBound(scores.begin(), scores.end(), 85); // 查找85的下界
QList<int>::iterator upper = qUpperBound(scores.begin(), scores.end(), 85); // 查找85的上界
qDebug() << "Lower bound of 85 is" << lower - scores.begin(); // 输出85的下界的索引
qDebug() << "Upper bound of 85 is" << upper - scores.begin(); // 输出85的上界的索引

第七章：总结

本文介绍了QT中的几种常用的排序函数，包括qSort，qStableSort，qPartialSort，qHeapSort，qLowerBound和qUpperBound，它们可以对QT中的一些容器类中的元素进行排序或者查找。

下面我们将比较一下不同排序函数的优缺点，以及给出一些使用建议：

  • qSort函数是一个通用的排序函数，它使用快速排序算法，可以对任何可随机访问的序列进行排序。它的优点是，它的平均时间复杂度是O(nlogn)，空间复杂度是O(logn)，效率较高。它的缺点是，它的最坏情况下的时间复杂度是O(n^2)，效率较低。另外，它的排序结果是不稳定的，也就是说，如果序列中有相等的元素，它们的相对位置可能会改变。因此，如果要对一个序列进行排序，可以使用qSort函数，但是要注意避免最坏情况的发生，以及考虑是否需要保持元素的相对位置。
  • qStableSort函数是一个稳定的排序函数，它使用归并排序算法，可以对任何可随机访问的序列进行排序。它的优点是，它的时间复杂度是O(nlogn)，效率较高。另外，它的排序结果是稳定的，也就是说，如果序列中有相等的元素，它们的相对位置不会改变。这一点在一些场景中是很重要的，例如，如果要对一个学生的列表按照姓名进行排序，然后再按照成绩进行排序，如果使用qSort函数，那么姓名相同的学生的成绩顺序可能会被打乱，而如果使用qStableSort函数，那么姓名相同的学生的成绩顺序会保持不变。它的缺点是，它的空间复杂度是O(n)，需要额外的空间来存储排序结果。因此，如果要对一个序列进行排序，而且需要保持元素的相对位置，可以使用qStableSort函数，但是要注意空间的消耗。
  • qPartialSort函数是一个部分排序函数，它使用堆排序算法，可以对任何可随机访问的序列进行部分排序。它的优点是，它可以指定一个范围，只对序列中的这个范围内的元素进行排序，而不影响其他元素。这样就可以节省时间，提高效率。它的缺点是，它的排序结果是不稳定的，也就是说，如果序列中有相等的元素，它们的相对位置可能会改变。另外，它的时间复杂度是O(nlogn)，空间复杂度是O(1)，效率和空间都不是最优的。因此，如果要对一个序列进行部分排序，可以使用qPartialSort函数，但是要注意元素的相对位置，以及是否有更好的算法。
  • qHeapSort函数是一个堆排序函数，它使用堆排序算法，可以对任何可随机访问的序列进行排序。它的优点是，它可以在不使用额外空间的情况下，对序列进行原地排序，也就是说，它不需要创建一个新的序列来存储排序结果，而是直接在原序列上进行操作。这样就可以节省空间，提高效率。它的缺点是，它的排序结果是不稳定的，也就是说，如果序列中有相等的元素，它们的相对位置可能会改变。另外，它的时间复杂度是O(nlogn)，空间复杂度是O(1)，效率和空间都不是最优的。因此，如果要对一个序列进行排序，而且不需要保持元素的相对位置，也不需要额外的空间，可以使用qHeapSort函数，但是要注意是否有更好的算法。
  • qLowerBound和qUpperBound函数是两个查找函数，它们可以在一个有序的序列中，查找一个给定的元素的下界和上界。它们的优点是，它们的查找效率是对数级别的，也就是说，它们使用二分查找算法，每次查找都可以将查找范围缩小一半。这样就可以快速地找到目标元素。它们的缺点是，它们的查找结果是一个迭代器，它可以用来访问或者修改序列中的元素，也可以用来计算元素的位置或者个数，但是它不能直接用来判断元素是否存在于序列中，也不能直接用来获取元素的值。因此，如果要在一个有序的序列中，查找一个给定的元素的下界和上界，可以使用qLowerBound和qUpperBound函数，但是要注意如何使用查找结果。

 

原文地址:https://blog.csdn.net/qq_43445867/article/details/134431883

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_3082.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

上一篇 [架构之路-248]：目标系统 – 设计方法 – 软件工程 – 需求工程- 需求开发：如何用图形表达需求，结构化需求分析与面向对象需求分析的比较与融合
下一篇 内容运营常用的ChatGPT通用提示词模板

相关文章

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

插入图片
浏览器会保存昵称、邮箱和网站cookies信息，下次评论时使用。