Scheme快排

#lang racket
(define (quicksort l)
  (define (divide l base)
    (if (null? l) '( () () () )
        (let ([first (car l)]
              [remain (divide (cdr l) base)])
          (cond
            [(< first base)
             (cons (cons first (car remain)) (cdr remain))]
            [(> first base) (list (car remain) (second remain) (cons first (last remain)))] ;用了second/last之类的racket only语法,换成cdar/cddar也行吧
            [(= first base) (list (car remain) (cons first (second remain)) (last remain))]
            )
          )
        )
    )
  (if (<= (length l) 1)
      l
      (let ([divided-list (divide l (car l))])
        (append (quicksort (car divided-list)) (second divided-list) (quicksort (last divided-list)))
        )
      )
  )

(define (gen-rand-list n)
  (if (= n 0) '()
      (cons (random 1000000) (gen-rand-list (- n 1)))
      )
  )

(define g (gen-rand-list 200000))

(time (length (quicksort g)))  ;解释执行1700ms左右,证明是快排。编译:cpu time: 656 real time: 657 gc time: 278

发表评论