第一章：排序函數(shù)的概述

排序函數(shù)是一種在編程中常用的函數(shù)，它可以對(duì)一個(gè)序列（如數(shù)組，列表，向量等）中的元素進(jìn)行排序，使其按照一定的順序排列。排序函數(shù)可以根據(jù)不同的排序算法，如冒泡排序，選擇排序，插入排序，快速排序，歸并排序，堆排序等，實(shí)現(xiàn)不同的排序效果。排序函數(shù)的作用有以下幾點(diǎn)：

• 提高查找效率。當(dāng)一個(gè)序列中的元素是有序的，就可以使用一些高效的查找算法，如二分查找，插值查找，斐波那契查找等，來(lái)快速地找到目標(biāo)元素。
• 方便數(shù)據(jù)分析。當(dāng)一個(gè)序列中的元素是有序的，就可以方便地進(jìn)行一些數(shù)據(jù)分析，如求最大值，最小值，中位數(shù)，眾數(shù)，分位數(shù)，頻率分布，直方圖等。
• 增加數(shù)據(jù)可讀性。當(dāng)一個(gè)序列中的元素是有序的，就可以增加數(shù)據(jù)的可讀性，使其更容易被人理解和比較。

QT是一個(gè)跨平臺(tái)的應(yīng)用程序開(kāi)發(fā)框架，它提供了一些常用的排序函數(shù)，可以對(duì)QT中的一些容器類（如QList，QVector，QMap，QSet等）中的元素進(jìn)行排序。QT中提供的排序函數(shù)有以下幾種：

• qSort：這是一個(gè)通用的排序函數(shù)，它使用快速排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行排序。它可以指定一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象，來(lái)自定義排序的規(guī)則。它的排序結(jié)果是不穩(wěn)定的，也就是說(shuō)，如果序列中有相等的元素，它們的相對(duì)位置可能會(huì)改變。
• qStableSort：這是一個(gè)穩(wěn)定的排序函數(shù)，它使用歸并排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行排序。它可以指定一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象，來(lái)自定義排序的規(guī)則。它的排序結(jié)果是穩(wěn)定的，也就是說(shuō)，如果序列中有相等的元素，它們的相對(duì)位置不會(huì)改變。
• qPartialSort：這是一個(gè)部分排序函數(shù)，它使用堆排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行部分排序。它可以指定一個(gè)范圍，只對(duì)序列中的這個(gè)范圍內(nèi)的元素進(jìn)行排序，而不影響其他元素。它可以指定一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象，來(lái)自定義排序的規(guī)則。它的排序結(jié)果是不穩(wěn)定的。
• qHeapSort：這是一個(gè)堆排序函數(shù)，它使用堆排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行排序。它可以指定一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象，來(lái)自定義排序的規(guī)則。它的排序結(jié)果是不穩(wěn)定的。它的特點(diǎn)是，它可以在不使用額外空間的情況下，對(duì)序列進(jìn)行原地排序，也就是說(shuō)，它不需要?jiǎng)?chuàng)建一個(gè)新的序列來(lái)存儲(chǔ)排序結(jié)果，而是直接在原序列上進(jìn)行操作。
• qLowerBound和qUpperBound：這不是排序函數(shù)，而是查找函數(shù)，它們可以在一個(gè)有序的序列中，查找一個(gè)給定的元素的下界和上界。下界是指序列中第一個(gè)不小于給定元素的位置，上界是指序列中第一個(gè)大于給定元素的位置。它們可以指定一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象，來(lái)自定義查找的規(guī)則。它們的查找效率是對(duì)數(shù)級(jí)別的，也就是說(shuō)，它們使用二分查找算法，每次查找都可以將查找范圍縮小一半。

第二章：qSort函數(shù)

