;;快速排序
(defun filter (predicate x lst)
(if (null lst)
'()
(if (funcall predicate x (car lst))
(cons (car lst) (filter predicate x (cdr lst)))
(filter predicate x (cdr lst)))))
(defun qsort (lst)
(if (null lst)
'()
(append (qsort (filter '> (car lst) (cdr lst)))
(list (car lst))
(qsort (filter '< (car lst) (cdr lst))))))
(qsort (list 4 3 2 9 1 33 78 29 100 99 0))
;;插入排序
(defun insert-item (sequence item fn)
(if (null sequence)
(list item)
(if (funcall fn (car sequence) item)
(cons (car sequence) (insert-item (cdr sequence) item fn))
(cons item sequence))))
(insert-item '(5 6 9) 7 '<=)
(defun my-sort (sequence fn)
(defun _sort (sequence sort-seq fn)
(if (null sequence)
sort-seq
(_sort (cdr sequence) (insert-item sort-seq (car sequence) fn) fn)))
(_sort sequence '() fn))
(my-sort '( 9 7 8 10 5 6 7 2 3 ) '<=)
;;归并排序
(define (merge left right)
(cond [(null? left)
right]
[(null? right)
left]
[else
(let f ((left left) (right right))
(cond [(null? left)
right]
[(null? right)
left]
[(<= (car left) (car right))
(cons (car left) (f (cdr left) right))]
[(> (car left) (car right))
(f (cons (car right) left) (cdr right))]))]))
(merge '(1 7 8 ) '(3))
(merge '(0 7 11 44 ) '())
(define (mergesort ls)
(cond
[(null? ls) '()]
[(pair? ls)
(let ((left (mergesort (car ls)))
(right (mergesort (cdr ls))))
(merge left right))]
[else (list ls)]))
(mergesort '(9 2 4 10 1 0 2 38))
阅读(3643) | 评论(0) | 转发(0) |
