Scheme实现快排：给定pivot和列表如何让partition返回两个子列表

需求与现有问题 #

你需要实现的partition接收两个参数：枢轴pivot、待处理列表，调用样例：

> (partition '3 '(5 7 8 6 4 2 1)) 

期望输出：

;;Value: ((2 1) (3 5 7 8 6 4))

即返回嵌套列表，第一个子列表是所有小于枢轴的元素，第二个子列表以枢轴开头，后续为所有大于等于枢轴的元素。

你当前编写的代码存在多处逻辑错误，运行时触发报错：

具体错误点：

• 参数语义不匹配：定义的函数形参是比较函数lt?和列表lst，和需要的「枢轴+待处理列表」参数逻辑完全不符
• 比较逻辑错误：代码中拿列表首元素和相邻的第二个元素比较，完全没有引入枢轴作为比较基准
• 边界处理缺失：递归到列表仅剩1个元素时，(cdr lst)为空表，执行(car rest)会直接触发空表取首元素的运行时错误
• 返回值结构错误：代码用values返回两个独立值，和需要的双元素嵌套列表结构不一致

修正后代码 #

(define (partition pivot lst)
  (let loop ((remain lst) (smaller '()) (ge '()))
    (cond
      ((null? remain)
       (list (reverse smaller) (cons pivot (reverse ge))))
      ((< (car remain) pivot)
       (loop (cdr remain) (cons (car remain) smaller) ge))
      (else
       (loop (cdr remain) smaller (cons (car remain) ge))))))

代码用尾递归遍历列表，遍历过程中把元素按和枢轴的大小关系分到两个分组里，遍历完成后按要求组装结果，不会出现空表操作的异常。

验证结果 #

运行测试用例：

(partition '3 '(5 7 8 6 4 2 1))

输出完全符合预期：

((2 1) (3 5 7 8 6 4))

内容的提问来源于stack exchange，提问作者5u5man