C++学习笔记-排序

 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

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int main()
{
    std::vector<int> values = {3, 8, 1, 4, 2, 6};
    
    std::cout << "Original: ";
    for (int val : values) std::cout << val << " ";
    std::cout << std::endl;
    
    // 默认升序排序
    std::vector<int> ascending = values;
    std::sort(ascending.begin(), ascending.end()); // 如果不提供任何谓词，那么它将按照默认从小到大排序
    
    std::cout << "Ascending: ";
    for (int val : ascending) std::cout << val << " ";
    std::cout << std::endl;
    
    // 使用std::greater降序排序
    std::vector<int> descending = values;
    std::sort(descending.begin(), descending.end(), std::greater<int>()); // std::greater<int>() 从大到小
    
    std::cout << "Descending: ";
    for (int val : descending) std::cout << val << " ";
    std::cout << std::endl;
    
    return 0;
}

 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

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> values = {3, 8, 1, 4, 2, 6};
    
    // 使用Lambda表达式自定义排序
    std::sort(values.begin(), values.end(), [](int a, int b)
    {
        /*
         * 比较函数返回一个bool值
         * 如果你想让第一个参数排在前面的话，返回true，否则返回false
         */
        if (a == 1)
            return false;  // 1不排在前面
        if (b == 1)
            return true;   // 其他数字排在1前面
        
        return a < b; // 其余按升序排列
    });
    
    std::cout << "Custom sort (1 at end): ";
    for (int val : values) std::cout << val << " ";
    std::cout << std::endl;
    
    return 0;
}

 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

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Student
{
    std::string name;
    int age;
    double gpa;
    
    Student(const std::string& n, int a, double g) : name(n), age(a), gpa(g) {}
    
    void Print() const
    {
        std::cout << name << " (Age: " << age << ", GPA: " << gpa << ")";
    }
};

