SICP的小练习--Scheme语言实现3个经典的排序算法

一、说明

从去年11月份开始了《计算机程序的构造和解释》这本书的学习,开始接触了函数式。学习过程中也对编程有了新的理解,对递归这一程序设计技术也有了更深的掌握。其间为了自娱自乐用Scheme这一小众的函数式语言实现了3个经典排序算法,分别是快速排序、归并排序、堆排序。

  • 目前我已经学习并完成了那本书的前三章的内容和习题,所有的代码也放在了GitHub仓库里,如果有对那本书感兴趣的朋友,可以一起讨论学习。

二、具体算法实现

1.快速排序

1.1.算法核心思想

  • 每次选取第一个元素作为基准,并采用过滤器filter将剩余元素中小于等于基准的作为small部分、剩余元素中大于基准的作为big部分,然后对smallbig部分进行快速排序,最后按small-基准-big的顺序组合成新的列表,直到列表中只有一个元素为止.

1.2.完整代码实现

1
2
3
4
5
6
7
8
(define (quicksort L)
(if (null? L)
'()
(let ((small (quicksort (filter (lambda (x) (<= x (car L)))
(cdr L))))
(big (quicksort (filter (lambda (x) (> x (car L)))
(cdr L)))))
(append small (cons (car L) big)))))

2.归并排序

2.1.算法核心思想

  • 合并两个列表L1、L2
    • 如果L1L2中有一个为空,则返回另一个.
    • 否则分别取L1L2的首元素x1x2
      • 如果x1小于等于x2,则将x1作为新列表的首元素,并继续合并L1的剩余部分和L2.
      • 如果x1大于x2,则将x2作为新列表的首元素,并继续合并L1L2的剩余部分.
1
2
3
4
5
6
7
8
(define (merge L1 L2)
(cond ((null? L1) L2)
((null? L2) L1)
(else
(let ((x1 (car L1)) (x2 (car L2)))
(if (<= x1 x2)
(cons x1 (merge (cdr L1) L2))
(cons x2 (merge L1 (cdr L2))))))))
  • 归并排序
    • 每次选取列表的头两个元素进行合并然后舍弃,并将合并之后元素放置列表末尾,继续对新列表进行归并排序,直到列表中只有一个元素.

1
2
3
4
5
6
7
8
9
10
11
12
(define (merge-sort L)
(define (transform x)
(if (number? x)
(list x)
x))
(cond ((null? L) '())
((= (length L) 1) (car L))
(else
(let ((l1 (transform (car L)))
(l2 (transform (cadr L))))
(let ((new (list (merge l1 l2))))
(merge-sort (append (cddr L) new)))))))

2.2.完整代码实现

3.堆排序

3.1.算法核心思想

  • 首先将数组映射为一棵完全二叉树

    规则:对于 i 下标位置的元素,它的左孩子下标为 2*i+1右孩子下标为 2*(i+1)​.

  • 维护一个以root下标为根,末尾下标为len的大根堆

    如果root的两个孩子有比它大的,则将root和那个最大元素交换位置,并对那个子树进行递归维护.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(define (MaxHeapify heap root len)
(define (Left i) (+ (* i 2) 1))
(define (Right i) (* (+ i 1) 2))
(let ((left (Left root))
(right (Right root))
(largest root))
(begin
(if (and (<= left len)
(> (vector-ref heap left)
(vector-ref heap root)))
(set! largest left))
(if (and (<= right len)
(> (vector-ref heap right)
(vector-ref heap largest)))
(set! largest right))
(if (not (= largest root))
(let ((head (vector-ref heap root)))
(begin
(vector-set! heap root (vector-ref heap largest))
(vector-set! heap largest head)
(MaxHeapify heap largest len)))))))
  • 初始化大根堆

    从堆中的最后一个有孩子的节点开始从右向左从下向上,以每个节点为根维护一个大根堆.

1
2
3
4
5
6
7
(define (BuildMaxHeap heap)
(define (build-iter i)
(if (>= i 0)
(begin
(MaxHeapify heap i (- (vector-length heap) 1))
(build-iter (- i 1)))))
(build-iter (- (div (vector-length heap) 2) 1)))
  • 堆排序

    从初始的大根堆开始,每次将0下标位置和len下标位置的元素交换,并len := len-1,然后继续对0到len位置的元素进行堆排序,直到len = 0.

1
2
3
4
5
6
7
8
9
10
11
12
(define (HeapSort heap)
(define (sort-iter i)
(if (>= i 1)
(let ((max (vector-ref heap 0)))
(begin
(vector-set! heap 0 (vector-ref heap i))
(vector-set! heap i max)
(MaxHeapify heap 0 (- i 1))
(sort-iter (- i 1))))))
(BuildMaxHeap heap)
(sort-iter (- (vector-length heap) 1))
heap)

3.2.完整代码实现

------------- 本文结束 感谢您的阅读 -------------

本文标题:SICP的小练习--Scheme语言实现3个经典的排序算法

文章作者:Perry

发布时间:2019年02月25日 - 16:09

最后更新:2019年09月19日 - 13:48

原始链接:https://perry96.com/archives/be062c72.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%