The Way 2 Inner Peace.

[转]Scheme 之道 --- 无处不在的函数
[scheme学习笔记]二叉树的遍历

[scheme学习笔记]scheme中的快速排序和合并排序

Qians posted @ 2011年11月11日 21:30 in scheme with tags lisp Scheme 排序 算法 递归 , 3260 阅读

 

 
 
快速排序:
快速排序是分而治之思想的体现,即将非平凡可解的问题分成相关的两个小问题.分别解决这两个小问题.再将所得结果合并起来.
具体来说.quick-sort先讲数表分成两个表.其中第一个表中所有元素小于原表中第一个元素.第二个表中元素大于等于原表中第一个元素.然后对这两个表使用同样的方法进行排序.最后再将他们连接起来.就得到了排序好的表.可设第一个元素为关键元素.
 
假设输入为
(list 11 8 14 7)
手工计算
关键元素:11
分成的两个表为
(list 8 7)
(list 14)
对第一个表使用相同方法排序.可以得到
(list 7 8)
如此.原来的表被分为三部分
1.(list 7 8)
2.11
3.(list 14)
现在将三部分合并起来,即可得到排序完成的表:
(list 7 8 11 14)
表格说明如下:
 
 
那么quick-sort就是一个递归的函数.当它遇到空表empty(即'())时停止.
先定义一个函数filter.(在racket的库中已经提供.).用于选出一个表中是某个函数为真的所有元素.此判定函数依次作用于表中所有函数.
;;filter:listX-listX
(define (filter pred list)
  (cond
    ((empty? list) list)
    (else (cond
          ((pred (car list))
           (cons (car list) (filter pred (cdr list))))
          (else (pred (cdr list)))))))
 
 
运用filter.可以写出分开两个表的表达式.
那么.quick-sort可以定义了
(define (q-sort lst)
  (if (null? lst)
      lst
      (append (q-sort (filter (lambda (x) (<= x (car lst))) (cdr lst)))
              (list (car lst))
              (q-sort (filter (lambda (x) (> x (car lst))) (cdr lst))))))
 
归并排序:
这个我也没理解透.只是按照how to design programs 习题 26.1.2一步步做出来的.
先抄题.
 
习题 26.1.2 开发函数 merge-sort,对数表排序(升序排列),使用如下两个辅助函数:
1. 第一个辅助函数 make-singles,它使用给定的表中的数构造一个单元素表的表。例如,
(equal? (make-singles (list 2 5 9 3))
(list (list 2) (list 5) (list 9) (list 3)))
2. 第二个辅助函数merge-all-neighbors,它合并相邻的两个表。更精确地说,它读入一个(数)表
的表,合并相邻的表。例如,
(equal? (merge-all-neighbors (list (list 2) (list 5) (list 9) (list 3)))
(list (list 2 5) (list 3 9)))
(equal? (merge-all-neighbors (list (list 2 5) (list 3 9)))
(list (list 2 3 5 9)))
一般来说,这个函数生成一个大概是输入表一半长的表。为什么输出的表并不总是输入表的一半
长?
确保这两个函数的开发相互独立。
函数 merge-sort 首先使用make-singles 把输入表分割为由单元素表组成的表;然后不断地使用
merge-all-neighbors 合并表,并且每次都使用sort 函数对每个小表排序,直至最终得到单一的表;最后这个
表就是merge-sort 的返回值。
 
代码如下.
;;merge-sort:list->list
(define (merge-sort x)
  (define (merge-sort-worker x)
    (if (= (length x) 1)
        (car x)
        (merge-sort-worker (merge-all-neighbors x))))
  (merge-sort-worker (make-singles x)))

    

;;make-singles:alon-> lists of number
(define (make-singles alon)
  (cond
    ((empty? alon) empty)
    (else (cons(cons (first alon) empty) (make-singles (rest alon))))))

;;merge-all-neighbors:lists->list
(define (merge-all-neighbors alist)
  (cond
    ((empty? alist) empty)
    ((empty? (rest alist)) empty)
    (else (cons (sort (append (first alist)(second alist))<)(merge-all-neighbors (rest (rest alist)))))))

 

 

另..

how to design programs中文版下载地址

ftp://ftp.cs.sjtu.edu.cn:990/huanglp/程序设计方法/如何设计程序.PDF

Moyaiun 说:
2013年11月17日 05:02

filter最后一行,(pred (cdr list))是否为(filter (cdr list))


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter