2026 年 1 月 31 日我照例做 Go 算法题的月度复盘翻到一道看着人畜无害、实际上把“数组”“顺序”“分组”三个关键词全考一遍的题。题面不长order 是一个长度为 n 的数组装着 1 到 n 的全部编号且互不重复数组元素的先后位置表示选手完成比赛的先后次序friends 是一个按升序排列的数组代表你的朋友名单。要求用 Go 把完成顺序重排让朋友们整体排到前面同时朋友之间、非朋友之间的相对顺序都不能打乱。这题在算法名词里叫稳定分区。它不考什么高深算法考的是对切片、哈希表、排序稳定性的理解和组合能力是典型“面试十分钟、代码二十行、坑有一箩筐”的题目。我把暴力解、哈希解、bool 索引解全部实现了一遍又跑了多组边界数据最后沉淀出这篇文章。不管你是准备笔试还是想在真实项目里做“按条件分组但保留入场顺序”的需求下面的分析都可以直接抄。1. 把题目翻译成人话1.1 输入数据在描述什么场景先把这个题还原成真实画面一场比赛n 个选手冲线order 数组就是裁判记录下来的名次表。比如 order [4,2,5,1,3]意思是 4 号选手第一个完赛2 号第二5 号第三1 号第四3 号第五。注意 order 里不会出现重复编号也不会缺漏1 到 n 每个都在里面。这是整个题最关键的一个性质。friends 数组表示“你要关注的朋友”比如 friends [1,3]。题目特别强调它是按升序排列的这说明朋友名单里没有重复项而且所有值一定落在 1 到 n 之间。放到场景里就是你手里有一张按号码排好序的好友列表比赛结束后你想把好友们的排名统一置顶方便一眼看到他们分别跑了第几。所以“重排完成顺序”这句话说白了就是把 order 这张名次表重新洗一遍——朋友优先全部挪到表头不是朋友的选手按原样跟在后面。而且不管是朋友还是非朋友内部的相对次序必须和原 order 完全一致因为名次表反映的是“谁先谁后”你只能调整分组位置不能篡改选手之间的真实先后。1.2 “重排”到底要满足什么规则用一个例子把这三点规则钉死。原 order [4,2,5,1,3]friends [1,3]朋友的集合是 {1,3}。在原表里1 号在第四位3 号在第五位所以朋友内部的相对顺序是 1 先 3 后。非朋友是 {2,4,5}。在原表里依次是 4、2、5所以非朋友内部顺序是 4、2、5。合并起来合法输出是 [1,3,4,2,5]。几个常见错误答案正好用来反证规则[3,1,4,2,5] 错在朋友内部顺序被逆转成 3 先 1 后与原表矛盾[4,2,5,1,3] 错在朋友没有被置顶[1,4,2,5,3] 错在朋友集合没有整体靠前3 被甩到了最后。这种“既要分区、又要保序”的约束就是稳定分区的定义。理解了这一点解法其实自己就会长出来。1.3 隐藏在题目里的两个关键线索面试官不会平白无故写“包含 1 到 n 的所有编号且互不重复”和“按升序排列”这两句话它们就是性价比最高的线索。第一编号是 1 到 n 的连续整数。这意味着“判断某个选手是不是朋友”根本不需要哈希表开一个长度为 n1 的 bool 切片用编号当下标直接 O(1) 命中且内存远小于 map。如果编号是零散的大整数比如身份证号那才轮到 map 上场。第二friends 按升序等于告诉你它内部无重复。这样你不用担心 friends 里有重复编号导致置顶后重复出现同时也暗示你成员判断可以用二分查找做。不过后面会看到二分查找反而是小题大做bool 切片才是最优解。抓住这两条线索最优解基本就浮出水面了。2. 从暴力到优雅三种解法递进2.1 最直观的双临时数组法先写一个绝对正确但看起来“笨”的方案准备两个空切片一个装朋友一个装非朋友遍历 order 一次按成员判断结果分别 append最后把两个切片拼起来。Go 代码长这样func reorderDoublePass(order, friends []int) []int { isFriend : make(map[int]bool, len(friends)) for _, id : range friends { isFriend[id] true } friendPart : make([]int, 0, len(friends)) otherPart : make([]int, 0, len(order)-len(friends)) for _, id : range order { if isFriend[id] { friendPart append(friendPart, id) } else { otherPart append(otherPart, id) } } return append(friendPart, otherPart...) }这个写法正确性一目了然append 天然保序朋友切片与非朋友切片内部都严格按 order 的遍历顺序收集最后拼接时朋友部分在左、其他在右分区也满足。时间复杂度 O(n)空间复杂度 O(n)。缺点是用了两个临时切片代码上多了一次拼接而且 append 拼接有容量层面的隐藏细节后面的踩坑章节会细说。2.2 稳定分区背后的原理为什么不能直接排序很多人第一反应是这还不简单用 sort.Slice 按“是否朋友”排一下不就行了比如sort.Slice(order, func(i, j int) bool { return isFriend[order[i]] !isFriend[order[j]] })看起来朋友会被排到前面但这里有个致命问题sort.Slice 不是稳定排序。当两个元素都是朋友、或者都不是朋友时比较器返回 false排序算法会把它们当作“相等”而 Go 的排序内部用的是 pdqsort 这类不稳定算法相等元素经过多次交换后相对顺序可能彻底乱掉。换句话说朋友内部、非朋友内部的原始顺序无法保证。有人会说那用 sort.SliceStable 不就行了确实行SliceStable 会保留相等键的原始相对顺序代码只有几行。但它把时间复杂度从 O(n) 直接拉高到了 O(n log n)。n 是 10 万时无所谓n 是 1000 万时就慢了一个数量级。更重要的是这是一道考“如何利用数组本身结构”的题直接用排序属于拿大炮打蚊子掩盖了真正想考察的稳定分区思想。正确的思路是既然我们只关心“朋友/非朋友”这一个二元属性而且要求各组内部保持原序那就用遍历收集而不是排序。遍历时元素的相遇顺序天然等于原 order 顺序只要分别收集再拼接保序是白送的。这是稳定分区和普通分区的根本区别。2.3 bool 数组索引优化与两趟遍历法顺着 1.3 的线索优化把 map 换成 bool 切片代码还能更干净。由于 order 保证包含 1 到 n 的全部编号且不重复friends 也必是 1 到 n 的子集直接声明 isFriend : make([]bool, n1)把 friends 里的编号对应下标置为 true之后每个 order 元素的判断就是一次切片下标访问连哈希计算都省了。在此基础上可以进一步改成“两趟遍历”第一趟只收朋友第二趟只收非朋友都写入同一个 result 切片。这样连两个临时切片都不用代码节奏更线性func reorder(order, friends []int) []int { isFriend : make([]bool, len(order)1) for _, id : range friends { isFriend[id] true } result : make([]int, 0, len(order)) for _, id : range order { if isFriend[id] { result append(result, id) } } for _, id : range order { if !isFriend[id] { result append(result, id) } } return result }效果和双数组法完全一致但少了一个切片、少了一次拼接逻辑也更接近“先把朋友全部挑出来再把剩下的接在后面”这道题的本意。这个版本就是本文推荐的主解法。2.4 顺带一提原地重排可行吗有的读者会追问能不能不申请 result直接在 order 原数组上做稳定分区把额外空间压到 O(1)答案是可行但很没必要。经典的原地稳定分区要借助块交换或旋转操作代码复杂、常数很大时间往往退化成 O(n log n) 甚至 O(n²)。Go 的切片模型本身鼓励“复制到新切片”额外 O(n) 空间在绝大多数业务场景下根本不是瓶颈。我在面试时如果候选人主动提原地方案会认可他知识面广但更希望他先给出清晰、正确的 O(n) 空间版本。可读性和正确性永远优先于炫技。3. Go 语言实现细节与完整代码3.1 成员资格判断map、bool 数组和二分查找怎么选这一节把“判断 friends 成员”的三种姿势放在一起对比。构建 friends 集合是重排的前提选错会影响常数但不影响复杂度量级。方式构建时间查询时间额外空间适用场景map[int]boolO(m)O(1)约几十字节/元素m 大时内存高编号零散、不连续、可能是大整数bool 切片O(m)O(1)n1 字节极小编号恰好是 1..n本题就是sort.Search 二分无需构建O(log m)无friends 已排序且 n 很小不想额外内存注意二分查找有个陷阱对每个 order 元素都做一次 O(log m) 查询总时间是 O(n log m)。n 是 10^6 时大约要做 2000 万次比较和 O(n) 的 bool 切片相比慢了近一个数量级。这算是“合理但次优”的典型。直接给结论题目给了 1..n 的强保证bool 切片是碾压级选手。只有当编号范围完全不可控时才退回 map。3.2 完整可运行的代码与逐步注释把上面的判断整合成一份完整体包含 main 和测试package main import fmt // reorder 稳定重排 order // friends 中的编号全部靠前朋友内部与非朋友内部均保持原 order 相对顺序。 func reorder(order, friends []int) []int { // 1. 用 bool 切片标记朋友下标就是编号 isFriend : make([]bool, len(order)1) for _, id : range friends { if id 1 id len(order) { isFriend[id] true } } // 2. 第一趟按原序收集所有朋友 result : make([]int, 0, len(order)) for _, id : range order { if isFriend[id] { result append(result, id) } } // 3. 第二趟按原序收集所有非朋友 for _, id : range order { if !isFriend[id] { result append(result, id) } } return result } func main() { // 用例一基础场景 fmt.Println(reorder([]int{4, 2, 5, 1, 3}, []int{1, 3})) // 期望 [1 3 4 2 5] // 用例二friends 为空 fmt.Println(reorder([]int{4, 2, 5, 1, 3}, []int{})) // 期望 [4 2 5 1 3] // 用例三friends 包含全部选手 fmt.Println(reorder([]int{4, 2, 5, 1, 3}, []int{1, 2, 3, 4, 5})) // 期望 [4 2 5 1 3]整体顺序不变 // 用例四极端最小 fmt.Println(reorder([]int{1}, []int{1})) // 期望 [1] }逐步解释第一步把 friends 变成 O(1) 可查的标记表第二步的 for range 变量 id 是按顺序出现的因此结果切片里的朋友自然保持原相对顺序第三步同理。整个函数没有排序、没有交换所有顺序都由遍历顺序本身保证这就是稳定分区最舒服的写法。3.3 测试用例设计比你想的要多这道题的正确性高度依赖边界我列一张自测表提交前建议对着过一遍用例orderfriends期望结果基础[4,2,5,1,3][1,3][1,3,4,2,5]无朋友[4,2,5,1,3][][4,2,5,1,3]全是朋友[4,2,5,1,3][1,2,3,4,5][4,2,5,1,3]单选手且是朋友[1][1][1]单选手非朋友[1][][1]朋友首尾分布[1,9,2,8,3][1,3,9][1,9,3,2,8]朋友首尾分布这行很能暴露问题原 order 里 1 在最前、3 在倒数第二、9 在第二。期望输出 [1,9,3,2,8]原因是朋友按原序是 1、9、3非朋友按原序是 2、8。如果你用不稳定排序处理很容易得到 [1,3,9,2,8] 这类错误答案。3.4 关于切片的三个坑第一个坑是 append 拼接的容量问题。双临时数组法里 return append(friendPart, otherPart...) 看起来没问题但 friendPart 如果容量还有富余拼接会直接写在 friendPart 的底层数组上一旦函数外部还持有 friendPart 的引用数据就被污染。虽然我们函数内 friendPart 不会再被使用写成这样属于安全行为但这种隐式共享很容易在代码演进中埋雷。我习惯用独立的 result 收口像 3.2 那样不给别名留机会。第二个坑是试图复用 order 的原底层数组比如 order order[:0] 再往里写。这样确实省内存但会破坏调用方持有的 order 视图工程上容易引发严重 bug。除非题目明确说“可以原地修改”否则一律返回新切片。第三个坑是 range 循环里对同一个切片做写操作。比如有人想边遍历边把朋友交换到前面同时 range 还在读原下标交换后的元素可能被跳过或重复处理。这类自修改代码是稳定分区最容易出错的地方老老实实用两趟只读遍历最稳。4. 踩坑实录四类常见错误4.1 用 sort.Slice 直接排朋友内部顺序被打乱第一个高频错误就是 2.2 里说的不稳定排序。我见过不少实现长这样sort.Slice(order, func(i, j int) bool { return isFriend[order[i]] !isFriend[order[j]] })对大多数随机数据它输出的朋友组内部顺序是乱的。比如 order [1,9,2,8,3]friends [1,3,9]这个比较器在排序时把键相同的元素互相交换实际可能得到 [1,3,9,2,8]而正确答案是 [1,9,3,2,8]。关键是这种错误不是必现的数据少时排序网络可能恰好保持原序数据一多就露馅。这也是我坚持“不用排序解决分组”的原因——效果依赖数据分布等于定时炸弹。4.2 friends 有序于是用二分查找做成员判断复杂度反而更糟第二个错误是把“friends 按升序”直接翻译成“我要用二分”。每个 order 元素都做一次 sort.Search时间复杂度 O(n log m)。看起来只多一个 log但 n10^7、m10^5 时比较次数差了两个数量级实测能慢到几百毫秒对比几十毫秒。friends 排序的用途不是为二分准备的而是为“集合构建简单”和“无重复”准备的。真正该做的是用 bool 切片一次到位。4.3 复用 order 的底层数组导致原数据被改坏还有同事为了省空间写过这样的代码order append(order[:0], friendPart...) order append(order, otherPart...)这在本地跑没问题一旦 order 是别人传进来的切片调用方之后再用 order数据已经面目全非。Go 的切片是引用类型函数内 append(order[:0], ...) 修改的是底层数组对调用方完全可见。如果是库函数这种悄悄改入参的行为特别阴。我的原则函数如无特殊说明绝不修改入参切片要返回新切片就用新的 result。4.4 认为“不需要保留非朋友顺序”最后一个错误是审题问题。有一类解法先把朋友筛选出来然后用交换把朋友逐个放到数组头部。交换操作会破坏非朋友内部的相对顺序。比如 order [1,9,2,8,3]如果交换可能得到朋友置顶了但非朋友中间的顺序被搞乱最后非朋友变成 [8,2,3] 而不是 [2,8,3]。出题人特意在题干里写了“朋友之间、非朋友之间的先后次序保持不变”这句话不是废话审题时千万别跳过。把需求抄成伪代码再动手这类错能少一半。5. 复杂度与工程视角5.1 复杂度推演把几种方案放在同一张表里看方案时间复杂度空间复杂度稳定性双重循环逐个找朋友O(nm)O(1)稳定map 双临时切片O(nm)O(nm)稳定bool 切片 两趟遍历O(nm)O(n)稳定sort.Slice 不稳定排O(n log n)O(1)不稳定错误sort.SliceStable 稳定排O(n log n)O(n)稳定从表里能看出bool 切片 两趟遍历是理论最优线性时间、线性空间、实现最短、稳定性天然满足。n 再大也只是两遍 for 循环不会出现排序那样的 log n 因子。工程上如果 n 是百万级它跑完大概个位数毫秒千万级也在几十毫秒量级性能完全够用。空间上再给一个直觉n10^6 时bool 切片 len(order)1 大约占 1MB因为 Go 的 bool 是 1 字节而 map 存一百万条记录轻松超过 50MBGC 压力也大。这个差距在内存敏感的服务里是实打实的。5.2 这个算法思想在真实项目里的影子稳定分区并不是竞赛专属。常见的例子是 App 的消息列表VIP 用户的消息要置顶但同一分组内继续保持时间倒序再比如待办系统把“紧急”任务提到前面但紧急任务之间仍按创建时间排。这些需求抽象出来全是我们这道题的变体按某个二元属性分组组内保留原有排序键。还有一个更底层的影子计数排序、基数排序的“稳定分配”步骤本质上就是多趟遍历收集——先按低位分桶再按桶序拼接。理解了稳定分区再去看基数排序的代码会通透很多。这也是我推荐大家重视这道题的原因它训练的不是某个 API而是“如何在保留顺序的前提下重排数据”这一种通用思维。6. 变式与进阶换一个问法你还认识它吗6.1 变式一不重排 order而是把 friends 按完成次序输出题目如果换一个问法很多人就认不出来了不要求你把 order 整个重排而是只输出 friends 中选手的完成次序。比如 order [4,2,5,1,3]friends [1,3,4]期望输出 [4,1,3]因为 4 号第一、1 号第四、3 号第五。这时角度完全反过来friends 是待排序对象order 是权重来源。解法是先遍历 order记录“编号 → 名次”的映射 pos再对 friends 做 sort.Slice按 pos 升序排package main import ( fmt sort ) func friendsRank(order, friends []int) []int { pos : make(map[int]int, len(order)) for i, id : range order { pos[id] i } result : append([]int(nil), friends...) sort.Slice(result, func(i, j int) bool { return pos[result[i]] pos[result[j]] }) return result } func main() { fmt.Println(friendsRank([]int{4, 2, 5, 1, 3}, []int{1, 3, 4})) // 期望 [4 1 3] }注意这里也可以用 int 切片做索引rank : make([]int, len(order)1)把 order[i] 对应的下标 i 存进去查询就是 rank[id]比 map 更快。这个变式的核心是“把数组下标当作值来用”order 的 index 本身就是名次这一步想通题就解开了。6.2 变式二要求 friends 内部按编号升序如果把约束改成“朋友整体置顶但朋友内部按编号升序非朋友内部保持原序”问题就变成了“部分稳定、部分排序”。做法是先按稳定分区拿到基本结果再对结果的朋友段做一次升序排序或者更省事地先对 friends 排序它本来就升序再按 1.2 的做法收集——因为收集时朋友内部已经按编号升序收集顺序自然满足要求。这类混合约束在真实需求里很常见。我的经验是先拆解成“分区 排序”两个独立步骤分别验证正确性最后组装。不要试图写一个复杂的比较器覆盖所有规则那只会让代码和测试都失控。6.3 变式三数据量极大且 friends 数量很小如果 n 很大比如亿级friends 只有十几个bool 切片仍要 O(n) 空间有点浪费。可以退而求其次只对 friends 建 map然后第一趟收集朋友第二趟收集非朋友。空间变成 O(m)时间仍是 O(n)。本质上还是同一套代码把 isFriend 从 bool 切片换成 map 即可。所以 bool 切片的优势只在 n 和 m 同量级时明显m 远小于 n 时 map 更划算。这类权衡题在系统设计面试里也常出现平时做题时多留个心眼收益不小。写到这里这道“重排完成顺序”的 Go 实现基本讲透了。我个人最想强调的一点是读题时一定要把“1 到 n 不重复”这类强约束当成天上掉的馅饼它直接决定了你能不能用 bool 切片、能不能压掉 map也决定了最终代码能在多大数据量下跑得轻松。落到代码层面稳定分区就用“先收集朋友、再收集非朋友”的两趟遍历任何花哨的交换和排序都是给自己挖坑。最后送一个小习惯每道数组重排题都先在纸上写出“规则三件套”——哪组在前、组内按什么序、是否允许修改入参再动手写 Go 代码。这三个问题想清楚Bug 能少七八成。