qSort函數(shù)是QT中提供的一個(gè)通用的排序函數(shù)，它使用快速排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行排序?？焖倥判蛩惴ǖ幕舅枷胧?，選擇一個(gè)基準(zhǔn)元素，將序列分為兩個(gè)子序列，一個(gè)子序列中的元素都小于或等于基準(zhǔn)元素，另一個(gè)子序列中的元素都大于基準(zhǔn)元素，然后對(duì)這兩個(gè)子序列遞歸地進(jìn)行快速排序，最后將兩個(gè)子序列合并成一個(gè)有序的序列。快速排序算法的平均時(shí)間復(fù)雜度是O(nlogn)，最壞情況下的時(shí)間復(fù)雜度是O(n^2)，空間復(fù)雜度是O(logn)。

qSort函數(shù)的函數(shù)原型如下

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

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

qSort函數(shù)的功能參數(shù)

對(duì)從begin到end（不包括end）的元素進(jìn)行排序。

第一個(gè)參數(shù)begin是指向序列開(kāi)始位置的迭代器

第二個(gè)參數(shù)end是指向序列結(jié)束位置的迭代器

第三個(gè)參數(shù)lessThan是一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象，它可以自定義排序的規(guī)則，它接受兩個(gè)元素作為參數(shù)，返回一個(gè)布爾值，表示第一個(gè)元素是否小于第二個(gè)元素。如果沒(méi)有指定第三個(gè)參數(shù)，qSort函數(shù)會(huì)使用默認(rèn)的比較規(guī)則，即使用元素的<運(yùn)算符進(jìn)行比較。

qSort函數(shù)的用法示例

• 如果要對(duì)一個(gè)數(shù)組進(jìn)行排序，可以直接傳入數(shù)組的首地址和尾地址作為參數(shù)，例如：

int arr[] = {5, 3, 7, 1, 9, 4, 6, 8, 2};
qSort(arr, arr + 9); // 對(duì)arr數(shù)組進(jìn)行升序排序

• 如果要對(duì)一個(gè)QList或者QVector進(jìn)行排序，可以使用它們的begin()和end()方法來(lái)獲取迭代器，例如：

QList<int> list;
list << 5 << 3 << 7 << 1 << 9 << 4 << 6 << 8 << 2;
qSort(list.begin(), list.end()); // 對(duì)list進(jìn)行升序排序

• 如果要對(duì)一個(gè)QMap或者QSet進(jìn)行排序，可以使用它們的keys()或者values()方法來(lái)獲取一個(gè)QList，然后對(duì)QList進(jìn)行排序，例如：

QMap<QString, int> map;
map["Alice"] = 90;
map["Bob"] = 80;
map["Charlie"] = 85;
map["David"] = 95;
QList<QString> names = map.keys(); // 獲取map的鍵的列表
qSort(names.begin(), names.end()); // 對(duì)names進(jìn)行升序排序

• 如果要自定義排序的規(guī)則，可以傳入一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象作為第三個(gè)參數(shù)，例如：

// 定義一個(gè)比較函數(shù)，按照字符串的長(zhǎng)度進(jìn)行比較
bool compareByLength(const QString &a, const QString &b)
{
    return a.length() < b.length();
}

// 定義一個(gè)比較對(duì)象，按照學(xué)生的成績(jī)進(jìn)行比較
struct compareByScore
{
    bool operator()(const Student &a, const Student &b)
    {
        return a.score > b.score; // 降序排序
    }
};

QList<QString> words;
words << "apple" << "banana" << "orange" << "pear" << "grape";
qSort(words.begin(), words.end(), compareByLength); // 按照單詞的長(zhǎng)度進(jìn)行升序排序

QList<Student> students;
students << Student("Alice", 90) << Student("Bob", 80) << Student("Charlie", 85) << Student("David", 95);
qSort(students.begin(), students.end(), compareByScore()); // 按照學(xué)生的成績(jī)進(jìn)行降序排序

qSort函數(shù)注意事項(xiàng)

