气泡排序与计划

我正在努力在Scheme中实现气泡排序算法，我必须说，编程的功能方式是一个奇怪的概念，我正在努力一点点来掌握它。气泡排序与计划

我已经成功地创建了一个函数，它会冒出我们遇到的第一大值，但这就是它所做的一切。

(bubbleH '(5 10 9 8 7)) 
(5 9 8 7 10)

我正在努力完成循环遍历列表所需的帮助程序功能，直到没有交换为止。

这是我到目前为止的地方，显然这是不正确的，但我认为我走在正确的轨道上。我知道我可以自己传递列表中的元素数量，但我正在寻找一种与此不同的解决方案。

(define bubbaS 
    (lambda (lst) 
    (cond ((= (length lst) 1) (bubba-help lst)) 
     (else (bubbaS (bubba-help lst))))))

来源

2014-02-17 Talen Kylon

分享到目前为止已经实施的内容，并呼吁您试图进一步塑造它。 – J0e3gan

[Bubble Sorting in Scheme]可能的重复（http://stackoverflow.com/questions/19260784/bubble-sorting-in-scheme） – J0e3gan

我的问题与你所链接的不同，我不想通过元素的数量作为参数。我想我应该加入！ –

在possible-duplicate SO question我使用bubble-up和bubble-sort-aux实现参考...

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

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

...，这是简单的语法糖：

(define (bubbleH L) 
    (bubble-sort-aux (length L) L))

随着语法糖添加，你应该让你在你的问题中指定正是最后一位：

(bubbleH '(5 10 9 8 7)) 
=> (5 7 8 9 10)

你可以用上面的东西修补一下repl.it session我保存了&共享。

来源

2014-02-18 00:16:53 J0e3gan

这是我自己的尾递归版本。

内部函数会像您的bubbleH程序一样冒出最大数量。但是，而不是返回一个完整列表，它会返回2个值：

未排序的休息名单
已经冒泡

如最大值：

> (bsort-inner '(5 1 4 2 8)) 
'(5 2 4 1) 
8 
> (bsort-inner '(1 5 4 2 8)) 
'(5 2 4 1) 
8 
> (bsort-inner '(4 8 2 5)) 
'(5 2 4) 
8

现在外循环只需要cons返回的第二个值，并在剩余列表上进行迭代。

代码：

(define (bsort-inner lst) 
    (let loop ((lst lst) (res null)) 
    (let ((ca1 (car lst)) (cd1 (cdr lst))) 
     (if (null? cd1) 
      (values res ca1) 
      (let ((ca2 (car cd1)) (cd2 (cdr cd1))) 
      (if (<= ca1 ca2) 
       (loop cd1 (cons ca1 res)) 
       (loop (cons ca1 cd2) (cons ca2 res)))))))) 

(define (bsort lst) 
    (let loop ((lst lst) (res null)) 
    (if (null? lst) 
     res 
     (let-values (((ls mx) (bsort-inner lst))) 
      (loop ls (cons mx res))))))

对于递归版本，我更喜欢一个其中最小值气泡在前面：

(define (bsort-inner lst) 
    ; after one pass, smallest element is in front 
    (let ((ca1 (car lst)) (cd1 (cdr lst))) 
    (if (null? cd1) 
     lst ; just one element => sorted 
     (let ((cd (bsort-inner cd1))) ; cd = sorted tail 
      (let ((ca2 (car cd)) (cd2 (cdr cd))) 
      (if (<= ca1 ca2) 
       (cons ca1 cd) 
       (cons ca2 (cons ca1 cd2)))))))) 

(define (bsort lst) 
    (if (null? lst) 
     null 
     (let ((s (bsort-inner lst))) 
     (cons (car s) (bsort (cdr s))))))

来源

2014-02-18 00:15:05 uselpa

气泡排序与计划

回答

相关问题