我仍然是正确的Lisp的新手,我正在尝试构建一个简单但至少有效的插入排序 - 我想切换元素到位,但仍然有能力随后附加到我的容器。我采用了旧的C ++实现:
template<typename Iter>
void insertionSort(Iter begin, Iter end){
for (auto i = begin; i != end; ++i){
for (auto j = i; j != begin && *(std::prev(j)) > *(j); j--){
std::iter_swap(j, std::prev(j));
}
}
}
并创建了以下代码(考虑到aref
和rotatef
具有公平的复杂性),但它似乎没有对输入产生任何影响(UPD:现在它只是不正确地工作),我的解决方案可能有什么问题?我正在返回测试目的,我应该创建一个宏来避免传值吗?
(defparameter testa (make-array 4 :initial-contents '(2 3 1 5)))
(defun insertion-sort (vect)
(loop for i from 0 to (1- (length vect)) do
(loop for j from i downto 0
until (or (= (1- j) -1) (> (aref vect (1- j)) (aref vect j)))
do (rotatef (aref vect i) (aref vect (1- j))))
)
vect
)
(format t "~a~%" (insertion-sort testa))
UPD:根据@jkiiski和@RainerJoswig的评论更新了代码,输出仍然是错误的。
在你的程序中有几个问题。
首先,排序不起作用,因为该行:
do (rotatef (aref vect i) (aref vect (1- j))))
应该:
do (rotatef (aref vect j) (aref vect (1- j))))
也就是说,你已经写了变量i
而不是j
如果进行此更正,您会发现订单正在减少(我假设您需要增加订单)。这取决于使用until
而不是while
。
最后,还有冗余代码。更简单有效的版本如下:
(defparameter testa (make-array 4 :initial-contents '(2 3 1 5)))
(defun insertion-sort (vect)
(loop for i from 1 below (length vect)
do (loop for j from i above 0
while (> (aref vect (1- j)) (aref vect j))
do (rotatef (aref vect j) (aref vect (1- j)))))
vect)
(format t "~a~%" (insertion-sort testa))
这与Insertion sort
的维基百科页面中的伪代码并行。
如果要参数化排序谓词,以及向函数添加可选的基于关键字的“key”参数,可以使用以下解决方案:
(defun insertion-sort (vect predicate &key (key #'identity))
(loop for i from 1 below (length vect)
do (loop for j from i above 0
while (funcall predicate
(funcall key (aref vect (1- j)))
(funcall key (aref vect j)))
do (rotatef (aref vect j) (aref vect (1- j)))))
vect)
CL-USER> (insertion-sort testa #'>)
#(1 2 3 5)
CL-USER> (insertion-sort testa #'<)
#(5 3 2 1)
CL-USER> (defparameter testa (make-array 4 :initial-contents '((c 3) (d 2) (b 1) (a 4))))
TESTA
CL-USER> (insertion-sort testa #'string> :key #'car)
#((A 4) (B 1) (C 3) (D 2))