• begin和end必須指向同一個(gè)序列，否則會(huì)導(dǎo)致未定義的行為。
• begin和end之間的元素必須能夠被交換，否則會(huì)導(dǎo)致編譯錯(cuò)誤。
• begin和end之間的元素必須能夠被比較，否則會(huì)導(dǎo)致編譯錯(cuò)誤或者運(yùn)行時(shí)錯(cuò)誤。
• lessThan必須是一個(gè)嚴(yán)格弱序關(guān)系，也就是說(shuō)，它必須滿足以下條件：
  • 對(duì)于任何元素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函數(shù)的排序結(jié)果是不穩(wěn)定的，也就是說(shuō)，如果序列中有相等的元素（即lessThan(x, y)和lessThan(y, x)都返回false），它們的相對(duì)位置可能會(huì)改變。

以上就是qSort函數(shù)的介紹，下面我們將介紹qStableSort函數(shù)。

第三章：qStableSort函數(shù)

qStableSort函數(shù)是QT中提供的一個(gè)穩(wěn)定的排序函數(shù)，它使用歸并排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行排序。歸并排序算法的基本思想是，將序列分為兩個(gè)子序列，對(duì)這兩個(gè)子序列分別進(jìn)行歸并排序，然后將兩個(gè)有序的子序列合并成一個(gè)有序的序列。歸并排序算法的時(shí)間復(fù)雜度是O(nlogn)，空間復(fù)雜度是O(n)。

qStableSort函數(shù)的函數(shù)原型如下

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

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

qStableSort函數(shù)的功能參數(shù)

對(duì)從begin到end（不包括end）的元素進(jìn)行排序

第一個(gè)參數(shù)begin是指向序列開(kāi)始位置的迭代器

第二個(gè)參數(shù)end是指向序列結(jié)束位置的迭代器

第三個(gè)參數(shù)lessThan是一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象，它可以自定義排序的規(guī)則，它接受兩個(gè)元素作為參數(shù)，返回一個(gè)布爾值，表示第一個(gè)元素是否小于第二個(gè)元素。如果沒(méi)有指定第三個(gè)參數(shù)，qStableSort函數(shù)會(huì)使用默認(rèn)的比較規(guī)則，即使用元素的<運(yùn)算符進(jìn)行比較。

qStableSort函數(shù)的用法示例

qStableSort函數(shù)的用法和qSort函數(shù)的用法基本相同，只是qStableSort函數(shù)的排序結(jié)果是穩(wěn)定的，也就是說(shuō)，如果序列中有相等的元素（即lessThan(x, y)和lessThan(y, x)都返回false），它們的相對(duì)位置不會(huì)改變。這一點(diǎn)在一些場(chǎng)景中是很重要的，例如，如果要對(duì)一個(gè)學(xué)生的列表按照姓名進(jìn)行排序，然后再按照成績(jī)進(jìn)行排序，如果使用qSort函數(shù)，那么姓名相同的學(xué)生的成績(jī)順序可能會(huì)被打亂，而如果使用qStableSort函數(shù)，那么姓名相同的學(xué)生的成績(jī)順序會(huì)保持不變。

代碼示例：

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

// 定義一個(gè)學(xué)生類，包含姓名和成績(jī)兩個(gè)屬性
class Student
{
public:
    Student(const QString &name, int score) : name(name), score(score) {}
    QString name; // 姓名
    int score; // 成績(jī)
};

// 定義一個(gè)比較函數(shù)，按照姓名進(jìn)行升序排序
bool compareByName(const Student &a, const Student &b)
{
    return a.name < b.name;
}

// 定義一個(gè)比較函數(shù)，按照成績(jī)進(jìn)行降序排序
bool compareByScore(const Student &a, const Student &b)
{
    return a.score > b.score;
}

