一、归并排序
1、思想
分解（Divide）：将当前序列从中间一分为二，递归地对左半部分和右半部分进行拆分。
解决（Conquer）：当拆分到每个子序列只有一个元素时，认为该序列是有序的（递归终止条件）。
合并（Combine）：将两个已排序的子序列合并成一个新的有序序列，直到最终合并为原长度的有序数组。
即，不断进行一分为二，当最后left == right时，递归结束，开始合并，并且不断从深层返回合并的结果。
2、特点和劣势
时间复杂度：O(n log n)：logn是指递归的层次 n是指合并排序产生的时间复杂度。
空间复杂度：O(n)（需要临时数组）
稳定排序（使用 <= 保证相等元素的相对顺序）
3、算法实现
（递归主函数）
递归主函数，不要思考这么复杂，从最简单的层面思考，问题变得很简单。
（归并函数）
核心思想是开辟两个临时数组存储左右部分，并通过双指针不断比较，填充arr原数组。
二、qsort的简单实现
针对malloc开辟的数组排序：
1、一维数组
2、二维数组
int cmp(const void *a, const void *b) {
int *row1 = (int *)a;
int *row2 = (int *)b;
// 第一级排序
if (row1[0] != row2[0]) {
return row1[0] - row2[0];
}
// 第二级排序
return row1[1] - row2[1];
}
qsort(arr, N, sizeof(arr[0]), cmp);三、快速排序
1、思想
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小（或小于等于），然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行。
2、特点和劣势
（1）快速排序的特点（优势）
- 极高的平均效率： 虽然其平均时间复杂度与归并排序、堆排序一样都是 $O(n \log n)$，但在实际运行中，快排通常比它们快。这是因为它的内部循环指令非常简单，且对 CPU 缓存（Cache） 非常友好。
- 原地排序 (In-place)： 与归并排序需要 $O(n)$ 的辅助数组不同，快排只需要 $O(\log n)$ 的递归栈空间。在内存受限的嵌入式系统或处理海量 GIS 空间数据时，这个优势非常巨大。
- 高度可优化： * 可以通过“三数取中”或“随机基准”来规避极端的测试数据。
- 当递归到区间较小（如 $n < 15$）时，可以切换为插入排序来进一步榨干性能。
（2）快速排序的劣势（短板）
- 不稳定性 (Unstable)： 这是快排最大的硬伤。正如你观察到的，
swap操作会打乱相等元素的原始相对顺序。举例： 如果你先按“成绩”排序，再按“学号”排序，快排可能会把你之前排好的成绩顺序搞乱。在 C 语言中，如果你需要稳定排序，通常得改用mergesort。 - 最坏情况触发： 如果基准值选得不好（比如每次都选到最小或最大的数），分区就会极度不均匀。
- 现象： 递归树退化成一个单向链表。
- 后果： 时间复杂度劣化为 $O(n^2)$，并且极易触发 栈溢出 (Stack Overflow)。
- 对小规模数据不划算： 由于递归调用存在开销，对于只有几个元素的数组，快排反而不如简单的插入排序快。
3、算法实现
