# 插入排序

## 如何把一个数字插入到一个列表中

;; using insert sort here

(define insert
(lambda (lst elem)
(cond ((null? lst) (list elem))
((< elem (car lst))
(cons elem lst))
(else (cons (car lst)
(insert (cdr lst) elem))))))

(define sort-rec
(lambda (prev now)
(if (null? now)
prev
(sort-rec (insert prev (car now))
(cdr now)))))
(define sort
(lambda (lst)
(sort-rec '() lst)))



## 提取出判断条件

(define insert
(lambda (lst elem pred)
(cond
((null? lst) (list elem))
((pred elem (car lst))
(cons elem lst))
(else (cons (car lst)
(insert (cdr lst) elem pred))))))


(insert '(1 2 3) '4 <)
(1 2 3 4)
(insert '(1 2 3) '0 <)
(0 1 2 3)
(insert '(1 3 2) '4 <)
(1 3 2 4)    ==> 这不是我们想要的


## 对一个列表进行插入排序

• sort-rec 逐个判断最新的元素和新的临时列表的比较
• sort-predicate 仅仅是选择判断的标准。
(define sort-rec
(lambda (prev now pred)
(if (null? now)
prev
(sort-rec (insert prev (car now) pred)
(cdr now)
pred))))

(define sort/predicate
(lambda (pred lst)
(sort-rec '() lst pred)))


• sort-rec的prev在逐渐的变大，而now的部分在不断的变小
• 也就是 sort-rec 的第一号位置不断变大，第二号位由于cdr作用不断变小。

(sort/predicate < '(1 6 5 7))

prev          now
1.  ()         (1 6 5 7)
2.  (1)        (6 5 7)
3.  (1 6)      (5 7)
4.  (1 5 6)    (7)
5.  (1 5 6 7)  ()



(sort/predicate < '(1 6 5 7))
(1 5 6 7)


## 利用内部define和letrec改写程序

• 采用内部的define实现

(define sort/predicate1
(lambda (pred lst)
(define sort-rec
(lambda (prev now pred)
(if (null? now)
prev
(sort-rec (insert prev (car now) pred)
(cdr now)
pred))))
(define insert
(lambda (lst elem pred)
(cond
((null? lst) (list elem))
((pred elem (car lst))
(cons elem lst))
(else (cons (car lst)
(insert (cdr lst) elem pred))))))

(sort-rec '() lst pred)))

(sort/predicate1 < '(1 6 5 7))


• 采用letrec实现sort/predicate,主要是用(letrec (() ...) ...) 结构

(define sort/predicate2
(lambda (pred lst)
(letrec ((sort-rec
(lambda (prev now pred)
(if (null? now)
prev
(sort-rec (insert prev (car now) pred)
(cdr now)
pred))))
(insert
(lambda (lst elem pred)
(cond
((null? lst) (list elem))
((pred elem (car lst))
(cons elem lst))
(else (cons (car lst)
(insert (cdr lst) elem pred)))))))

(sort-rec '() lst pred))))

(sort/predicate2 < '(1 6 5 7))



## 结论

1. 每隔离一层抽象，相当于增加了一种变化
2. 了解插入排序的实现过程。
##### 令狐冲
###### Engineer of offshore wind turbine technique research

My research interests include distributed energy, wind turbine power generation technique , Computational fluid dynamic and programmable matter.