// 創(chuàng)建一個(gè)學(xué)生的列表
    QList<Student> students;
    students << Student("Alice", 90) << Student("Bob", 80) << Student("Charlie", 85) << Student("David", 95) << Student("Alice", 88) << Student("Bob", 82);

    // 使用qStableSort函數(shù)按照姓名進(jìn)行排序
    qStableSort(students.begin(), students.end(), compareByName);

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

    // 使用qStableSort函數(shù)按照成績(jī)進(jìn)行排序
    qStableSort(students.begin(), students.end(), compareByScore);

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

運(yùn)行這段代碼，可以得到以下輸出：

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函數(shù)的排序結(jié)果是穩(wěn)定的，也就是說(shuō)，姓名相同的學(xué)生的成績(jī)順序沒(méi)有改變，而是保持了原來(lái)的順序。這樣就可以方便地對(duì)數(shù)據(jù)進(jìn)行分組或者分析。

qStableSort函數(shù)注意事項(xiàng)

• begin和end必須指向同一個(gè)序列，否則會(huì)導(dǎo)致未定義的行為。
• begin和end之間的元素必須能夠被交換，否則會(huì)導(dǎo)致編譯錯(cuò)誤。
• begin和end之間的元素必須能夠被比較，否則會(huì)導(dǎo)致編譯錯(cuò)誤或者運(yùn)行時(shí)錯(cuò)誤。
• lessThan必須是一個(gè)嚴(yán)格弱序關(guān)系，也就是說(shuō)，它必須滿足以下條件：
  • 對(duì)于任何元素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函數(shù)的排序結(jié)果是穩(wěn)定的，也就是說(shuō)，如果序列中有相等的元素，它們的相對(duì)位置不會(huì)改變。

以上就是qStableSort函數(shù)的介紹，下面我們將介紹qPartialSort函數(shù)

第四章：qPartialSort函數(shù)

qPartialSort函數(shù)是QT中提供的一個(gè)部分排序函數(shù)，它使用堆排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行部分排序。堆排序算法的基本思想是，將序列視為一個(gè)完全二叉樹(shù)，然后構(gòu)建一個(gè)最大堆或者最小堆，也就是說(shuō)，每個(gè)節(jié)點(diǎn)的值都大于或者小于它的子節(jié)點(diǎn)的值。然后，將堆的根節(jié)點(diǎn)（也就是最大或者最小的元素）與堆的最后一個(gè)節(jié)點(diǎn)交換，然后將堆的大小減一，再調(diào)整堆的結(jié)構(gòu)，重復(fù)這個(gè)過(guò)程，直到堆的大小等于指定的范圍。堆排序算法的時(shí)間復(fù)雜度是O(nlogn)，空間復(fù)雜度是O(1)。

qPartialSort函數(shù)的函數(shù)原型

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函數(shù)的功能參數(shù)

對(duì)從begin到end（不包括end）的元素進(jìn)行部分排序，使得從begin到middle（不包括middle）的元素是最小的或者最大的，而且是有序的，而從middle到end的元素是無(wú)序的。

第一個(gè)參數(shù)begin是指向序列開(kāi)始位置的迭代器

第二個(gè)參數(shù)middle是指向序列中間位置的迭代器

第三個(gè)參數(shù)end是指向序列結(jié)束位置的迭代器

第四個(gè)參數(shù)lessThan是一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象，它可以自定義排序的規(guī)則，它接受兩個(gè)元素作為參數(shù)，返回一個(gè)布爾值，表示第一個(gè)元素是否小于第二個(gè)元素。如果沒(méi)有指定第四個(gè)參數(shù)，qPartialSort函數(shù)會(huì)使用默認(rèn)的比較規(guī)則，即使用元素的<運(yùn)算符進(jìn)行比較。

qPartialSort函數(shù)的用法示例

• 如果要對(duì)一個(gè)數(shù)組進(jìn)行部分排序，可以直接傳入數(shù)組的首地址，中間地址和尾地址作為參數(shù)，例如：