void PrintStudents(const std::vector<Student>& students, const std::string& title)
{
    std::cout << title << ":" << std::endl;
    for (const auto& student : students)
    {
        std::cout << "  ";
        student.Print();
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

int main()
{
    std::vector<Student> students = {
        {"Alice", 20, 3.8},
        {"Bob", 19, 3.2},
        {"Charlie", 21, 3.9},
        {"Diana", 20, 3.5},
        {"Eve", 18, 3.7}
    };
    
    PrintStudents(students, "Original");
    
    // 按年龄排序
    std::vector<Student> byAge = students;
    std::sort(byAge.begin(), byAge.end(), [](const Student& a, const Student& b) {
        return a.age < b.age;
    });
    PrintStudents(byAge, "Sorted by Age");
    
    // 按GPA降序排序
    std::vector<Student> byGPA = students;
    std::sort(byGPA.begin(), byGPA.end(), [](const Student& a, const Student& b) {
        return a.gpa > b.gpa;
    });
    PrintStudents(byGPA, "Sorted by GPA (Descending)");
    
    // 按姓名字母顺序排序
    std::vector<Student> byName = students;
    std::sort(byName.begin(), byName.end(), [](const Student& a, const Student& b) {
        return a.name < b.name;
    });
    PrintStudents(byName, "Sorted by Name");
    
    // 多级排序：先按年龄，再按GPA
    std::vector<Student> multiLevel = students;
    std::sort(multiLevel.begin(), multiLevel.end(), [](const Student& a, const Student& b) {
        if (a.age != b.age)
            return a.age < b.age;
        return a.gpa > b.gpa;  // 年龄相同时按GPA降序
    });
    PrintStudents(multiLevel, "Sorted by Age, then by GPA");
    
    return 0;
}

 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

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

class SortingBenchmark
{
private:
    std::vector<int> GenerateRandomData(size_t size)
    {
        std::vector<int> data;
        data.reserve(size);
        
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(1, 10000);
        
        for (size_t i = 0; i < size; ++i)
        {
            data.push_back(dis(gen));
        }
        
        return data;
    }
    
    template<typename SortFunc>
    long long MeasureTime(std::vector<int> data, SortFunc sortFunc)
    {
        auto start = std::chrono::high_resolution_clock::now();
        sortFunc(data.begin(), data.end());
        auto end = std::chrono::high_resolution_clock::now();
        
        return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    }
    
public:
    void RunBenchmark(size_t dataSize)
    {
        std::cout << "=== Sorting Benchmark (Size: " << dataSize << ") ===" << std::endl;
        
        auto data = GenerateRandomData(dataSize);
        
        // std::sort
        auto time1 = MeasureTime(data, [](auto begin, auto end) {
            std::sort(begin, end);
        });
        
        // std::stable_sort
        auto time2 = MeasureTime(data, [](auto begin, auto end) {
            std::stable_sort(begin, end);
        });
        
        // std::partial_sort (只排序前一半)
        auto time3 = MeasureTime(data, [&](auto begin, auto end) {
            std::partial_sort(begin, begin + dataSize / 2, end);
        });
        
        // std::nth_element (找到中位数)
        auto time4 = MeasureTime(data, [&](auto begin, auto end) {
            std::nth_element(begin, begin + dataSize / 2, end);
        });
        
        std::cout << "std::sort: " << time1 << " μs" << std::endl;
        std::cout << "std::stable_sort: " << time2 << " μs" << std::endl;
        std::cout << "std::partial_sort: " << time3 << " μs" << std::endl;
        std::cout << "std::nth_element: " << time4 << " μs" << std::endl;
        std::cout << std::endl;
    }
};

int main()
{
    SortingBenchmark benchmark;
    
    benchmark.RunBenchmark(10000);
    benchmark.RunBenchmark(100000);
    benchmark.RunBenchmark(1000000);
    
    return 0;
}

  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cctype>

// 自然排序（处理数字）
bool NaturalCompare(const std::string& a, const std::string& b)
{
    size_t i = 0, j = 0;
    
    while (i < a.length() && j < b.length())
    {
        if (std::isdigit(a[i]) && std::isdigit(b[j]))
        {
            // 比较数字
            int numA = 0, numB = 0;
            while (i < a.length() && std::isdigit(a[i]))
            {
                numA = numA * 10 + (a[i] - '0');
                ++i;
            }
            while (j < b.length() && std::isdigit(b[j]))
            {
                numB = numB * 10 + (b[j] - '0');
                ++j;
            }
            
            if (numA != numB)
                return numA < numB;
        }
        else
        {
            if (a[i] != b[j])
                return a[i] < b[j];
            ++i;
            ++j;
        }
    }
    
    return a.length() < b.length();
}

// 大小写不敏感排序
bool CaseInsensitiveCompare(const std::string& a, const std::string& b)
{
    return std::lexicographical_compare(
        a.begin(), a.end(),
        b.begin(), b.end(),
        [](char c1, char c2) {
            return std::tolower(c1) < std::tolower(c2);
        }
    );
}

// 按字符串长度排序
bool LengthCompare(const std::string& a, const std::string& b)
{
    if (a.length() != b.length())
        return a.length() < b.length();
    return a < b;  // 长度相同时按字典序
}

void SpecialSortingExamples()
{
    std::cout << "=== Special Sorting Examples ===" << std::endl;
    
    // 自然排序示例
    std::vector<std::string> files = {
        "file1.txt", "file10.txt", "file2.txt", "file20.txt", "file3.txt"
    };
    
    std::cout << "Original file list:" << std::endl;
    for (const auto& file : files) std::cout << "  " << file << std::endl;
    
    std::sort(files.begin(), files.end());
    std::cout << "\nLexicographic sort:" << std::endl;
    for (const auto& file : files) std::cout << "  " << file << std::endl;
    
    std::sort(files.begin(), files.end(), NaturalCompare);
    std::cout << "\nNatural sort:" << std::endl;
    for (const auto& file : files) std::cout << "  " << file << std::endl;
    
    // 大小写不敏感排序
    std::vector<std::string> words = {"apple", "Banana", "cherry", "Date", "elderberry"};
    
    std::cout << "\nOriginal words:" << std::endl;
    for (const auto& word : words) std::cout << "  " << word << std::endl;
    
    std::sort(words.begin(), words.end(), CaseInsensitiveCompare);
    std::cout << "\nCase-insensitive sort:" << std::endl;
    for (const auto& word : words) std::cout << "  " << word << std::endl;
    
    // 按长度排序
    std::vector<std::string> phrases = {"C++", "Programming", "is", "fun", "and", "powerful"};
    
    std::cout << "\nOriginal phrases:" << std::endl;
    for (const auto& phrase : phrases) std::cout << "  " << phrase << std::endl;
    
    std::sort(phrases.begin(), phrases.end(), LengthCompare);
    std::cout << "\nSorted by length:" << std::endl;
    for (const auto& phrase : phrases) std::cout << "  " << phrase << std::endl;
}

int main()
{
    SpecialSortingExamples();
    return 0;
}

 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

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

void PartialSortingExamples()
{
    std::cout << "=== Partial Sorting Examples ===" << std::endl;
    
    // 生成随机数据
    std::vector<int> data;
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 100);
    
    for (int i = 0; i < 20; ++i)
    {
        data.push_back(dis(gen));
    }
    
    std::cout << "Original data:" << std::endl;
    for (int val : data) std::cout << val << " ";
    std::cout << std::endl;
    
    // 1. partial_sort - 只排序前N个元素
    std::vector<int> partialSorted = data;
    std::partial_sort(partialSorted.begin(), partialSorted.begin() + 5, partialSorted.end());
    
    std::cout << "\nPartial sort (first 5 elements):" << std::endl;
    for (size_t i = 0; i < partialSorted.size(); ++i)
    {
        if (i == 5) std::cout << "| ";
        std::cout << partialSorted[i] << " ";
    }
    std::cout << std::endl;
    
    // 2. nth_element - 找到第N个元素的正确位置
    std::vector<int> nthElement = data;
    size_t n = 10;
    std::nth_element(nthElement.begin(), nthElement.begin() + n, nthElement.end());
    
    std::cout << "\nAfter nth_element (n=" << n << "):" << std::endl;
    std::cout << "Element at position " << n << ": " << nthElement[n] << std::endl;
    std::cout << "All elements before position " << n << " are <= " << nthElement[n] << std::endl;
    std::cout << "All elements after position " << n << " are >= " << nthElement[n] << std::endl;
    
    // 3. 找到前K个最大元素
    std::vector<int> topK = data;
    int k = 3;
    std::partial_sort(topK.begin(), topK.begin() + k, topK.end(), std::greater<int>());
    
    std::cout << "\nTop " << k << " largest elements:" << std::endl;
    for (int i = 0; i < k; ++i)
    {
        std::cout << topK[i] << " ";
    }
    std::cout << std::endl;
    
    // 4. 找到中位数
    std::vector<int> median = data;
    size_t mid = median.size() / 2;
    std::nth_element(median.begin(), median.begin() + mid, median.end());
    
    std::cout << "\nMedian: " << median[mid] << std::endl;
    
    // 5. 找到特定百分位数
    std::vector<int> percentile = data;
    size_t p90 = static_cast<size_t>(percentile.size() * 0.9);
    std::nth_element(percentile.begin(), percentile.begin() + p90, percentile.end());
    
    std::cout << "90th percentile: " << percentile[p90] << std::endl;
}

int main()
{
    PartialSortingExamples();
    return 0;
}

 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
88
89

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Employee
{
    std::string name;
    std::string department;
    int salary;
    int id;
    
    Employee(const std::string& n, const std::string& d, int s, int i)
        : name(n), department(d), salary(s), id(i) {}
    
    void Print() const
    {
        std::cout << "ID:" << id << " " << name << " (" << department << ") $" << salary;
    }
};

void PrintEmployees(const std::vector<Employee>& employees, const std::string& title)
{
    std::cout << title << ":" << std::endl;
    for (const auto& emp : employees)
    {
        std::cout << "  ";
        emp.Print();
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

void StableSortExample()
{
    std::cout << "=== Stable Sort Example ===" << std::endl;
    
    std::vector<Employee> employees = {
        {"Alice", "Engineering", 75000, 1},
        {"Bob", "Marketing", 65000, 2},
        {"Charlie", "Engineering", 75000, 3},
        {"Diana", "Sales", 70000, 4},
        {"Eve", "Engineering", 75000, 5},
        {"Frank", "Marketing", 65000, 6}
    };
    
    PrintEmployees(employees, "Original");
    
    // 先按部门排序
    std::stable_sort(employees.begin(), employees.end(), 
                    [](const Employee& a, const Employee& b) {
                        return a.department < b.department;
                    });
    PrintEmployees(employees, "Sorted by Department (stable)");
    
    // 再按薪水排序（保持部门内的原有顺序）
    std::stable_sort(employees.begin(), employees.end(), 
                    [](const Employee& a, const Employee& b) {
                        return a.salary > b.salary;
                    });
    PrintEmployees(employees, "Sorted by Salary (stable) - maintains department order for same salary");
    
    // 对比：使用普通sort
    std::vector<Employee> employees2 = {
        {"Alice", "Engineering", 75000, 1},
        {"Bob", "Marketing", 65000, 2},
        {"Charlie", "Engineering", 75000, 3},
        {"Diana", "Sales", 70000, 4},
        {"Eve", "Engineering", 75000, 5},
        {"Frank", "Marketing", 65000, 6}
    };
    
    std::sort(employees2.begin(), employees2.end(), 
             [](const Employee& a, const Employee& b) {
                 return a.department < b.department;
             });
    
    std::sort(employees2.begin(), employees2.end(), 
             [](const Employee& a, const Employee& b) {
                 return a.salary > b.salary;
             });
    PrintEmployees(employees2, "Using regular sort - order may not be preserved");
}

int main()
{
    StableSortExample();
    return 0;
}

 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

#include <iostream>
#include <vector>
#include <algorithm>

void SortingGuide()
{
    std::cout << "=== Sorting Algorithm Selection Guide ===" << std::endl;
    
    std::vector<int> data = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    std::cout << "Original: ";
    for (int val : data) std::cout << val << " ";
    std::cout << std::endl;
    
    // 1. std::sort - 最常用，平均O(n log n)，不稳定
    std::vector<int> sorted1 = data;
    std::sort(sorted1.begin(), sorted1.end());
    std::cout << "std::sort (unstable, O(n log n)): ";
    for (int val : sorted1) std::cout << val << " ";
    std::cout << std::endl;
    
    // 2. std::stable_sort - 稳定排序，O(n log n)
    std::vector<int> sorted2 = data;
    std::stable_sort(sorted2.begin(), sorted2.end());
    std::cout << "std::stable_sort (stable, O(n log n)): ";
    for (int val : sorted2) std::cout << val << " ";
    std::cout << std::endl;
    
    // 3. std::partial_sort - 只需要前K个元素时使用
    std::vector<int> sorted3 = data;
    std::partial_sort(sorted3.begin(), sorted3.begin() + 3, sorted3.end());
    std::cout << "std::partial_sort (first 3): ";
    for (int val : sorted3) std::cout << val << " ";
    std::cout << std::endl;
    
    // 4. std::nth_element - 只需要第N个元素时使用
    std::vector<int> sorted4 = data;
    std::nth_element(sorted4.begin(), sorted4.begin() + 4, sorted4.end());
    std::cout << "std::nth_element (5th element): ";
    for (int val : sorted4) std::cout << val << " ";
    std::cout << " (5th element: " << sorted4[4] << ")" << std::endl;
    
    std::cout << "\nWhen to use each algorithm:" << std::endl;
    std::cout << "- std::sort: General purpose, fastest for complete sorting" << std::endl;
    std::cout << "- std::stable_sort: When relative order of equal elements matters" << std::endl;
    std::cout << "- std::partial_sort: When you only need the top/bottom K elements" << std::endl;
    std::cout << "- std::nth_element: When you only need the Nth element (median, percentiles)" << std::endl;
}

int main()
{
    SortingGuide();
    return 0;
}