newlisp实现quick sort

实现的时候要注意，如果将一个list传给函数，在函数内部修改后，不会改变函数外的list。

因此采用了变通的方法，将list作为全局变量，函数递归时不传递list为参数。

实现代码如下：

sort.lsp文件

(setq values '())

(define (quick-sort start end)
  (if (>= start end)
      (begin
;;	(println "return")
	)
      (begin
	(letn (first-idx start
			 last-idx end
			 key (values first-idx)
			 )
	  (while (< first-idx last-idx)
	    (while (and (< first-idx last-idx) (>= (values last-idx) key))
	      (-- last-idx)
	      )
	    (swap (values first-idx) (values last-idx))
	    (while (and (< first-idx last-idx) (<= (values first-idx) key))
	      (++ first-idx)
	      )
	    (swap (values first-idx) (values last-idx))
	    )
	  (quick-sort start (- first-idx 1))
	  (quick-sort (+ first-idx 1) end)
	  )
	)
      )
  )

调用代码

#!/usr/bin/newlisp

(load "sort.lsp")

(setq values '(5 6 7 9 3 7 8 1 18 26 34 -9))
(println values)
(quick-sort 0 (- (length values) 1))
(println values)

(exit)

运行结果：

[dean@dell_xps_13 detector]$ ./test.lsp 
(5 6 7 9 3 7 8 1 18 26 34 -9)
(-9 1 3 5 6 7 7 8 9 18 26 34)