我知道quicksort的O(n log n)平均时间复杂度.伪快速排序(当你从足够远的地方看它,具有适当高的抽象级别时只是一个快速排序),通常用于演示函数语言的简洁性如下(在Haskell中给出):
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]
好的,所以我知道这件事有问题.最大的问题是它没有排序,这通常是quicksort的一大优势.即使这没关系,它仍然需要比典型的快速排序更长的时间,因为它在分区时必须进行两次列表传递,然后它会进行昂贵的附加操作以将其拼接回来.此外,选择第一个元素作为枢轴不是最佳选择.
但即便考虑所有这些,这个快速排序的平均时间复杂度与标准快速排序不同吗？即,O(n log n)？因为追加和分区仍然具有线性时间复杂度,即使它们效率低下.
我正在尝试使用LISP进行快速排序,但我的功能输出有问题.
(defun qsort (L)
(cond
((null L) nil)
(t(append
(qsort (list< (car L) (cdr L)))
(cons (car L) nil)
(qsort (list>= (car L) (cdr L)))))))
(defun list< (a b)
(cond
(( or(null a)(null b) nil))
(( < a (car b)) (list< a (cdr b)))
(t(cons (car b) (list< a (cdr b))))))
(defun list>= (a b)
(cond
(( or( null a)(null b) nil))
(( >= a (car b)) (list> a (cdr b)))
(t(cons (car b) (list> a (cdr b))))))
我的问题是当list …