int arr[] = {5, 3, 7, 1, 9, 4, 6, 8, 2};
qPartialSort(arr, arr + 3, arr + 9); // 對(duì)arr數(shù)組進(jìn)行部分排序，使得前三個(gè)元素是最小的，并且是有序的

• 如果要對(duì)一個(gè)QList或者QVector進(jìn)行部分排序，可以使用它們的begin()和end()方法來(lái)獲取迭代器，例如：

QList<int> list;
list << 5 << 3 << 7 << 1 << 9 << 4 << 6 << 8 << 2;
qPartialSort(list.begin(), list.begin() + 3, list.end()); // 對(duì)list進(jìn)行部分排序，使得前三個(gè)元素是最小的，并且是有序的

• 如果要對(duì)一個(gè)QMap或者QSet進(jìn)行部分排序，可以使用它們的keys()或者values()方法來(lái)獲取一個(gè)QList，然后對(duì)QList進(jìn)行部分排序，例如：

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()); // 對(duì)scores進(jìn)行部分排序，使得前兩個(gè)元素是最小的，并且是有序的

• 如果要自定義排序的規(guī)則，可以傳入一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象作為第四個(gè)參數(shù)，例如：

// 定義一個(gè)比較函數(shù)，按照字符串的長(zhǎng)度進(jìn)行比較
bool compareByLength(const QString &a, const QString &b)
{
    return a.length() < b.length();
}

// 定義一個(gè)比較對(duì)象，按照學(xué)生的成績(jī)進(jìn)行比較
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); // 按照單詞的長(zhǎng)度進(jìn)行部分排序，使得前兩個(gè)元素是最短的，并且是有序的

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()); // 按照學(xué)生的成績(jī)進(jìn)行部分排序，使得前兩個(gè)元素是最高的，并且是有序的

qPartialSort函數(shù)注意事項(xiàng)

• begin，middle和end必須指向同一個(gè)序列，否則會(huì)導(dǎo)致未定義的行為。
• begin，middle和end之間的元素必須能夠被交換，否則會(huì)導(dǎo)致編譯錯(cuò)誤。
• begin，middle和end之間的元素必須能夠被比較，否則會(huì)導(dǎo)致編譯錯(cuò)誤或者運(yùn)行時(shí)錯(cuò)誤。
• lessThan必須是一個(gè)嚴(yán)格弱序關(guān)系，也就是說(shuō)，它必須滿足以下條件：
  • 對(duì)于任何元素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函數(shù)的排序結(jié)果是不穩(wěn)定的，也就是說(shuō)，如果序列中有相等的元素，它們的相對(duì)位置可能會(huì)改變。

以上就是qPartialSort函數(shù)的介紹，下面我們將介紹qHeapSort函數(shù)。

第五章：qHeapSort函數(shù)

qHeapSort函數(shù)是QT中提供的一個(gè)堆排序函數(shù)，它使用堆排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行排序。堆排序算法的基本思想是，將序列視為一個(gè)完全二叉樹(shù)，然后構(gòu)建一個(gè)最大堆或者最小堆，也就是說(shuō)，每個(gè)節(jié)點(diǎn)的值都大于或者小于它的子節(jié)點(diǎn)的值。然后，將堆的根節(jié)點(diǎn)（也就是最大或者最小的元素）與堆的最后一個(gè)節(jié)點(diǎn)交換，然后將堆的大小減一，再調(diào)整堆的結(jié)構(gòu)，重復(fù)這個(gè)過(guò)程，直到堆的大小為零。堆排序算法的時(shí)間復(fù)雜度是O(nlogn)，空間復(fù)雜度是O(1)。

qHeapSort函數(shù)的函數(shù)原型

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

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

qHeapSort函數(shù)的功能是參數(shù)

對(duì)從begin到end（不包括end）的元素進(jìn)行排序。

第一個(gè)參數(shù)begin是指向序列開(kāi)始位置的迭代器

