AutoLisp基于X坐标的坐标列表快速排序陷入无限循环问题排查求助

嘿，我看到你在用快速排序给坐标列表按X轴升序排序时陷入了无限循环，帮你梳理下代码里的几个关键问题，这些就是导致循环停不下来的核心原因：

1. qd:swap 函数完全没生效 #

AutoLisp是值传递的，你当前的swap函数只是交换了局部变量g和h的值，根本没碰原列表里的元素！这就导致分区操作时，元素位置完全没变化，每次递归的分区结果都一样，自然会无限循环下去。

你需要改成直接通过索引修改列表元素的方式，因为AutoLisp的列表是不可变的，修改后会生成新列表，所以swap要返回修改后的列表：

;; 先实现一个修改列表指定索引元素的工具函数
(defun setnth (idx val lst)
  (if (= idx 0)
    (cons val (cdr lst))
    (cons (car lst) (setnth (1- idx) val (cdr lst)))
  )
)

;; 修正后的swap函数，接收列表和两个索引，返回交换后的新列表
(defun qd:swap (sp idx1 idx2)
  (setq temp (nth idx1 sp))
  (setq sp (setnth idx1 (nth idx2) sp))
  (setq sp (setnth idx2 temp sp))
  sp
)

2. qd:partition 循环条件错误 #

你写的循环条件是 (< j (- (length sp) 2))，这是个固定值，完全没考虑当前分区的high参数！正确的循环范围应该是从low到high-1，也就是改成 (< j high)，否则会漏掉分区内的部分元素，导致分区逻辑失效，递归无法收敛。

另外，i的初始值应该设为(1- low)而不是-1，因为low不一定是0，这样才能正确跟踪小于等于pivot的元素位置。修正后的partition函数：

(defun qd:partition (sp low high / pivot i j temp)
  (cond
    ((null sp) nil)
    (t
      (setq pivot (car (nth high sp)))
      (setq i (1- low))
      (setq j low)
      (while (< j high)
        (if (<= (car (nth j sp)) pivot)
          (progn
            (setq i (1+ i))
            (setq sp (qd:swap sp i j))
          )
        )
        (setq j (1+ j))
      )
      (setq sp (qd:swap sp (1+ i) high))
    )
  )
  (list sp (1+ i)) ; 返回修改后的列表和分区点索引
)

3. 递归时未传递修改后的列表 #

你的qd:quicksort_x函数没有返回值，也没有把partition修改后的列表传递给下一层递归，导致每次递归操作的都是原列表，分区永远没变化，自然无限循环。修正后的排序函数要接收并返回每次分区后的新列表：

(defun qd:quicksort_x (sp low high / part new-sp part-idx)
  (if (< low high)
    (progn
      (setq part (qd:partition sp low high))
      (setq new-sp (car part))
      (setq part-idx (cadr part))
      ;; 递归处理左右分区，传递更新后的列表
      (setq new-sp (qd:quicksort_x new-sp low (1- part-idx)))
      (setq new-sp (qd:quicksort_x new-sp (1+ part-idx) high))
      new-sp
    )
    sp ; 基线情况：分区只有一个元素，直接返回
  )
)

最后修正调用方式 #

现在排序函数会返回排序后的列表，调用时要接收这个返回值：

;; 你的坐标列表
(setq sp '((112040.0 -34649.7 0.0)
           (112004.0 -34641.7 0.0)
           (112134.0 -34649.7 0.0)
           (112098.0 -34641.7 0.0)
           (112000.0 -34773.7 0.0)
           (112000.0 -34881.7 0.0)
           (111946.0 -34801.7 0.0)))
(setq low 0)
(setq high (- (length sp) 1))
;; 输出排序结果
(princ (qd:quicksort_x sp low high))

把这些修改后，你的快速排序应该就能正常运行，按X坐标升序排列你的坐标列表了。

备注：内容来源于stack exchange，提问作者Gayathri