找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3150|回复: 6

[求助] 研讨下这个函数 qsort

[复制链接]

已领礼包: 1268个

财富等级: 财源广进

发表于 2013-5-8 17:21:21 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

×
搜到一个这样的函数,哪个大侠给讲解下[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]
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

已领礼包: 51个

财富等级: 招财进宝

发表于 2013-5-8 17:25:48 | 显示全部楼层
没仔细看呢,从函数名字看,应该是快速排序算法,时间效率上应该是n级的,仔细看下在说。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 51个

财富等级: 招财进宝

发表于 2013-5-8 17:29:13 | 显示全部楼层
从  (setq x (nth (/ (length lst) 2) lst))  这句看,应该是把表分两半,两边往中间去,应该是快速排序算法。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 51个

财富等级: 招财进宝

发表于 2013-5-8 17:33:16 | 显示全部楼层
本帖最后由 Lispboy 于 2013-5-8 17:35 编辑

找点资料来贴上:

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

  1. 快速排序的基本思想是基于分治策略的。对于输入的子序列L【p..r】,如果规模足够小则直接进行排序(比如用前述的冒泡、选择、插入排序均可),否则分三步处理:

  2. 分解(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】中任一元素的值。

  3. 递归求解(Conquer):通过递归调用快速排序算法,分别对L【p..q】和L【q 1..r】进行排序。

  4. 合并(Merge):由于对分解出的两个子序列的排序是就地进行的,所以在L【p..q】和L【q 1..r】都排好序后不需要执行任何计算L【p..r】就已排好序,即自然合并。

  5. 这个解决流程是符合分治法的基本步骤的。因此,快速排序法是分治法的经典应用实例之一。
复制代码

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

  1. 取中点A【(left right)/2】为分界点、或选取最大和最小值的平均值为分界点等
复制代码
应该是快速排序算法。

快速排序算法最坏情况下是n^2,平均时间复杂度是 n(logn).
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1632个

财富等级: 堆金积玉

发表于 2013-5-8 20:45:54 | 显示全部楼层
此函数的关键是这句(append (qsort l cmp) e (qsort g cmp))递归的用法,你明白了,就明白了此函数的原意
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2013-6-9 11:09:01 | 显示全部楼层
好东西 好的不是源码 是解释
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 3702个

财富等级: 富可敌国

发表于 2013-6-9 18:26:32 | 显示全部楼层
不知道lst数据量大时,递归会不会溢出?
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )

GMT+8, 2024-3-29 21:08 , Processed in 0.312518 second(s), 44 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表