第二個(gè)參數(shù)end是指向序列結(jié)束位置的迭代器

第三個(gè)參數(shù)lessThan是一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象，它可以自定義排序的規(guī)則，它接受兩個(gè)元素作為參數(shù)，返回一個(gè)布爾值，表示第一個(gè)元素是否小于第二個(gè)元素。如果沒(méi)有指定第三個(gè)參數(shù)，qHeapSort函數(shù)會(huì)使用默認(rèn)的比較規(guī)則，即使用元素的<運(yùn)算符進(jìn)行比較。

qHeapSort函數(shù)的用法示例

qSort函數(shù)的用法基本相同，只是qHeapSort函數(shù)的特點(diǎn)是，它可以在不使用額外空間的情況下，對(duì)序列進(jìn)行原地排序，也就是說(shuō)，它不需要?jiǎng)?chuàng)建一個(gè)新的序列來(lái)存儲(chǔ)排序結(jié)果，而是直接在原序列上進(jìn)行操作。這樣就可以節(jié)省空間，提高效率。

代碼示例：

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

// 定義一個(gè)學(xué)生類，包含姓名和成績(jī)兩個(gè)屬性
class Student
{
public:
    Student(const QString &name, int score) : name(name), score(score) {}
    QString name; // 姓名
    int score; // 成績(jī)
};

// 定義一個(gè)比較函數(shù)，按照姓名進(jìn)行升序排序
bool compareByName(const Student &a, const Student &b)
{
    return a.name < b.name;
}

// 定義一個(gè)比較函數(shù)，按照成績(jī)進(jìn)行降序排序
bool compareByScore(const Student &a, const Student &b)
{
    return a.score > b.score;
}
    // 創(chuàng)建一個(gè)學(xué)生的列表
    QList<Student> students;
    students << Student("Alice", 90) << Student("Bob", 80) << Student("Charlie", 85) << Student("David", 95);

    // 使用qHeapSort函數(shù)按照姓名進(jìn)行排序
    qHeapSort(students.begin(), students.end(), compareByName);

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

    // 使用qHeapSort函數(shù)按照成績(jī)進(jìn)行排序
    qHeapSort(students.begin(), students.end(), compareByScore);

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

 運(yùn)行這段代碼，可以得到以下輸出：

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

可以看到，qHeapSort函數(shù)的排序結(jié)果是不穩(wěn)定的，也就是說(shuō)，姓名相同的學(xué)生的成績(jī)順序可能會(huì)改變，而且它可以在不使用額外空間的情況下，對(duì)序列進(jìn)行原地排序，也就是說(shuō)，它不需要?jiǎng)?chuàng)建一個(gè)新的序列來(lái)存儲(chǔ)排序結(jié)果，而是直接在原序列上進(jìn)行操作。

qHeapSort函數(shù)的注意事項(xiàng)

• begin和end必須指向同一個(gè)序列，否則會(huì)導(dǎo)致未定義的行為。
• begin和end之間的元素必須能夠被交換，否則會(huì)導(dǎo)致編譯錯(cuò)誤。
• begin和end之間的元素必須能夠被比較，否則會(huì)導(dǎo)致編譯錯(cuò)誤或者運(yùn)行時(shí)錯(cuò)誤。
• lessThan必須是一個(gè)嚴(yán)格弱序關(guān)系，也就是說(shuō)，它必須滿足以下條件：
  • 對(duì)于任何元素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函數(shù)的排序結(jié)果是不穩(wěn)定的，也就是說(shuō)，如果序列中有相等的元素，它們的相對(duì)位置可能會(huì)改變。

以上就是qHeapSort函數(shù)的介紹，下面我們將介紹qLowerBound和qUpperBound函數(shù)。

第六章：qLowerBound和qUpperBound函數(shù)

