scheme 合并排序

示例

合并排序是一种常见的排序算法,平均情况复杂度为O(n log n),最坏情况复杂度为O(n log n)。尽管它不能就地执行,但它保证O(n log n)了所有情况下的复杂性。

合并排序重复将输入分成两部分,直到到达空列表或单元素列表。到达拆分树的底部之后,它会往回备份,将两个已排序的拆分合并到一起,直到剩下一个已排序的列表。

使用此方法,合并排序的Scheme实现可能如下所示:

;; Merge two sorted lists into a single sorted list

(define (merge list1 list2)

  (cond

    ((null? list1)

     list2)

    ((null? list2)

     list1)

    (else

      (let ((head1 (car list1))

            (head2 (car list2)))

        ; Add the smaller element to the front of the merge list

        (if (<= head1 head2)

          (cons

            head1

            ; Recursively merge

            (merge (cdr list1) list2))

          (cons

            head2

            ; Recursively merge

            (merge list1 (cdr list2))))))))

(define (split-list lst)

  (let ((half (quotient (length lst) 2)))

    ; Create a pair of the first and second halves of the list

    (cons

      (take lst half)

      (drop lst half))))

(define (merge-sort lst)

  (cond

    ((or (null? lst) ; empty list is sorted, so merge up

         (null? (cdr lst))) ; single-element list is sorted, so merge up

     lst)

    (else

      (let ((halves (split-list lst)))

        ; Recursively split until the bottom, then merge back up to sort

        (merge (merge-sort (car halves))

               (merge-sort (cdr halves)))))))

           

以上是 scheme 合并排序 的全部内容, 来源链接: utcz.com/z/330668.html

回到顶部