自定义QSort函数， 欢迎前来踢馆！

XDSoft

crazylsp 发表于 2013-6-6 22:00
确实是这样。整数的重复排序我已做成，不过感觉对画图确实没什么用途好的，我选试下大师 ...

其实，做个实数的排序就够了，排整数的时候，可以先FLOAT他们，排序完在FIX。

ayl1004

这应该是vl-sort函数的优点

sicky111

一篇好帖总是可以聚集很多人气，来晚了，学习。

redcat2012

表排序极度理解(详见6#代码)

pengfei2010

晓东大师说的太对了可以先FLOAT他们，排序完在FIX

高山流水

       在Theswamp已经对比过了，高飞老师的这2个排序函数确实非常快。
       谈点个人对VL-SORT函数丢失相同整数的看法——
       计算机处理器做处理时，数据格式必须是一致的，整数和实数（浮点数）在CPU为不同的数据格式，但都是以二进制表示的；两数值相等的浮点数，在计算机中模拟只能是模糊相等不是绝对相等，而两个数值相同的整型数是绝对相等的；正式因为这个绝对相当，导致 vl-sort在排序时第二个相同的整数找不到位置而丢失（从这点来看，vl-sort 的算法应该冒泡排序法，这也是VL-SORT在追求效率时落下的一个BUG）；而 vl-sort-i 的好处在于它只是排位置，位置值是唯一的，所以不会丢失数据。

2. 
   
3. (defun mergesort (lst / merge brklst)
   
4.   ;; by Gile
   
5.   (defun merge (l1 l2)
   
6.     (cond
   
7.       ((null l1) l2)
   
8.       ((null l2) l1)
   
9.       ((if (< (car l1) (car l2))
   
10.   (cons (car l1) (merge (cdr l1) l2))
    
11.   (cons (car l2) (merge l1 (cdr l2)))
    
12.        )
    
13.       )
    
14.     )
    
15.   )
    
16.   (defun brklst (lst acc n)
    
17.     (if (= 0 n)
    
18.       (list acc lst)
    
19.       (brklst (cdr lst) (cons (car lst) acc) (1- n))
    
20.     )
    
21.   )
    
22.   (if (cdr lst)
    
23.     (progn
    
24.       (setq lst (brklst lst nil (/ (length lst) 2)))
    
25.       (merge (mergesort (car lst))
    
26.       (mergesort (cadr lst))
    
27.       )
    
28.     )
    
29.     lst
    
30.   )
    
31. )
    

<br /> (defun mergesort (lst / merge brklst)<br />   ;; by Gile<br />   (defun merge (l1 l2)<br />     (cond<br />       ((null l1) l2)<br />       ((null l2) l1)<br />       ((if (< (car l1) (car l2))<br />   (cons (car l1) (merge (cdr l1) l2))<br />   (cons (car l2) (merge l1 (cdr l2)))<br />        )<br />       )<br />     )<br />   )<br />   (defun brklst (lst acc n)<br />     (if (= 0 n)<br />       (list acc lst)<br />       (brklst (cdr lst) (cons (car lst) acc) (1- n))<br />     )<br />   )<br />   (if (cdr lst)<br />     (progn<br />       (setq lst (brklst lst nil (/ (length lst) 2)))<br />       (merge (mergesort (car lst))<br />       (mergesort (cadr lst))<br />       )<br />     )<br />     lst<br />   )<br /> )<br />

      

st788796

高山流水 发表于 2014-10-17 23:47
在Theswamp已经对比过了，高飞老师的这2个排序函数确实非常快。
       谈点个人对VL-SORT函数丢失 ...

在 Autocad 平台下，AutoLisp 仅仅是 Autodesk 用 ARX 扩展的一个工具，car 也好，cons 也好，都要转换到 ARX 内部处理，vl-sort 将更多步骤包装到了内部，效率自然比你用一堆他提供的基本函数组合要高

高山流水

st788796 发表于 2014-10-18 09:02
在 Autocad 平台下，AutoLisp 仅仅是 Autodesk 用 ARX 扩展的一个工具，car 也好，cons 也好，都要转换到 ...

      我不赞成您的观点，AutoLisp（AutoCAD于1986年v2.18版时提供了AutoLISP程序设计的支持http://www.cnki.com.cn/Article/CJFDTotal-YHJS199728014.htm）是嵌入AutoCAD内部的早期交互语言（这也是ALISP一直很稳定的原因），是基于Lisp发展而来的（Lisp的函数格式稍微修改下个别函数名就可以拿到ALISP使用）；也就是说它的语言基础时LISP语言，而非后来的ObjectARX语言（AutoCAD2002以后才有的，基于MSVC++的）；而VisualLisp是AutoLisp的改进。ObjectARX可以很好和VLISP进行交互，函数容易被VLISP调用，这是因为AutoCAD为了语言升级过渡专门做了内部数据交互组件的。基于前述内容，个人认为VL-SORT是基于LISP语言的。.
      LISP 提供两种主要排序：排序Sort和稳定排序Stable-sort；http://wenku.baidu.com/view/5eaf3c2c3169a4517723a3f2.html
     “sort的第一个参数是一个列表，第二个是一个比较函数。sort函数不保证稳定性：如果这里有a和b两个元素，(and (not (< a b)) (not (< b a)))，sort可能会改变它们的位置。stable-sort（稳定排序）与sort非常像，不过它确保两个相等的元素在排序后的列表中的顺序与排序前列表中的顺序相同。注意：sort可能会破坏它的参数，如果原始序列对我们很重要，最好使用 copy-list或copy-seq 函数创建一个副本。”
     或许VL-SORT的这个BUG是从LISP的SORT一直遗留下来。     

st788796

高山流水 发表于 2014-10-18 14:13
我不赞成您的观点，AutoLisp（AutoCAD于1986年v2.18版时提供了AutoLISP程序设计的支持http://www.c ...

您这扯远了，以前也曾经追本溯源搜索一些Lisp的历史、介绍，包括下载过一个CLisp，试图更好的理解学习Autolisp，然后又知道了桌子的 ADS ObjectARX ，都是工具，Lisp基础7个函数，然后去变幻，桌子也仿效弄出这么个"AutoLisp"让我等乐此不疲的跟着玩，其实，在AutoCAD屋檐下，A/Vlisp不算啥，换个方式你的开发会变的更强大和如此简单
目前流行的很多语言或多或少都在借鉴Lisp概念，而且人工智能领域Lisp也是主力(此Lisp非A/Vlisp)

XDSoft

高山流水 发表于 2014-10-17 23:47
在Theswamp已经对比过了，高飞老师的这2个排序函数确实非常快。
       谈点个人对VL-SORT函数丢失 ...

VL-SORT的排序肯定不会是冒泡，快速排序对C++而言都是很容易实现的。

st788796

http://www.ibm.com/developerworks/cn/java/j-cb02067.html




http://www.cnblogs.com/weidagang ... 03/tao_of_lisp.html




http://blog.jobbole.com/30614/




http://daiyuwen.freeshell.org/gb/rol/roots_of_lisp.html




http://www.360doc.com/content/13/1101/13/6828497_325824721.shtml

高山流水

XDSoft 发表于 2014-10-18 17:25
VL-SORT的排序肯定不会是冒泡，快速排序对C++而言都是很容易实现的。

感谢晓东老师指导，那是否是延续了LISP中的Sort函数，整型数比较引起的整数的丢失呢。

高山流水

st788796 发表于 2014-10-18 17:59
http://www.ibm.com/developerworks/cn/java/j-cb02067.html

http://www.cnblogs.com/weidagang2046/arc ...

感谢st长老提供这么多的链接，我得好好学习下了

aimisiyou

对于有重复的数，H:QSORT1会出现硬错误，H:QSORT2却不会出现硬错误。

Highflybird

aimisiyou 发表于 2016-12-12 12:53

很好的踢馆。
仔细检查了一下，发现qsort1有bug,修改了一下：
代码如下:
[pcode=lisp,true]
;;;=============================================================
;;;Highflybird's  快速排序算法1                                 
;;;考虑如下情况：如果已经是一个排序好的表                       
;;;如果是一个随机表，则算法稍微慢于QSORT2                     
;;;但对于一个已排序好的标，则算法要快于QSORT2                 
;;;=============================================================
(defun H:QSort1 (s / a k L R)
  (if (cddr s)
    (progn
      (setq k (* (+ (car s) (last s)) 0.5))                        ;考虑最坏的情况，取其平均值为关键数
      (while s
        (if (< (setq a (car S)) k)                              ;每个数与关键数比较
          (setq L (cons a L))                                        ;小于它的放到左边
          (Setq R (cons a R))                                   ;大于或等于它的放到右边
        )
        (setq S (cdr S))                                       
      )
      (if L
        (append (H:QSort1 L) (H:QSort1 R))
        (cons (car R) (H:QSort1 (CDR R)))                        ;左边为空,则递归右边(为何没有右边为空的情况？请思考.)
      )
    )
    (if (and (cdr s) (> (car s) (cadr s)))                        ;只有两个数的情况
      (reverse s)
      s
    )
  )
)
[/pcode]