导言

快速排序是一种高效的分治排序算法，平均时间复杂度为 O (n log n)。使用 C++ 模板实现快速排序可以使其适用于各种数据类型，配合比较器还能灵活调整排序规则。

一、快速排序算法原理

快速排序的核心思想是：

  1. 选择一个元素作为 "基准"(pivot)
  2. 将数组分区，所有比基准值小的元素移到基准前面，比基准值大的元素移到基准后面
  3. 递归地对前后两个子数组进行排序

这种分治策略使快速排序成为实际应用中最快的排序算法之一。

二、模板类实现

下面是完整的MyQsort模板类实现，支持任意可比较的数据类型和自定义比较规则：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <vector>
#include <functional>
#include <iostream>

// 模板类声明，默认使用std::less<T>作为比较器
template<typename T, typename Compare = std::less<T>>
class MyQsort {
public:
    // 构造函数：接收数组和大小，初始化容器
    MyQsort(T* arr, size_t size, Compare com = Compare());
    
    // 快速排序入口函数
    void quick_sort();
    
    // 打印排序结果
    void print() const;

private:
    // 递归快速排序实现
    void quick(int left, int right, Compare& com);
    
    // 分区操作，返回基准元素的最终位置
    int partition(int left, int right, Compare& com);
    
    // 存储待排序元素的容器
    std::vector<T> _vec;
};

// 构造函数实现
template<typename T, typename Compare>
MyQsort<T, Compare>::MyQsort(T* arr, size_t size, Compare com) {
    if (arr && size > 0) {
        _vec.assign(arr, arr + size);
    }
}

// 快速排序入口
template<typename T, typename Compare>
void MyQsort<T, Compare>::quick_sort() {
    if (_vec.size() <= 1) return; // 空数组或单个元素无需排序
    Compare com;
    quick(0, _vec.size() - 1, com);
}

// 递归快速排序
template<typename T, typename Compare>
void MyQsort<T, Compare>::quick(int left, int right, Compare& com) {
    if (left < right) {
        // 进行分区操作，获取基准元素位置
        int pivot_pos = partition(left, right, com);
        // 递归排序左子数组
        quick(left, pivot_pos - 1, com);
        // 递归排序右子数组
        quick(pivot_pos + 1, right, com);
    }
}

// 分区操作
template<typename T, typename Compare>
int MyQsort<T, Compare>::partition(int left, int right, Compare& com) {
    // 选择最右边的元素作为基准
    T pivot = _vec[right];
    // i指向小于基准区域的最后一个元素
    int i = left - 1;
    
    // 遍历数组，将小于基准的元素移到左侧
    for (int j = left; j < right; ++j) {
        // 使用比较器判断元素是否应该放在基准左侧
        if (com(_vec[j], pivot)) {
            ++i;
            std::swap(_vec[i], _vec[j]);
        }
    }
    
    // 将基准元素放到正确位置
    std::swap(_vec[i + 1], _vec[right]);
    return i + 1; // 返回基准元素的位置
}

// 打印排序结果
template<typename T, typename Compare>
void MyQsort<T, Compare>::print() const {
    for (const auto& elem : _vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

三、使用示例

下面展示如何使用MyQsort类对不同数据类型进行排序，包括默认排序和自定义比较器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "my_qsort.h"
#include <functional>
#include <string>

// 测试基本数据类型排序
void test_int_sort() {
    std::cout << "=== 整数排序测试 ===" << std::endl;
    int arr[] = {5, 2, 9, 1, 5, 6};
    size_t size = sizeof(arr) / sizeof(arr[0]);
    
    // 默认升序排序
    MyQsort<int> qsort_asc(arr, size);
    qsort_asc.quick_sort();
    std::cout << "升序排序结果: ";
    qsort_asc.print();
    
    // 使用greater实现降序排序
    MyQsort<int, std::greater<int>> qsort_desc(arr, size);
    qsort_desc.quick_sort();
    std::cout << "降序排序结果: ";
    qsort_desc.print();
    std::cout << std::endl;
}

// 测试字符串排序
void test_string_sort() {
    std::cout << "=== 字符串排序测试 ===" << std::endl;
    std::string arr[] = {"apple", "banana", "cherry", "date", "blueberry"};
    size_t size = sizeof(arr) / sizeof(arr[0]);
    
    // 默认按字典序排序
    MyQsort<std::string> qsort_str(arr, size);
    qsort_str.quick_sort();
    std::cout << "字符串排序结果: ";
    qsort_str.print();
    std::cout << std::endl;
}

// 定义一个结构体用于测试
struct Student {
    std::string name;
    int age;
    
    Student(std::string n, int a) : name(std::move(n)), age(a) {}
};

// 测试结构体排序
void test_struct_sort() {
    std::cout << "=== 结构体排序测试 ===" << std::endl;
    Student students[] = {
        {"Alice", 20},
        {"Bob", 18},
        {"Charlie", 22},
        {"David", 19}
    };
    size_t size = sizeof(students) / sizeof(students[0]);
    
    // 自定义比较器：按年龄升序排序
    auto age_less = [](const Student& s1, const Student& s2) {
        return s1.age < s2.age;
    };
    
    MyQsort<Student, decltype(age_less)> qsort_stu(students, size, age_less);
    qsort_stu.quick_sort();
    
    std::cout << "按年龄排序结果: " << std::endl;
    // 这里需要修改print方法或者单独打印，因为Student没有默认输出运算符
    // 为简化示例，假设我们有合适的print实现
    std::cout << "(实现略：按年龄从小到大输出学生信息)" << std::endl;
}

int main() {
    test_int_sort();
    test_string_sort();
    test_struct_sort();
    return 0;
}

四、代码解析

4.1 模板参数说明

  • typename T：表示要排序的数据类型，可以是基本类型（int、double 等）或自定义类型
  • typename Compare = std::less：比较器类型，默认使用std::less实现升序排序

4.2 核心函数解析

  1. partition 函数：
    • 选择最右侧元素作为基准 (pivot)
    • 将所有小于基准的元素移到左侧，大于基准的元素移到右侧
    • 返回基准元素的最终位置，用于递归划分
  2. quick 函数：
    • 递归实现快速排序
    • 对分区后的左右子数组分别进行排序
  3. 构造函数：
    • 接收原始数组和大小
    • 使用 vector 存储元素，方便管理和访问

五、编译与运行

运行结果：

1
2
3
4
5
6
7
8
9
10
=== 整数排序测试 ===
升序排序结果: 1 2 5 5 6 9 
降序排序结果: 9 6 5 5 2 1 

=== 字符串排序测试 ===
字符串排序结果: apple banana blueberry cherry date 

=== 结构体排序测试 ===
按年龄排序结果:
(实现略：按年龄从小到大输出学生信息)

六、性能分析

  • 时间复杂度：
    • 平均情况：O (n log n)
    • 最坏情况：O (n²)（可通过合理选择基准元素优化）
    • 最好情况：O (n log n)
  • 空间复杂度：O (log n) ~ O (n)，主要来自递归调用栈
  • 稳定性：本实现是非稳定排序，相等元素的相对位置可能改变

七、优化建议

  1. 基准元素选择：可以使用三数取中法（首、中、尾三个元素的中值）作为基准，避免最坏情况
  2. 小规模数组优化：对小于一定阈值（如 10-20 个元素）的子数组使用插入排序，提高实际运行效率
  3. 尾递归优化：将其中一个递归调用改为循环，减少栈空间使用
  4. 处理重复元素：使用三路快排（将数组分为小于、等于、大于基准三部分），优化含大量重复元素的数组排序