1 В избранное 0 Ответвления 0

OSCHINA-MIRROR/perry96-SICP

Присоединиться к Gitlife
Откройте для себя и примите участие в публичных проектах с открытым исходным кодом с участием более 10 миллионов разработчиков. Приватные репозитории также полностью бесплатны :)
Присоединиться бесплатно
Клонировать/Скачать
merge-sort.md 1.3 КБ
Копировать Редактировать Web IDE Исходные данные Просмотреть построчно История
Perry961002 Отправлено 30.01.2019 17:40 95aaf6a

归并排序算法

算法核心思想

  • 合并两个列表L1、L2
    • 如果L1L2中有一个为空,则返回另一个.
    • 否则分别取L1L2的首元素x1x2
      • 如果x1小于等于x2,则将x1作为新列表的首元素,并继续合并L1的剩余部分和L2.
      • 如果x1大于x2,则将x2作为新列表的首元素,并继续合并L1L2的剩余部分.
(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))))))))
  • 归并排序
    • 每次选取列表的头两个元素进行合并然后舍弃,并将合并之后元素放置列表末尾,继续对新列表进行归并排序,直到列表中只有一个元素.

(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)))))))

Опубликовать ( 0 )

Вы можете оставить комментарий после Вход в систему

1
https://api.gitlife.ru/oschina-mirror/perry96-SICP.git
git@api.gitlife.ru:oschina-mirror/perry96-SICP.git
oschina-mirror
perry96-SICP
perry96-SICP
master