1
#include <vector>
2
#include <algorithm>
3
#include <chrono>
4
#include <iostream>
5

6
// 演示用：不同排序对同一数组的性能对比
7
// 实际项目中用 Google Benchmark 或 perf 更准确
8
void benchmark_sorts() {
9
    const int N = 1000000;
10
    std::vector<int> original(N);
11
    std::generate(original.begin(), original.end(), rand);
12

13
    std::vector<int> arr;
14

15
    // 快排
16
    arr = original;
17
    auto t1 = std::chrono::high_resolution_clock::now();
18
    std::sort(arr.begin(), arr.end());  // Introsort（主体是快排）
19
    auto t2 = std::chrono::high_resolution_clock::now();
20

21
    // 堆排
22
    arr = original;
23
    auto t3 = std::chrono::high_resolution_clock::now();
24
    std::make_heap(arr.begin(), arr.end());
25
    std::sort_heap(arr.begin(), arr.end());
26
    auto t4 = std::chrono::high_resolution_clock::now();
27

28
    // 归并（使用 std::stable_sort，底层是归并）
29
    arr = original;
30
    auto t5 = std::chrono::high_resolution_clock::now();
31
    std::stable_sort(arr.begin(), arr.end());
32
    auto t6 = std::chrono::high_resolution_clock::now();
33

34
    // 典型结果（相对耗时）：
35
    // 快排: 1.0x   ← 最快（缓存局部性好）
36
    // 归并: 1.5x   ← 慢于快排（需要额外数组 + 合并回写）
37
    // 堆排: 2.5x   ← 最慢（缓存局部性最差）
38
}

1
快排的内存访问模式（Lomuto 分区）：
2
┌──────┬──────┬──────┬──────┬──────┬──────┐
3
│ < p  │ < p  │ > p  │  ?   │  ?   │ pivot│  逐个顺序扫描
4
└──────┴──────┴──────┴──────┴──────┴──────┘
5
  ↑ i                          ↑ j 向右移动
6
  每次访问相邻元素 → Cache Line 利用率接近 100%
7

8
堆排的内存访问模式（heapifyDown）：
9
         [0]
10
        /   \
11
     [1]     [2]
12
     /  \    /  \
13
   [3]  [4][5]  [6]
14

15
访问 [0] → [1] → [3] → [7] ...
16
在数组中：
17
[0][1][2][3][4][5][6][7][8]...
18
 ↑     ↑       ↑         ↑
19
 每次访问跳 log n 级距离 → 几乎每次都是 Cache Miss

1
// Timsort 简化版的核心概念演示
2
// 实际 Timsort 实现约 1000 行，这里只展示 run 检测
3
std::vector<std::pair<int, int>> findRuns(const std::vector<int>& arr) {
4
    std::vector<std::pair<int, int>> runs;
5
    int n = arr.size();
6
    int i = 0;
7

8
    while (i < n) {
9
        int start = i;
10
        ++i;
11

12
        // 检测递增或递减趋势
13
        if (i < n && arr[i - 1] <= arr[i]) {
14
            while (i < n && arr[i - 1] <= arr[i]) ++i;  // 递增
15
        } else {
16
            while (i < n && arr[i - 1] > arr[i]) ++i;   // 递减
17
            std::reverse(arr.begin() + start, arr.begin() + i);  // 翻转为递增
18
        }
19

20
        // 如果 run 太短，用插入排序扩展到 minrun
21
        int runLen = i - start;
22
        if (runLen < 32 && i < n) {
23
            int end = std::min(start + 32, n);
24
            insertionSortRange(arr, start, end - 1);
25
            i = end;
26
        }
27

28
        runs.push_back({start, i - start});
29
    }
30
    return runs;
31
}

1
// 三指针：lt 标记 0 的右边界，gt 标记 2 的左边界，i 扫描
2
void sortColors(std::vector<int>& nums) {
3
    int lt = 0, i = 0, gt = nums.size() - 1;
4

5
    while (i <= gt) {
6
        if (nums[i] == 0) {
7
            std::swap(nums[lt], nums[i]);
8
            ++lt;
9
            ++i;
10
        } else if (nums[i] == 2) {
11
            std::swap(nums[i], nums[gt]);
12
            --gt;
13
            // i 不自增：换过来的 nums[gt] 可能是 0 或 1
14
        } else {
15
            ++i;
16
        }
17
    }
18
}

1
struct ListNode {
2
    int val;
3
    ListNode* next;
4
    ListNode(int x) : val(x), next(nullptr) {}
5
};
6

7
// 快慢指针找中点（断开前后两半）
8
ListNode* split(ListNode* head) {
9
    if (!head || !head->next) return nullptr;
10

11
    ListNode* slow = head;
12
    ListNode* fast = head->next;  // fast 先走一步，让 slow 停在前半段的末尾
13

14
    while (fast && fast->next) {
15
        slow = slow->next;
16
        fast = fast->next->next;
17
    }
18

19
    ListNode* mid = slow->next;
20
    slow->next = nullptr;  // 断开！
21
    return mid;
22
}
23

