[scheme学习笔记]递归插入排序
对数表进行排序,排序函数读入一个表,产生另一个表
即
;; sort : list-of-numbers -> list-of-numbers ;; to create a sorted list of numbers from all the numbers in alon (define (sort alon) ...)
例子为:
(sort empty) ;; expected value: empty (sort (cons 1297.04 (cons 20000.00 (cons -505.25 empty)))) ;; expected value: (cons 20000.00 (cons 1297.04 (cons -505.25 empty)))
如果输入为empty.则输出empty
因为sort是递归定义的.所以可以得出函数的模板为:
(define (sort alon)
(cond
((empty? alon)empty)
(else (...(first alon)...(sort (rest alon))))))
接着,需要处理的就是sort函数cond字句的第二部分.该部分包含两个表达式.先弄清楚他们结果分别是什么.
1.(first alon)输出数表的第一个数
2.(sort(rest alon))是对数表的剩下部分进行排序的结果
则可以知道.这个字句需要做的就是将(first alon)插入到表(sort(rest alon))中.
要讲数插入表.必须历遍整个表
此处,可以定义一个函数insert,它以一个数和一个表为参数.输出一个表.
insert定义如下:
;; insert : number list-of-numbers -> list-of-numbers ;; to create a list of numbers from n and the numbers on alon ;; that is sorted in descending order; alon is already sorted (define (insert n alon) ...))
如此.就可以给出sort的定义
(define (sort alon)
(cond
((empty? alon) empty)
(else (insert (first alon) (sort (rest alon))))))
现在.cond第二个字句的意义清晰了.要产生最终值.可先取出非空表的第一个数.再对其它部分进行排序.最后把前者插入到后者的合适部分.
剩下的部分就是对insert进行设计.
首先考虑insert做什么事情.
下面是例子
第一种情况
(insert 5 empty) ;; expected value: (cons 5 empty)
如果insert的第二个参数是非空表,
则第二种情况为
(insert 1297.04 (cons 20000.00 (cons -505.25 empty))) ;; expected value: (cons 20000.00 (cons 1297.04 (cons -505.25 empty)))
可以给出函数的模板
(define (insert n alon)
(cond
((empty? alon) ...)
(else ... (first alon) ... (insert n (rest alon)) ...)))
首先给出的表达式的结果
(first alon)得到的是数表的第一个数
(insert n(rest alon))得到一个排序完成的数表
接着考虑.insert的第二个参数为非空表时,可能出现以下两种情况
1.n>=(first alon) 因为alon是一个有序表,所以alon中所有数都不不会大于n,则用cons 把n 和alon组合在一起
2.n<(first alon).即
(insert 3 (cons 6 (cons 2 (cons 1 (cons -1 empty)))))
即(first alon)是6
(insert n (rest alon))是(cons 3 (cons 2 (cons 1 (cons -1 empty))))
这样的情况时.(first alon)是最大的数.所以它排在第一位,而n要插入(rest alon)之中.
这样.得到最终结果
(cons (first alon) (insert n (rest alon)))
于是.得到完整定义:
;; sort : list-of-numbers -> list-of-numbers (sorted)
;; to create a list of numbers with the same numbers as
;; alon sorted in descending order
(define (sort alon)
(cond
[(empty? alon) empty]
[(cons? alon) (insert (first alon) (sort (rest alon)))]))
;; insert : number list-of-numbers (sorted) -> list-of-numbers (sorted)
;; to create a list of numbers from n and the numbers on
;; alon that is sorted in descending order; alon is sorted
(define (insert n alon)
(cond
[(empty? alon) (cons n empty)]
[else (cond
[(>= n (first alon)) (cons n alon)]
[(< n (first alon)) (cons (first alon) (insert n (rest alon)))])]))
评论 (0)
