C++如何使用模板实现通用排序算法

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // 为了方便，这里也引入std::sort做对比

// 通用冒泡排序函数模板
template <typename T>
void bubbleSort(std::vector<T>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            // 默认使用T类型的operator<进行比较
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// 也可以提供一个接受自定义比较器的版本，更通用
template <typename T, typename Compare>
void bubbleSortWithComparator(std::vector<T>& arr, Compare comp) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            // 使用传入的比较器进行比较
            if (comp(arr[j + 1], arr[j])) { // 如果arr[j+1]应该排在arr[j]前面
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// 辅助打印函数
template <typename T>
void printVector(const std::string& name, const std::vector<T>& arr) {
    std::cout << name << ": [";
    for (size_t i = 0; i < arr.size(); ++i) {
        std::cout << arr[i] << (i == arr.size() - 1 ? "" : ", ");
    }
    std::cout << "]" << std::endl;
}

int main() {
    // 整数排序
    std::vector<int> intVec = {5, 2, 8, 1, 9, 4};
    printVector("Original Integers", intVec);
    bubbleSort(intVec);
    printVector("Sorted Integers (Bubble)", intVec);
    std::cout << std::endl;

    // 字符串排序
    std::vector<std::string> strVec = {"banana", "apple", "grape", "cherry"};
    printVector("Original Strings", strVec);
    bubbleSort(strVec);
    printVector("Sorted Strings (Bubble)", strVec);
    std::cout << std::endl;

    // 使用自定义比较器进行降序排序（整数）
    std::vector<int> intVecDesc = {5, 2, 8, 1, 9, 4};
    printVector("Original Integers (Desc)", intVecDesc);
    // 使用lambda表达式作为比较器
    bubbleSortWithComparator(intVecDesc, [](int a, int b) { return a > b; });
    printVector("Sorted Integers (Bubble Desc)", intVecDesc);
    std::cout << std::endl;

    // 当然，实际项目中我们更倾向于使用STL提供的std::sort
    std::vector<double> doubleVec = {3.14, 1.618, 2.718, 0.577};
    printVector("Original Doubles", doubleVec);
    std::sort(doubleVec.begin(), doubleVec.end()); // std::sort也是模板函数
    printVector("Sorted Doubles (std::sort)", doubleVec);
    std::cout << std::endl;

    return 0;
}

template <typename T>

bubbleSort

>

bubbleSortWithComparator

int

sortInts

double

sortDoubles

std::string

sortStrings

Person

Product

void*

void*

Student

operator<

operator>

bubbleSort

// 自定义Student结构体
struct Student {
    std::string name;
    int score;

    // 重载小于运算符，实现按分数降序排序（分数越高，越“小”，排在前面）
    // 或者说，默认的std::sort会按升序排列，如果想分数高的排前面，
    // 那么这里定义的是“什么情况下a排在b前面”，即a.score > b.score
    bool operator<(const Student& other) const {
        return score > other.score; // 分数高的“小于”分数低的，这样std::sort会把分数高的放前面
    }

    // 为了方便打印
    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        os << "(" << s.name << ", " << s.score << ")";
        return os;
    }
};

int main() {
    std::vector<Student> students = {
        {"Alice", 90},
        {"Bob", 85},
        {"Charlie", 92},
        {"David", 88}
    };

    printVector("Original Students", students); // 使用上面定义的通用打印函数
    bubbleSort(students); // 使用重载的operator<进行排序
    printVector("Sorted Students (by score desc)", students);

    // 如果想按姓名升序，就需要自定义比较器了
    // ...
    return 0;
}

bubbleSortWithComparator

// 假设我们想按姓名升序排序
struct StudentNameAscComparator {
    bool operator()(const Student& a, const Student& b) const {
        return a.name < b.name;
    }
};

int main() {
    // ... (Student定义和初始化同上)

    std::vector<Student> studentsByName = {
        {"Alice", 90},
        {"Bob", 85},
        {"Charlie", 92},
        {"David", 88}
    };

    printVector("Original Students (for name sort)", studentsByName);
    // 使用函数对象作为比较器
    bubbleSortWithComparator(studentsByName, StudentNameAscComparator{});
    printVector("Sorted Students (by name asc)", studentsByName);
    std::cout << std::endl;

    // 也可以使用lambda表达式，更简洁
    std::vector<Student> studentsByScoreAsc = {
        {"Alice", 90},
        {"Bob", 85},
        {"Charlie", 92},
        {"David", 88}
    };
    printVector("Original Students (for score asc)", studentsByScoreAsc);
    bubbleSortWithComparator(studentsByScoreAsc, [](const Student& a, const Student& b) {
        return a.score < b.score; // 按分数升序
    });
    printVector("Sorted Students (by score asc)", studentsByScoreAsc);

    return 0;
}

std::enable_if

Concepts

void*

std::sort

std::sort