方案中的气泡排序

Question

我正在编写一个递归代码到Bubble排序(通过交换最小到最大)

我只有一次做气泡排序的代码

(define (bubble-up L)  
   (if (null? (cdr L))  
     L   
  (if (< (car L) (cadr L))  
(cons (car L) (bubble-up (cdr L)))  
(cons (cadr L) (bubble-up (cons (car L) (cddr L))))  
  )
 )  

如果我将一个列表放入这段代码中，它将返回末尾最大的列表。

前..。(泡沫塑料‘(8 9 4 2 6 7)) ->’(8 4 2 6 7)

现在，我正试图编写一个代码来执行(冒泡L) N次(列表中的整数数)。

我有这样的代码：

  (define (bubble-sort-aux N L)   
    (cond ((= N 1) (bubble-up L))  
       (else (bubble-sort-aux (- N 1) L)  
  (bubble-up L))))  
(bubble-sort-aux 6 (list 8 9 4 2 6 7))  -> ' (8 4 2 6 7 9)

但是递归似乎没有发生，因为它只排序一次！

任何建议都欢迎，我只是有点困惑！

Answer 1

试试这个：

(define (bubble-sort-aux N L)   
  (cond ((= N 1) (bubble-up L))  
        (else (bubble-sort-aux (- N 1) (bubble-up L)))))  

如果您保持“冒泡”列表的N次数，它将在最后排序。代码的问题是，您没有将bubble-up的结果用于任何东西--但是如果我们将bubble-up返回的值传递给函数的下一个调用，它最终将被排序。现在，该程序如预期的那样工作：

(bubble-sort-aux 6 (list 8 9 4 2 6 7))
=> '(2 4 6 7 8 9)

Answer 2

我的实施：

(define (bubble-swap ls)
  (if (null? (cdr ls))
      ls
      (if (> (car ls) (cadr ls))
          (cons (cadr ls) (bubble-swap (cons (car ls) (cddr ls))))
          (cons (car ls) (bubble-swap (cdr ls))))))

(define (len ls)
  (if (null? ls)
      0
      (+ 1 (len (cdr ls)))))

(define (bubblesort_ ls n)
  (if (= n 1)
      ls
      (bubblesort_ (bubble-swap ls) (- n 1))))

(define (bubblesort ls) (bubblesort_ ls (len ls)))

我实现了一个定制的len函数，但如果可用的话，您可以使用标准的length函数。