24
// 合并两个有序链表
25
ListNode* merge(ListNode* l1, ListNode* l2) {
26
    ListNode dummy(0);
27
    ListNode* tail = &dummy;
28

29
    while (l1 && l2) {
30
        if (l1->val <= l2->val) {
31
            tail->next = l1;
32
            l1 = l1->next;
33
        } else {
34
            tail->next = l2;
35
            l2 = l2->next;
36
        }
37
        tail = tail->next;
38
    }
39
    tail->next = l1 ? l1 : l2;
40

41
    return dummy.next;
42
}
43

44
ListNode* sortList(ListNode* head) {
45
    if (!head || !head->next) return head;
46

47
    ListNode* mid = split(head);
48
    ListNode* left  = sortList(head);
49
    ListNode* right = sortList(mid);
50
    return merge(left, right);
51
}

1
#include <vector>
2
#include <algorithm>
3

4
struct Renderable {
5
    uint32_t  id;
6
    float     depth;        // 离相机的距离
7
    int       material_id;  // 材质 ID
8
    int       render_queue; // 渲染队列（背景=0, 几何体=1000, 透明=3000, 叠加=4000）
9
    bool      is_transparent;
10

11
    // ... 其他渲染数据
12
};
13

14
// 渲染排序：先按队列分组，再按深度和材质排序
15
void sortRenderables(std::vector<Renderable>& objects) {
16
    std::sort(objects.begin(), objects.end(),
17
        [](const Renderable& a, const Renderable& b) {
18
            // 1. 先按渲染队列排序（不透明 → 透明 → UI 叠加）
19
            if (a.render_queue != b.render_queue)
20
                return a.render_queue < b.render_queue;
21

22
            // 2. 同一队列内：
23
            if (a.render_queue == 3000) {
24
                // 透明物体：从远到近（Painter's Algorithm）
25
                return a.depth > b.depth;
26
            } else {
27
                // 不透明物体：从近到远（利用 Early-Z 剔除）
28
                // 同时按材质排序（减少 GPU 状态切换）
29
                if (a.material_id != b.material_id)
30
                    return a.material_id < b.material_id;
31
                return a.depth < b.depth;
32
            }
33
        });
34
}

1
渲染优化原理：
2
┌─────────────────────────────────────────────────────┐
3
│ Early-Z 优化（不透明物体）                              │
4
│ 从近到远渲染 → 近处的先写入深度缓冲                      │
5
│ → 远处的像素被 Early-Z 测试提前剔除                      │
6
│ → 节省大量像素着色器计算                                │
7
├─────────────────────────────────────────────────────┤
8
│ 材质排序                                               │
9
│ 相同材质的物体一起渲染 → 减少 SetShader/SetTexture 调用   │
10
│ → 减少 GPU 状态切换（每次切换都有开销）                    │
11
├─────────────────────────────────────────────────────┤
12
│ Painter's Algorithm（透明物体）                          │
13
│ 从远到近渲染 → 远处的颜色先写入                         │
14
│ → 近处的透明色和远处的颜色做 alpha 混合                  │
15
│ → 产生正确的半透明效果                                  │
16
└─────────────────────────────────────────────────────┘

1
#include <queue>
2
#include <vector>
3
#include <string>
4

5
struct PlayerScore {
6
    std::string name;
7
    int64_t     score;
8
    int         level;
9

10
    // 最小堆：分数低的在堆顶（方便弹出）
11
    bool operator>(const PlayerScore& other) const {
12
        if (score != other.score) return score > other.score;
13
        return level > other.level;  // 分数相同按等级排
14
    }
15
};
16

17
class Leaderboard {
18
    static constexpr int TOP_K = 100;
19

20
    std::priority_queue<PlayerScore, std::vector<PlayerScore>,
21
                        std::greater<PlayerScore>> _topK;  // 最小堆
22
public:
23
    // 更新玩家分数
24
    void updateScore(const PlayerScore& ps) {
25
        _topK.push(ps);
26
        if (_topK.size() > TOP_K) {
27
            _topK.pop();  // 弹出堆顶（当前第 101 名，即最小值）
28
        }
29
    }
30

31
    // 获取排行榜（降序）
32
    std::vector<PlayerScore> getTopK() const {
33
        auto heap = _topK;  // 拷贝一份
34
        std::vector<PlayerScore> result;
35
        result.reserve(heap.size());
36

37
        while (!heap.empty()) {
38
            result.push_back(heap.top());
39
            heap.pop();
40
        }
41
        // 堆是从小到大的，反转得到从大到小
42
        std::reverse(result.begin(), result.end());
43
        return result;
44
    }
45
};

1
struct Friend {
2
    std::string name;
3
    bool        online;
4
    int         intimacy;  // 亲密度
5
    int         level;
6
};
7

8
void sortFriendList(std::vector<Friend>& friends) {
9
    // 利用 std::tuple 的字典序比较（C++17）
10
    std::sort(friends.begin(), friends.end(),
11
        [](const Friend& a, const Friend& b) {
12
            // 按优先级从高到低：
13
            // 在线的在前 → 亲密度高的在前 → 等级高的在前 → 名字字典序
14
            return std::tie(
15
                !a.online,          // 反转：online=true → 0（排前面）
16
                -a.intimacy,        // 反转：亲密度高的排前面
17
                -a.level,           // 反转：等级高的排前面
18
                a.name              // 名字字典序（正常顺序）
19
            ) < std::tie(
20
                !b.online,
21
                -b.intimacy,
22
                -b.level,
23
                b.name
24
            );
25
        });
26
}