研讨下这个函数 qsort

st788796

搜到一个这样的函数，哪个大侠给讲解下[pcode=lisp,true](defun qsort (lst cmp / x y l e g)
  (if lst
    (progn
      (setq x (nth (/ (length lst) 2) lst))
      (foreach y lst
        (cond
          ((equal y x)
           (setq e (cons y e))
          )
          ((apply cmp (list y x))
           (setq l (cons y l))
          )
          (T (setq g (cons y g)))
        )
      )
      (append (qsort l cmp) e (qsort g cmp))
    )
  )
)[/pcode]

Lispboy

没仔细看呢，从函数名字看，应该是快速排序算法，时间效率上应该是n级的，仔细看下在说。

Lispboy

从  (setq x (nth (/ (length lst) 2) lst))  这句看，应该是把表分两半，两边往中间去，应该是快速排序算法。

Lispboy

找点资料来贴上：

1. 
   
2. 快速排序(QuickSort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。
   
3. 快速排序被认为是当前最优秀的内部排序方法。
   

复制代码

1. 
   
2. 快速排序的基本思想是基于分治策略的。对于输入的子序列L【p..r】，如果规模足够小则直接进行排序（比如用前述的冒泡、选择、插入排序均可），否则分三步处理：
   
3. 
   
4. 分解(Divide)：将待排序列L【p..r】划分为两个非空子序列L【p..q】和L【q 1..r】，使L【p..q】中任一元素的值不大于L【q 1..r】中任一元素的值。具体可通过这样的途径实现：在序列L【p..r】中选择数据元素L【q】，经比较和移动后，L【q】将处于L【p..r】中间的适当位置，使得数据元素L【q】的值小于L【q 1..r】中任一元素的值。
   
5. 
   
6. 递归求解(Conquer)：通过递归调用快速排序算法，分别对L【p..q】和L【q 1..r】进行排序。
   
7. 
   
8. 合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L【p..q】和L【q 1..r】都排好序后不需要执行任何计算L【p..r】就已排好序，即自然合并。
   
9. 
   
10. 这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。
    

复制代码

1. 
   
2. 快速排序法是对冒泡排序法的一种改进，也是基于交换排序的一种算法。因此，被称为"分区交换排序"。
   
3.   在待排序序列中按某种方法选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成"{左子序列}K{右子序列}"。再分别对左、右两部分实施上述分解过程，直到各子序列长度为1，即有序为止。
   
4.   分界点元素值K的选取方法不同，将构成不同的排序法，也将影响排序的效率：例如，可取左边第1个元素为分界点、取中点A【（left right）/2】为分界点、或选取最大和最小值的平均值为分界点等。
   

复制代码

楼主提供的函数应该是 符合

1. 
   
2. 取中点A【（left right）/2】为分界点、或选取最大和最小值的平均值为分界点等
   

复制代码

应该是快速排序算法。

快速排序算法最坏情况下是n^2，平均时间复杂度是 n(logn).

ScmTools

此函数的关键是这句(append (qsort l cmp) e (qsort g cmp))递归的用法，你明白了，就明白了此函数的原意

cre8or

好东西 好的不是源码 是解释

dnbcgrass

不知道lst数据量大时，递归会不会溢出？