我知道Racket's stdlib，但我想自己实现一个排序功能作为练习 . 我决定使用合并排序算法，因为它在递归术语中自然定义 . 很快我就提出了工作代码，但它运行得太慢了 . 在我看来，运行时间是列表大小的指数，虽然理论上它应该是 O(n·log n) .
这是我的代码：
#lang racket
(define (pair x y) (list x y))
(define (split input)
(cond
[(empty? input) (pair null null)]
[(empty? (rest input)) (pair input null)]
[else
(let [(tail (cddr input))]
(pair (cons (first input) (first (split tail)))
(cons (second input) (second (split tail)))))]))
(define (merge input1 input2)
(if (ormap empty? (list input1 input2))
(append input1 input2)
(if (< (first input1) (first input2))
(cons (first input1) (merge (rest input1) input2))
(cons (first input2) (merge input1 (rest input2))))))
(define (sort input)
(cond
[(empty? input) null]
[(empty? (rest input)) input]
[else
(let [(halves (split input))]
(merge (sort (first halves)) (sort (second halves))))]))
(define (sorted? input)
(cond
[(empty? input) #t]
[(empty? (rest input)) #t]
[else
(and (<= (first input) (second input))
(sorted? (rest input)))]))
似乎我使用了一些“原子”操作，它不会像我想象的那样在恒定时间内运行，但是我无法弄清楚哪些操作 . 30个随机项目的分类是瞬时的，40个项目在几秒钟内处理，50个项目需要半分钟 . 所以我想知道，障碍在哪里？
1 回答
在
split中，您调用(split tail)两次而不是使用let运行一次并将结果存储到变量中 . 这可能会使split呈现指数时间 .