list - 如何在列表球拍的正确位置插入数字？

Question

假设你插入 (15) 如果我运行这个程序，输出将是 (14 16 17 18 19) 我怎样才能让程序在正确的位置插入数字 15 (pos = 1) 或任何数字 (n)这是正确的位置（pos）。

(define list1 '(14 16 17 18 19))

(define lst (list))
(define (insert lst n)
  (if (empty? lst)
      '()
      (foldr cons (list n) lst))) ;The value gets inserted at the end of the list

Answer 1

我们有许多排序算法，如快速排序、直方图排序、冒泡排序。

您可以查看此排序算法或维基百科。

如果n大于列表中的每个数据，lst我们'()就返回(list n)

例如(f '() 1) -> '(1)

当n小于或等于第一个元素时，我们在第一个位置插入。

例如(f '(2) 1) -> (cons 1 '(2))

如果不是，我们想要这样的数据： (f '(1 2 4) 3) -> (cons 1 (f '(2 4) 3)) -> (cons 1 (cons 2 (f '(4) 3))) -> (cons 1 (cons 2 (cons 3 '(4)))) -> (list 1 2 3 4)

(define (insert-with-<-order lst n)
  (cond
    [(empty? lst)
     (list n)]
    [(<= n (first lst))
     (cons n lst)]
    [else
     (cons (first lst)
           (insert-with-<-order (rest lst) n))]))

(insert-with-<-order '(1 1 2 3) 1.5)
(insert-with-<-order '(-2 0.5 1 2 5) 0.1)
(insert-with-<-order '(1 2 3) 4)

利用sort

(define (insert-with-order lst n)
  (sort (cons n lst) <))

(insert-with-order '(14 16 17 18 19) 15)