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

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

快速排序:

快速排序是分而治之思想的体现,即将非平凡可解的问题分成相关的两个小问题.分别解决这两个小问题.再将所得结果合并起来.

具体来说.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