qLowerBound和qUpperBound函數(shù)是QT中提供的兩個(gè)查找函數(shù)，它們可以在一個(gè)有序的序列中，查找一個(gè)給定的元素的下界和上界。下界是指序列中第一個(gè)不小于給定元素的位置，上界是指序列中第一個(gè)大于給定元素的位置。它們可以指定一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象，來(lái)自定義查找的規(guī)則。它們的查找效率是對(duì)數(shù)級(jí)別的，也就是說(shuō)，它們使用二分查找算法，每次查找都可以將查找范圍縮小一半。

qLowerBound和qUpperBound函數(shù)的函數(shù)原型

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函數(shù)的功能和參數(shù)

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

第一個(gè)參數(shù)begin是指向序列開(kāi)始位置的迭代器

第二個(gè)參數(shù)end是指向序列結(jié)束位置的迭代器

第三個(gè)參數(shù)value是要查找的元素

第四個(gè)參數(shù)lessThan是一個(gè)比較函數(shù)或者一個(gè)比較對(duì)象，它可以自定義查找的規(guī)則，它接受兩個(gè)元素作為參數(shù)，返回一個(gè)布爾值，表示第一個(gè)元素是否小于第二個(gè)元素。如果沒(méi)有指定第四個(gè)參數(shù)，qLowerBound和qUpperBound函數(shù)會(huì)使用默認(rèn)的比較規(guī)則，即使用元素的<運(yùn)算符進(jìn)行比較。

qLowerBound和qUpperBound函數(shù)的用法示例

• 如果要在一個(gè)數(shù)組中查找一個(gè)元素的下界和上界，可以直接傳入數(shù)組的首地址和尾地址作為參數(shù)，例如：

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的上界的索引

• 如果要在一個(gè)QList或者QVector中查找一個(gè)元素的下界和上界，可以使用它們的begin()和end()方法來(lái)獲取迭代器，例如：

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的上界的索引

• 如果要在一個(gè)QMap或者QSet中查找一個(gè)元素的下界和上界，可以使用它們的keys()或者values()方法來(lái)獲取一個(gè)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()); // 對(duì)scores進(jìn)行排序
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的上界的索引

第七章：總結(jié)

本文介紹了QT中的幾種常用的排序函數(shù)，包括qSort，qStableSort，qPartialSort，qHeapSort，qLowerBound和qUpperBound，它們可以對(duì)QT中的一些容器類中的元素進(jìn)行排序或者查找。

下面我們將比較一下不同排序函數(shù)的優(yōu)缺點(diǎn)，以及給出一些使用建議：

