泡泡方案

排序

我寫一個遞歸碼冒泡排序（從小到大通過交換）
我有一個代碼做冒泡排序只是一次泡泡方案

(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 9）

現在我是代碼，它返回最後一個號碼列表
EX試圖寫一個代碼來做（泡泡L）N次（列表中的整數數量）
我有這個公司de：

(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)

但是遞歸似乎沒有發生，因爲它只排序一次！
任何建議將受到歡迎，我只是難住！

來源

2013-10-09 Avery Poole

「我正在寫一個遞歸代碼到Bubble Sort」 - 不要！ –

@MitchWheat AveryPoole在Scheme中編寫，其中tail-call優化是由規範強制的。迭代通常是通過Scheme中的尾遞歸實現的。 Recation _is_是在Scheme中實現這一點的自然事物。 –

有沒有其他方法？剛開始編寫代碼，尾遞歸是我學到的唯一方法。 @MitchWheat –

試試這個：

(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)

來源

2013-10-09 00:29:16

謝謝一噸奧斯卡！我認爲我有點被燒燬，那是一個很大的錯誤=/ –

@AveryPoole歡迎你！總是我的快樂:) –

我的實現：

(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功能。

來源

2017-02-27 10:00:54 fabior

回答

相關問題