★ FEATURED ARTICLE 第一次看见“小丑排序”这个名字我心想这是不是那种故意把数据越排越乱的恶搞题。结果读完题面才发现正好相反它是一道非常正经的模拟题核心就一句话——先把数字排好序再按“左边一个、右边一个”的顺序重新输出。我第一次做是在某高校的程序设计实训作业里题号排在那一批训练题的中间位置难度不高但挺有意思尤其适合新手拿来练排序、双指针和边界判断。这篇就把这个题的完整解读、实现代码和我自己踩过的坑一次讲清楚。1. 题目拆解小丑排序真正要你做的事1.1 “小丑”这个比喻到底在描述什么先别急着开写咱们把题面里的“小丑”两个字拆开看。经典排序算法里冒泡排序靠相邻交换快速排序靠分治划分名字都对应着明确的操作过程。小丑排序不是那种教科书里的标准算法它是出题老师自己包装出来的一种规则题。为什么叫“小丑”因为取数过程很像小丑表演。想象一个小丑站在一队人面前他先冲到最左边拉出一个人放到新队伍里又冲到最右边拉出一个人放到新队伍后面然后继续回到左边、右边……直到原来的队伍被拉空。这种左右横跳的取人方式看起来就是小丑在台上蹦来蹦去。所以小丑排序的本质不是“发明一种新的排序算法”而是“先排序 按左右交替规则重排”。理解这一点后面所有代码都不难写。很多人一开始被名字唬住以为要用什么奇怪的数据结构其实底层就是数组和两个下标。1.2 手算一遍顺序是这么来的举个具体例子输入 n6六个数是 [6, 5, 4, 3, 2, 1]。第一步先排序得到 [1, 2, 3, 4, 5, 6]。然后设两个指针L 指向最左边的 1R 指向最右边的 6。取数过程如下取 a[L]1L 向右移动指向 2取 a[R]6R 向左移动指向 5取 a[L]2L 向右移动指向 3取 a[R]5R 向左移动指向 4取 a[L]3L 向右移动指向 4取 a[R]4R 向左移动指向 4最终输出 [1, 6, 2, 5, 3, 4]。注意观察输出结果既不是升序也不是降序而是像两端拉链一样交叉的序列。如果不看推导过程直接看输出很容易以为题目做错了实际上这就是小丑排序的标准效果。我第一次跑样例时还反复确认过后来才发现规律就是左右交替。1.3 这题真正训练的四个点这种题看起来简单但能一次性写对的人并不多。它至少考了四个方面数组排序要么自己写冒泡、选择要么调用语言自带的 sort。对新手来说自己写一个排序也能练手但做题优先用现成的稳。双指针思想左右两个下标同时往中间走不是所有题目都只用一个循环变量从头扫到尾。边界判断n 为奇数时最后左右指针会指向同一个元素处理不好就会重复输出。输出格式OJ 判题非常严格多一个空格、少一个换行都可能直接判错。这四个点合在一起正好是很多入门题的标准套路。所以这道题虽然顶着个花哨的名字实际价值就是帮你在一个简单场景里把这些基本功串起来。2. 思路设计为什么“先排序再双指针”是最优解2.1 为什么不建议硬模拟或者用链表有人可能会想能不能不排序直接用原数组左右轮流取不行。因为题面已经明确要求“先按编号从小到大排序”不排序的结果和样例输出对不上。也有人想用链表来模拟小丑拉人的过程每取一个人就把节点删掉这种做法虽然也能出结果但代码量大还容易在指针操作上翻车纯属给自己加难度。数组双指针是最直观的解法。它把“左右横跳”这件事映射成两个下标一个从左往右走一个从右往左走两个下标自然相遇时循环结束。不需要删除元素不需要维护链表关系只需要理解“指针移动”和“停止条件”。有人可能会担心排序之后所有数字的位置变了左右交替还是原来的顺序吗这里要分清楚小丑排序的定义就是“排好序之后的序列做左右交替”而不是“原始序列左右交替之后再排序”。顺序不能反这是做题最容易绕晕的地方。2.2 双指针是怎么把“左右横跳”翻译成代码的核心代码其实就一个 while 循环逻辑非常短while (left right) { if (left right) b.push_back(a[left]); if (left right) b.push_back(a[right--]); }这里有个关键细节为什么每次 push 之前都要判断一次 left right因为 n 为奇数时最后一次 left 和 right 会指向同一个元素。如果连写两次 a[left] 和 a[right--]同一个元素会被取两次输出序列里就会多出一个重复数字。我第一次写的时候就是没加这个判断n5 的样例直接输出了六个数字排查了半天才发现是边界问题。这种错误很经典代码看起来没问题一跑边界用例就露馅。顺便说一句先取左边还是先取右边完全看题面。有的版本描述成“小丑先走到最右边”那就把两条语句的顺序换一下。本质上没有差别但一定要以题目给定的顺序为准不能凭感觉。2.3 复杂度与数据范围拿不准先看这里排序调用系统 sort时间复杂度是 O(n log n)双指针过程每个元素只被访问一次是 O(n)所以整体是 O(n log n)。空间方面如果按下面代码建一个新数组 b额外空间是 O(n)如果直接边取边输出可以做到 O(1) 额外空间。对实训题来说n 一般不会太大几万到十万都很常见O(n log n) 完全够用。如果遇到 n 是 10^6 级别的变态数据也可以把代码改成边取边输出省掉 b 数组逻辑一样只是少了最后那层存储。时间复杂度这块不需要过度担心真正容易挂的是边界和格式不是性能。3. 完整代码两个语言版本逐行讲透3.1 C 参考实现C 更适合这种纯算法题标准库里的 sort 直接用代码干净利落。#include iostream #include vector #include algorithm using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); vectorint b; b.reserve(n); int left 0, right n - 1; while (left right) { if (left right) { b.push_back(a[left]); left; } if (left right) { b.push_back(a[right]); --right; } } for (int i 0; i n; i) { if (i) cout ; cout b[i]; } cout \n; return 0; }逐行说几个容易忽略的地方ios::sync_with_stdio(false);和cin.tie(nullptr);是 C 的输入输出加速配置。实训 OJ 的测评数据可能很大加上之后能明显减少读写耗时属于写 C 题的默认习惯。b.reserve(n)提前分配容量避免 push_back 过程中反复扩容带来的性能损耗。sort(a.begin(), a.end())默认从小到大排序完全符合题意。输出那段if (i) cout ;是“第一个数前不加空格”的标准写法避免行尾多一个空格被判 Presentation Error。3.2 Python 参考实现如果学校允许用 Python那这个题就更简单了。Python 的 sort 和 join 能省掉不少麻烦。def main(): n int(input()) a list(map(int, input().split())) a.sort() b [] left, right 0, n - 1 while left right: if left right: b.append(a[left]) left 1 if left right: b.append(a[right]) right - 1 print( .join(map(str, b))) if __name__ __main__: main()Python 版本里最需要注意的是输入方式。input().split()默认按空白字符切分能处理行尾换行和多个空格。但如果题目输入不是固定在一行而是可能跨行给出那input()一次只会读一行会有问题。更稳妥的做法是用sys.stdin.read().split()一次性读入全部数据再按顺序取。import sys def main(): data list(map(int, sys.stdin.read().split())) n data[0] a data[1:1 n] a.sort() ...这个写法更抗造不管数字分成几行输入都能正确处理。我在提交 Python 版本时基本都会用这种方式省得被输入的换行格式坑到。3.3 两种写法共同的三个隐藏注意点这里总结三个我实际踩过的坑C 和 Python 都会遇到。第一个是循环条件必须写left right不能写成。写成的话当 n 为偶数时最后两个元素之间会少取一次当 n 为奇数时中间的那个元素根本不会被取到最终输出会比 n 少一个数。第二个是排序方向。默认 sort 是升序这没问题。但如果题面要求“编号从大到小排序后再依次取出”那就得改成降序。C 里写sort(a.begin(), a.end(), greaterint())Python 里写a.sort(reverseTrue)。做题前一定要看清题面我见过不少同学在这个地方阴沟翻船。第三个是多组测试用例的情况。我做的这版题目只有一组输入但有些学校的题库会把题目包装成“多组输入直到 EOF”。C 可以写成while (cin n)Python 可以放在while True里用 try/except 捕获结束。如果题目没提多组就按单组处理不要多此一举。4. 实战避坑样例过了为什么还是 WA4.1 边界条件里的“奇偶陷阱”这是最容易出问题的一个点。拿 n5 和 n6 分别手算一遍对比一下结果n排序后数组小丑排序结果5[1, 2, 3, 4, 5][1, 5, 2, 4, 3]6[1, 2, 3, 4, 5, 6][1, 6, 2, 5, 3, 4]n5 时最后一次 left 和 right 都指向 3只能取一次。n6 时倒数第二次取完 3 和 4left 变成 4right 变成 3循环结束没有重合的元素。如果你写的循环是while (left right)那 n5 时中间那个 3 会漏掉。如果你写的是while (left right)但循环体里不判断那 n5 时 3 会被取两次。两种情况都会 WA。最好的办法就是循环体里保留两个if (left right)判断一个多余动作都不做。虽然看起来有点啰嗦但这就是防御性编程的典型写法用一点代码冗余换取逻辑正确。4.2 输出格式空格和换行的门道OJ 判断输出时通常对空格数量很敏感。很多题目要求“相邻数字之间用一个空格分隔”如果行尾多出一个空格可能直接给你一个 Presentation Error有时也会算 WA。推荐的输出方式有两种。一种是 C 里的if (i) cout ;也就是在非第一个元素前补空格行尾自然没有多余空格。另一种是先拼字符串用 Python 的 .join(map(str, b))这个直接就是标准格式。另外别忘输出行尾换行。虽然很多 OJ 的 checker 对末尾换行不敏感但统一写上cout \n或print()更稳妥。你要是忘了换行有些评测系统可能会把下一组数据的内容跟当前输出连在一起导致结果判定异常。4.3 题目变体出现时怎么快速改代码刷题多了你会发现同一个“小丑排序”在不同学校的题库里可能有细微差别。最常见的有三种变体。第一种是取数顺序变了题目要求“先取最右边再取最左边”。这种最简单把代码里两条if语句对调位置即可逻辑完全不变。第二种是排序方向变了要求按编号从大到小排序后再左右交替。C 里给 sort 加一个 greater 比较器Python 里给 sort 加 reverseTrue其他都不用动。第三种是规则完全不同的版本不是先整体排序而是每次从原序列里取当前最大和最小的数放到新序列两端。这种已经不是同一个题了需要换思路通常要用 multiset 或者双端队列维护两端最值复杂度也会变成 O(n log n) 加一些数据结构操作。怎么判断是哪种版本看题面里有没有“先按编号排序”这句话。有就是本文这个版本没有可能是每轮动态选最大最小。做题第一件事永远是圈出规则里的顺序词把“先”“再”“最后”这些字眼全标出来再开始想代码。我实训时见过同学拿着另一个版本的题面来问一对细节才发现大家做的根本不是同一个题比赛和作业里这种事特别多。最后分享一个我的个人习惯拿到这种排序加模拟的题不要急着敲代码先在纸上把 n5 和 n6 两种情况手算一遍把左右指针每次指向的位置标出来。这样既能确认自己对题意的理解没错又能顺便把循环边界检查一遍。这个小习惯帮我省了不少 debug 时间也推荐你试一试。毕竟小丑排序看起来花哨本质还是基础功。
阅读完成 · 觉得有帮助？