• qSort函數(shù)是一個(gè)通用的排序函數(shù)，它使用快速排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行排序。它的優(yōu)點(diǎn)是，它的平均時(shí)間復(fù)雜度是O(nlogn)，空間復(fù)雜度是O(logn)，效率較高。它的缺點(diǎn)是，它的最壞情況下的時(shí)間復(fù)雜度是O(n^2)，效率較低。另外，它的排序結(jié)果是不穩(wěn)定的，也就是說(shuō)，如果序列中有相等的元素，它們的相對(duì)位置可能會(huì)改變。因此，如果要對(duì)一個(gè)序列進(jìn)行排序，可以使用qSort函數(shù)，但是要注意避免最壞情況的發(fā)生，以及考慮是否需要保持元素的相對(duì)位置。
• qStableSort函數(shù)是一個(gè)穩(wěn)定的排序函數(shù)，它使用歸并排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行排序。它的優(yōu)點(diǎn)是，它的時(shí)間復(fù)雜度是O(nlogn)，效率較高。另外，它的排序結(jié)果是穩(wěn)定的，也就是說(shuō)，如果序列中有相等的元素，它們的相對(duì)位置不會(huì)改變。這一點(diǎn)在一些場(chǎng)景中是很重要的，例如，如果要對(duì)一個(gè)學(xué)生的列表按照姓名進(jìn)行排序，然后再按照成績(jī)進(jìn)行排序，如果使用qSort函數(shù)，那么姓名相同的學(xué)生的成績(jī)順序可能會(huì)被打亂，而如果使用qStableSort函數(shù)，那么姓名相同的學(xué)生的成績(jī)順序會(huì)保持不變。它的缺點(diǎn)是，它的空間復(fù)雜度是O(n)，需要額外的空間來(lái)存儲(chǔ)排序結(jié)果。因此，如果要對(duì)一個(gè)序列進(jìn)行排序，而且需要保持元素的相對(duì)位置，可以使用qStableSort函數(shù)，但是要注意空間的消耗。
• qPartialSort函數(shù)是一個(gè)部分排序函數(shù)，它使用堆排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行部分排序。它的優(yōu)點(diǎn)是，它可以指定一個(gè)范圍，只對(duì)序列中的這個(gè)范圍內(nèi)的元素進(jìn)行排序，而不影響其他元素。這樣就可以節(jié)省時(shí)間，提高效率。它的缺點(diǎn)是，它的排序結(jié)果是不穩(wěn)定的，也就是說(shuō)，如果序列中有相等的元素，它們的相對(duì)位置可能會(huì)改變。另外，它的時(shí)間復(fù)雜度是O(nlogn)，空間復(fù)雜度是O(1)，效率和空間都不是最優(yōu)的。因此，如果要對(duì)一個(gè)序列進(jìn)行部分排序，可以使用qPartialSort函數(shù)，但是要注意元素的相對(duì)位置，以及是否有更好的算法。
• qHeapSort函數(shù)是一個(gè)堆排序函數(shù)，它使用堆排序算法，可以對(duì)任何可隨機(jī)訪問(wèn)的序列進(jìn)行排序。它的優(yōu)點(diǎn)是，它可以在不使用額外空間的情況下，對(duì)序列進(jìn)行原地排序，也就是說(shuō)，它不需要?jiǎng)?chuàng)建一個(gè)新的序列來(lái)存儲(chǔ)排序結(jié)果，而是直接在原序列上進(jìn)行操作。這樣就可以節(jié)省空間，提高效率。它的缺點(diǎn)是，它的排序結(jié)果是不穩(wěn)定的，也就是說(shuō)，如果序列中有相等的元素，它們的相對(duì)位置可能會(huì)改變。另外，它的時(shí)間復(fù)雜度是O(nlogn)，空間復(fù)雜度是O(1)，效率和空間都不是最優(yōu)的。因此，如果要對(duì)一個(gè)序列進(jìn)行排序，而且不需要保持元素的相對(duì)位置，也不需要額外的空間，可以使用qHeapSort函數(shù)，但是要注意是否有更好的算法。
• qLowerBound和qUpperBound函數(shù)是兩個(gè)查找函數(shù)，它們可以在一個(gè)有序的序列中，查找一個(gè)給定的元素的下界和上界。它們的優(yōu)點(diǎn)是，它們的查找效率是對(duì)數(shù)級(jí)別的，也就是說(shuō)，它們使用二分查找算法，每次查找都可以將查找范圍縮小一半。這樣就可以快速地找到目標(biāo)元素。它們的缺點(diǎn)是，它們的查找結(jié)果是一個(gè)迭代器，它可以用來(lái)訪問(wèn)或者修改序列中的元素，也可以用來(lái)計(jì)算元素的位置或者個(gè)數(shù)，但是它不能直接用來(lái)判斷元素是否存在于序列中，也不能直接用來(lái)獲取元素的值。因此，如果要在一個(gè)有序的序列中，查找一個(gè)給定的元素的下界和上界，可以使用qLowerBound和qUpperBound函數(shù)，但是要注意如何使用查找結(jié)果。

到此這篇關(guān)于QT中幾種常用的排序函數(shù)用法總結(jié)的文章就介紹到這了,更多相關(guān)QT排序函數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論