C++泛型快速排序比较器配置问题及代码实现求助

我太懂你在实现Goodrich那本《Data Structures and Algorithms in C++》里的泛型快速排序时的头疼了——尤其是用自定义比较器这块，泛型参数稍不注意就容易出问题。先把你给出的代码补全，再把关键细节给你掰扯清楚。

首先，先把你贴的部分代码放出来：

#include <iostream>
#include <vector>
#include <functional>
template <typename E, typename C> // quick-sort S
void quickSort(std::vector<E>& S, const C& less) {
    if (S.size() <= 1) {return;}
    // 代码未完整展示的内容
}

快速排序的核心是**分区（partition）**步骤，我们需要先实现一个辅助的分区函数，用传入的less比较器来判断元素的大小关系。下面是完整的实现：

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm> // 用于swap，也可以自己实现

// 辅助分区函数：返回基准元素的最终位置
template <typename E, typename C>
int partition(std::vector<E>& S, int low, int high, const C& less) {
    // 选中间元素作为基准，避免最坏时间复杂度（比如已经有序的数组）
    int mid = low + (high - low) / 2;
    std::swap(S[mid], S[high]); // 把基准移到末尾
    E pivot = S[high];
    int i = low - 1; // 记录小于基准的区域的最后一个位置

    for (int j = low; j < high; ++j) {
        // 使用传入的比较器判断：如果S[j]小于基准，就放到左边区域
        if (less(S[j], pivot)) {
            ++i;
            std::swap(S[i], S[j]);
        }
    }
    // 把基准移到正确的位置
    std::swap(S[i + 1], S[high]);
    return i + 1;
}

// 递归辅助函数，处理数组的[low, high]范围
template <typename E, typename C>
void quickSortHelper(std::vector<E>& S, int low, int high, const C& less) {
    if (low < high) {
        int pivotIdx = partition(S, low, high, less);
        // 递归排序左半部分
        quickSortHelper(S, low, pivotIdx - 1, less);
        // 递归排序右半部分
        quickSortHelper(S, pivotIdx + 1, high, less);
    }
}

// 快速排序主函数
template <typename E, typename C>
void quickSort(std::vector<E>& S, const C& less) {
    if (S.size() <= 1) {
        return;
    }
    // 调用递归的重载版本，处理指定范围
    quickSortHelper(S, 0, S.size() - 1, less);
}

// 测试代码
int main() {
    // 测试int类型，升序排序
    std::vector<int> nums = {5, 2, 9, 1, 5, 6};
    std::cout << "排序前：";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    // 使用std::less<int>()作为比较器
    quickSort(nums, std::less<int>());

    std::cout << "升序排序后：";
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    // 测试自定义降序比较器
    std::vector<int> nums2 = {5, 2, 9, 1, 5, 6};
    quickSort(nums2, [](int a, int b) { return a > b; }); // lambda作为比较器

    std::cout << "降序排序后：";
    for (int num : nums2) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    return 0;
}

这里要注意几个容易踩坑的点：

• 比较器的使用：全程用传入的less(a, b)来判断元素关系，不要直接用<或者>，这样才能兼容任意元素类型和自定义排序规则
• 基准选择：选中间元素而不是第一个/最后一个，能避免数组已经有序时的O(n²)最坏时间复杂度
• 递归范围：用辅助函数处理指定的[low, high]范围，比每次分割数组更高效（不用额外创建子数组）
• 泛型兼容性：只要元素类型E支持比较器C的操作，就能正常工作——比如你可以排序自定义的Person类，只要传入对应的比较器（比如按年龄、姓名排序）

比如如果要排序自定义类，示例如下：

struct Person {
    std::string name;
    int age;
};

// 按年龄升序的比较器
struct AgeLess {
    bool operator()(const Person& a, const Person& b) {
        return a.age < b.age;
    }
};

// 调用方式
std::vector<Person> people = {{"Alice", 25}, {"Bob", 20}, {"Charlie", 30}};
quickSort(people, AgeLess());

这样就能完美实现书中的泛型快速排序逻辑啦～

内容的提问来源于stack exchange，提问作者I Like