Code59 零基础 · 排序 · 57—59¶
先读 第 0 课，再按每题“完整题干与条件 → 输入输出示例 → 人话讲解与状态推演 → 完整函数与逐句说明 → 自测”学习。题干整理和教学补充分别标注，原速查内容放在每题最后。
本篇对应全书第 57—59 题。三道题分别解决“原地比较排序”“稳定归并排序”“只划分大小两组、不完整排序”。区间默认是含左右端点的闭区间，数组下标从 0 开始。示例和推导为本次补充，原稿只读。
读代码前：编译环境与类型¶
本章展示的是完整函数，不是每题各有一个 main 的独立程序。练习编译一题时，将所需类型、辅助函数与题目函数放在同一份学习用 C 文件里，再添加调用它的 main；第 0 课给了最小程序例子。常用标准头文件如下（它们提供打印、分配空间、真假类型、整数上限）：
57｜快速排序（本章第 1 题）¶
题目与要求¶
题目（依据原题整理）：原资料此项题名为“快速排序”。本练习按其代码补全要求：给定整数数组，编写快速排序算法，将指定区间内的元素按非递减顺序排列。
已知条件：输入数组 A 以及待排区间的左右端点 low、high；两个端点都包含在区间内，元素可以重复。
需要得到：原数组指定区间排好序，所有原元素及其出现次数保留。
输入 → 输出示例（教学补充）：A=[4,1,3,2]，low=0，high=3 → A=[1,2,3,4]。
约定与提醒（教学补充）：整数组排序时范围为 0 到 n-1。一次划分不是完整排序，不能只调用一次 partition 就宣布完成；这里不要求保持同值元素的原相对次序。
题干回源：Code59 PDF 第 27 页；回源 · PDF 第 27 页 · b_27_1；PDF 第 27 页 · b_27_0
。原资料没有另列完整应用场景，上面的输入输出要求为教学补全。
1. 快排先摆正一个“分界数”，再管两边¶
枢轴 pivot 就是本轮选中的分界数。先把小于它的放左边，不小于它的放右边，再分别把两边内部排好。第一轮结束通常还没全有序，只是枢轴的位置合适了。
输入 [5,2,8,1,7]，取首值 5 作为 pivot。low、high 是两只手指向的下标，最初为 0、4。先把 5 保存在独立变量里，原下标 0 可以当作待填的位置，称为“坑”，不是数组真的少了一格。
2. 每一次复制后都保住被覆盖的值了吗？¶
| 步骤 | 手指与待填位置 | 数组状态 | pivot 独立保存 |
|---|---|---|---|
| 开始 | low=0 待填，high=4 | [5,2,8,1,7] |
5 |
| 从右找小数 | 7>=5，high 退到 3；1<5 停 | 未修改 | 5 |
| 右值填左坑 | A[0]=A[3]，右位置 3 变待填 | [1,2,8,1,7] |
5 |
| 从左找不小的数 | 越过 1、2，low 到 2 的 8 | 未修改 | 5 |
| 左值填右坑 | A[3]=A[2]，位置 2 变待填 | [1,2,8,8,7] |
5 |
| 再从右找 | high 从 3 退到 2，与 low 相遇 | 中间复制只会自己给自己 | 5 |
| 填回枢轴 | A[2]=5 | [1,2,5,8,7] |
返回位置 2 |
相等位置上的自复制不改变结果。随后左段 [1,2] 已易排好，右段 [8,7] 排成 [7,8]，全体变 [1,2,5,7,8]。
3. 完整函数与逐句说明¶
代码段 1¶
int partition(int A[], int low, int high) {
int pivot = A[low];
while (low < high) {
while (low < high && A[high] >= pivot)
high--;
A[low] = A[high];
while (low < high && A[low] < pivot)
low++;
A[high] = A[low];
}
A[low] = pivot;
return low;
}
void quickSort(int A[], int low, int high) {
if (low >= high)
return;
int pivotPos = partition(A, low, high);
quickSort(A, low, pivotPos - 1);
quickSort(A, pivotPos + 1, high);
}
partition 先保存 A[low]。外层 while 保证两端还没相遇；右内循环跳过大于等于 pivot 的数，因为它们留在右边没问题，找到小数就复制到左端。左内循环跳过小于 pivot 的数，找到不小的就复制到右端。每次内循环同时检查 low<high，防止越过彼此。
两手相遇后，最后一个待填位置放 pivot，return low 交回分界位置。上面的函数只是一次分区，不递归。
quickSort 的 if 表示空段或单元素已自然有序；否则先调用 partition，得到 pivotPos，再分别递归 [low,pivotPos-1] 和 [pivotPos+1,high]。枢轴已经定位，不再放回任何子任务，否则可能重复处理、不收敛。
4. 自己试与不能只背平均复杂度¶
对 [2,1]：保存 2，右端 1 填左坑，两端相遇后把 2 放右边，得到 [1,2]。对已经升序且总取首数的数组，枢轴常落最边上，两边严重不平衡，最坏可到 O(n²)，不是每次都必然 O(n log n)。相等元素身份顺序不保证保持，所以它通常不稳定。
学懂后回看：结论、复杂度与回源¶
题意与结论：先把一个枢轴放到分界位置，使左边小于它、右边大于等于它，再递归排序左右两段。一次 partition 只完成分区，不代表整个数组已排好。
思路推导：枢轴最终放哪，取决于小值应该在它左边、大值应该在它右边。正式代码使用“挖坑填数”：先保存首元素 pivot，空出左坑；从右找小值填左坑，再从左找不小于 pivot 的值填右坑，最后用 pivot 填上相遇处的坑。
走一遍：[5,2,8,1,7]，pivot=5。右侧跳过 7，在 1 停下，把 1 填到下标 0，此时真正保存的枢轴仍在变量里；左侧越过 1、2，在 8 停下，把 8 填到刚才右边的坑。两指针继续靠拢，最终在下标 2 相遇，填回 5，得到 [1,2,5,8,7]。再分别排 [1,2] 和 [8,7]，得到全序 [1,2,5,7,8]。
代码抓手与正确性：右扫条件 A[high]>=pivot，左扫条件 A[low]<pivot；每次扫描都先保证 low<high。保存 pivot 后，中间的重复数组值只是“坑”的临时表现，不是数据丢失。partition 返回 pivotPos，递归区间必须排除枢轴，即 [low,pivotPos-1] 与 [pivotPos+1,high]。
复杂度与易错点：平均时间 O(n log n)，最坏 O(n²)；平均栈 O(log n)，最坏 O(n)。首元素作枢轴时，已排序或全部相等数据可能极不均衡。快排通常不稳定，枢轴两侧相等元素的相对位置不保证保持。随机枢轴可改善期望表现，但不能把原确定性首枢轴实现说成已随机化。
回源：PDF 第 27 页；回源 · PDF 第 27 页 · b_27_1；PDF 第 27 页 · b_27_0
。正式代码
58｜二路归并排序（本章第 2 题）¶
题目与要求¶
题目（依据原题整理）：原资料此项题名为“二路归并排序”。本练习按其代码补全要求：给定整数数组，编写二路归并排序算法，将指定区间按非递减顺序排列。
已知条件：输入数组 A 及闭区间端点 low、high，原数组不要求有序；允许为合并操作申请辅助数组。
需要得到：原数组指定区间排好序，保留全部元素及重复次数。
输入 → 输出示例（教学补充）：A=[4,1,3,2]，low=0，high=3 → A=[1,2,3,4]。
约定与提醒（教学补充）：不能把它与“输入已经有序的两个表直接归并”混为一题，这里首先要把无序区间排好。下面校订函数返回布尔值，辅助内存申请失败时返回 false，此时不能认为排序已完成。
题干回源：Code59 PDF 第 27 页；回源 · PDF 第 27 页 · b_27_3；PDF 第 27 页 · b_27_2
。原资料只列算法题名，输入输出描述为教学补全。
1. 归并排序先拆到简单，再合回来¶
单个数本来就有序。把 [4,1,3,2] 拆成 [4,1] 和 [3,2]，再拆成四个单数，各自两两合成 [1,4] 与 [2,3]，最后合并为 [1,2,3,4]。
与快排不同，归并切成左右段时并没有先挑小值到左边；它按位置直接一分为二，真正排序发生在子段排好后的合并。
2. 最后一次合并，把原数组与临时数组分开¶
先把 [1,4,2,3] 复制到 temp，左段 temp[0..1]、右段 temp[2..3]；i=0、j=2，k=0 是原数组下一写位置。
| 比较前 i、j、k | 两边当前值 | 写入原数组 | 接下来 |
|---|---|---|---|
| 0、2、0 | 1、2 | A[0]=1 | i=1，k=1 |
| 1、2、1 | 4、2 | A[1]=2 | j=3，k=2 |
| 1、3、2 | 4、3 | A[2]=3 | j=4，右段耗尽，k=3 |
| 左段还剩 4 | 不再比较 | A[3]=4 | 完成 |
第二步已经覆盖原 A[1] 的 4，但 4 还在 temp[1]，所以不会丢。这就是为什么需要临时数组，不能一边覆盖原数组一边假装原值还在。
3. 完整函数与逐句说明¶
代码段 1¶
bool mergeRanges(int A[], int low, int mid, int high) {
int length = high - low + 1;
int *temp = (int *)malloc(length * sizeof(int));
if (temp == NULL)
return false;
for (int i = low; i <= high; i++)
temp[i - low] = A[i];
int i = 0;
int j = mid - low + 1;
int leftEnd = mid - low;
int rightEnd = high - low;
int k = low;
while (i <= leftEnd && j <= rightEnd) {
if (temp[i] <= temp[j])
A[k++] = temp[i++];
else
A[k++] = temp[j++];
}
while (i <= leftEnd)
A[k++] = temp[i++];
while (j <= rightEnd)
A[k++] = temp[j++];
free(temp);
return true;
}
bool mergeSort(int A[], int low, int high) {
if (low >= high)
return true;
int mid = low + (high - low) / 2;
if (!mergeSort(A, low, mid))
return false;
if (!mergeSort(A, mid + 1, high))
return false;
return mergeRanges(A, low, mid, high);
}
mergeRanges 收到两个已排序的相邻段 [low,mid]、[mid+1,high]。length=high-low+1 包含两端；malloc 申请同样多的 temp 格；失败返回 false。复制时用 temp[i-low]，因为原数组区间可能从下标 20 开始，但 temp 仍从 0 开始。
左读指针 i=0，右读指针 j=mid-low+1；leftEnd、rightEnd 是它们各自最后能读的 temp 下标；k=low 从原区间起点写。两边都没空时比较当前值，相等先拿左边，写完对应读指针及 k 增一；之后补剩余一边。用完 free temp，return true。
mergeSort 先处理空段或单元素；求中点后分别递归左右，任一返回 false 都向上传失败；两边都排好，才调用 mergeRanges 合成整段。主调用者也要检查最终返回值，不能忽略内存失败状态。
4. 自己试与为什么是稳定的¶
把相同值标成 2a、2b，并且 2a 在原数组较前。当两段首值都为 2，<= 让左段的 2a 先入结果，原同值次序保留。若改成 <，相等时先取右段，可能破坏稳定性。
练习 [3,1,2]：先把左两格归并为 [1,3]，右边只有 [2]，最后合成 [1,2,3]。数组长度不是 2 的幂也可以，左右段不必总等长。
学懂后回看：结论、复杂度与回源¶
题意与结论：先把数组分成两半，各自排好，再用双指针合并两个有序段。与快排的区别是：快排在递归前做分区，归并在递归后做合并。
思路推导：单元素天然有序，因此可一直二分到长度 1，再逐层向上合并。合并前把当前区间复制到 temp，防止往原数组写结果时覆盖还没读取的值。
走一遍：[4,1,3,2]。分为 [4,1]、[3,2]；各自再分成单元素，归并得到 [1,4]、[2,3]。最后比较 1 与 2，取 1；比较 4 与 2，取 2；比较 4 与 3，取 3；左段剩 4，补入，得到 [1,2,3,4]。
代码抓手与正确性：temp 使用从 0 开始的局部下标，原数组写指针 k 从 low 开始；右段在 temp 的起点是 mid-low+1。比较相等时先取左段 <=，保持同值元素的原相对次序，因此稳定。每轮合并都产生有序结果，逐层归纳得到整个数组有序。
复杂度与易错点：时间各情况下均 O(n log n)；辅助数组峰值 O(n)，递归栈 O(log n)，总辅助空间仍 O(n)。不是同时为每层永久保留 n 个元素，所以不应写成峰值 O(n log n)。temp 用完须 free；校订版已补齐释放，并把申请失败向上传回。mergeSort 返回 false 时，数组可能部分有序，不能宣称排序完成。
回源：PDF 第 27 页；回源 · PDF 第 27 页 · b_27_3；PDF 第 27 页 · b_27_2
。正式代码
59｜元素个数最接近、两组和差最大（本章第 3 题，2016）¶
题目与要求¶
题目（依据原题整理）：由 n 个正整数构成集合 A={a_k | 0<=k<n}，其中 n>=2。把它划分为两个不相交子集 A1、A2，其元素个数为 n1、n2、元素和为 S1、S2。设计尽可能高效的算法，先使 |n1-n2| 最小，再在此前提下使 |S1-S2| 最大。
已知条件：输入正整数数组及长度，每个元素必须恰好分入一组，不能遗漏或重复使用。
需要得到：满足两个优先级要求的分组。下面函数先在原数组中形成两段，再把两组分别写入输出数组 A1、A2，把各组元素个数写入 n1、n2；它不直接返回和差，和差可由分组结果求和后计算。
输入 → 输出示例（教学补充）：A=[1,2,9,10] → 两组可为 {1,2} 与 {9,10}，各 2 个元素，和差为 19-3=16。
约定与提醒（教学补充）：优先让元素个数接近，不是让元素和接近；也不能先把所有大数放一组而不管组的大小。0<=k<n 限制的是下标，不是要求每个元素小于 n；原稿该处排版歧义已在正式稿中校订。
题干回源：Code59 PDF 第 27 页；回源 · PDF 第 27 页 · b_27_4；PDF 第 27 页 · b_27_5
。
1. 两个要求有先后，不是想怎么拉大差就怎么分¶
先使两组人数尽量接近：n=5 时只能分 2 和 3，不能为了拉大和差分成 1 和 4。人数定了以后，再使两组元素和之差尽量大。
输入正整数 [8,1,6,2,9]；输出一组 [1,2]、另一组 [6,8,9]，两组和 3 与 23，差 20。组内 [2,1] 或 [9,6,8] 也行，因为题目没有要求各组内部排序。
2. 为什么要把小的集中起来，而不是平均分数值¶
如果小组里错放了 6，而大组里留着 2，小组和大了 4、大组和小了 4；把 6、2 交换回来，两组和差能增大 8。所以为了拉大差，要把较小值放在一起。它与“使两组和尽量相等”的另一类分组题目标相反。
target=n/2=2 表示较小组应有两个数，占下标 0、1；分界下标 target=2 是较大组开始的位置。别把“有两个人”写成占下标 0、1、2 三格。
3. 快速选择真的只追一边，走一遍看它停在哪¶
| 当前区间 | 一次 partition 后的数组 | pivotPos | 接下来为什么这样做 |
|---|---|---|---|
| 0..4，枢轴 8 | [2,1,6,8,9] |
3 | 目标 2 在左边，只查 0..2 |
| 0..2，枢轴 2 | [1,2,6,8,9] |
1 | 目标 2 在右边，只查 2..2 |
| 2..2，枢轴 6 | 不变 | 2 | 正好等于 target，停止 |
这个例子碰巧全有序，但算法不承诺做到全有序。只要左边两格是较小的两数，就够切组；不像快排还要把所有剩余两边都递归排序。
4. 完整函数与逐句说明¶
代码段 1¶
void splitForMaximumSumDifference(int A[], int n,
int A1[], int *n1,
int A2[], int *n2) {
int target = n / 2;
int low = 0;
int high = n - 1;
while (low <= high) {
int pivotPos = partition(A, low, high);
if (pivotPos == target)
break;
if (pivotPos < target)
low = pivotPos + 1;
else
high = pivotPos - 1;
}
*n1 = target;
*n2 = n - target;
for (int i = 0; i < *n1; i++)
A1[i] = A[i];
for (int i = 0; i < *n2; i++)
A2[i] = A[target + i];
}
本题调用的 partition 就是第 57 题的分区函数；为便于独立阅读，原样附在这里：
int partition(int A[], int low, int high) {
int pivot = A[low];
while (low < high) {
while (low < high && A[high] >= pivot)
high--;
A[low] = A[high];
while (low < high && A[low] < pivot)
low++;
A[high] = A[low];
}
A[low] = pivot;
return low;
}
参数 A 是可被原地重排的输入数组；A1、A2 用来接收两组；n1、n2 是两个接收人数的地址。先设置目标下标、搜索左右界。while 当前搜索区间非空，调用 partition 得到一次定位；等于目标就 break，只跳出这段搜索循环；偏左则 low=pivotPos+1，偏右则 high=pivotPos-1，继续只追包含目标的位置。
后面 *n1=target、*n2=n-target 把两组人数写给调用者。第一个 for 复制 A 前 target 个到 A1；第二个 for 从 A[target] 开始复制到 A2[0]，所以读下标是 target+i、写下标只是 i。
附出的 partition 和第 57 题相同：保存枢轴、左右找错位值填坑、相遇后放回枢轴并返回它的位置。这一题借用它，但没有调用 quickSort 排完全部。
5. 自己试与重要前提¶
[1,2,3,4] 应分 [1,2] 和 [3,4]，人数差 0、和差 4；[1,4] 与 [2,3] 虽同样人数差 0，但和差 0，不是目标。
本题保证正整数，奇数人数时让较大值组多一个元素会取得最大绝对和差。若允许负数，尤其奇数长度，不能不分析就照搬这个结论。快速选择平均 O(n)、最坏 O(n²)；“只查一边”不保证每次恰好砍半，枢轴选择极差时仍可能慢。
学懂后回看：结论、复杂度与回源¶
题意与结论：n 个正整数分成两个不相交子集，先让个数差最小，再让元素和的绝对差最大。取较小的 floor(n/2) 个为一组，剩余较大的 ceil(n/2) 个为另一组；用快速选择找到分界，无须完整排序。
思路推导：第一个目标先固定两组大小。对大小固定的一组，若“小值组”里有 x，而“大值组”里有更小的 y，交换 x、y 会让小值组的和下降、大值组的和上升，使有方向的和差增大；重复交换直到所有小组值都不大于大组值。n 为奇数且都是正数时，让较大值组同时多一个元素，达到绝对和差的最大值。
走一遍：[8,1,6,2,9]，n=5，target=2。较小两数是 [1,2]，和 3；较大三数是 [6,8,9]，和 23，个数差 1、和差 20。若小组误放 [1,6]，两组和为 7、19，差只有 12。这里需要的是两个集合，组内 [2,1] 和 [9,6,8] 也完全合格。
代码抓手与正确性：partition 返回 pivotPos。若它小于 target，只继续查右侧；大于 target，只继续查左侧；等于 target 就停止。目标是让下标 [0,target-1] 放较小的 target 个值，下标 target 是大组的第一个位置。与快排不同，每轮只追查一边，不递归排好两边。
为什么下标没有差一：target=2 时，小组占下标 0、1，大组从下标 2 开始。把排序意义上的下标 2 枢轴定位后，左侧恰有两个不大于分界的元素；不要求这两个自身有序。
复杂度与易错点：正式快速选择平均时间 O(n)，最坏 O(n²)；除输出数组外工作空间 O(1)。完全排序再切半也正确，但比较排序通常需 O(n log n)，做了多余工作。题设 n>=2、元素为正整数；若改成可含负数，特别是奇数长度时，不能不加分析照搬“大组取大值”的绝对和差结论。原文 0<=k<n 限定下标 k，不是把元素值限定为小于 n。
回源：PDF 第 27 页；回源 · PDF 第 27 页 · b_27_4；PDF 第 27 页 · b_27_5
。正式代码