在函数式编程语言中排序

Question

我已经学习了一段时间的函数式编程,但我还没有读过有关使用函数式编程语言进行排序的内容.

我知道基于价值交换的排序算法很难用功能性的想法实现,但我想知道有没有用于函数式编程的排序算法？这些是什么？

谢谢.

Answer 1

在函数式语言中,您编写一个函数,给定一个列表返回一个排序列表,而不是接触(当然)输入.

考虑例如合并排序...首先你编写一个函数,给定两个已经排序的列表返回一个单独的排序列表,其中包含两个元素.例如:

def merge(a, b):
    if len(a) == 0:
        return b
    elif len(b) == 0:
        return a
    elif a[0] < b[0]:
        return [a[0]] + merge(a[1:], b)
    else:
        return [b[0]] + merge(a, b[1:])

然后你可以编写一个函数,通过合并列表的第一和第二半的结果来对列表进行排序.

def mergesort(x):
    if len(x) < 2:
        return x
    else:
        h = len(x) // 2
        return merge(mergesort(x[:h]), mergesort(x[h:]))

关于Python语法:

• L[0] 是列表的第一个元素 L
• L[1:] 是所有剩余元素的列表
• 更一般地说,L[:n]是第n个元素的列表,L[n:]其余的
• A + Bif A和B是两个列表是通过串联获得的列表
• [x] 是一个只包含单个元素的列表 x

PS:注意上面的python代码只是为了展示概念...在Python中这不是一个合理的方法.我使用Python是因为我认为如果你知道任何其他常见的命令式语言,它是最容易阅读的.

Answer 2

以下是Haskell中实现的排序算法的一些链接:

• 快速排序
• 插入排序
• 合并排序
• 选择排序
• 数排序

合并排序通常是排序链表的最佳选择.功能语言通常在列表上运行,尽管我对大多数函数式语言如何实现列表知之甚少.在Common Lisp中,它们被实现为链表,我认为大多数函数式语言也是如此.

虽然可以为链表创建快速排序,但由于随机访问,它将受到不良的枢轴选择的影响.虽然这对完全随机输入无关紧要,但在部分或完全分类的输入枢轴选择变得非常重要.其他排序算法也可能受到链表的慢随机访问性能的影响.

另一方面,合并排序适用于链表,并且可以实现该算法,使得它仅需要链接列表的一些额外空间常量.

Answer 3

这是Haskell中的经典(伪 - ？)快速排序:

sort []      =   []
sort (p:xs)  =   sort [x | x<- xs, x <= p]
              ++ [p]
              ++ sort [x | x <- xs, x > p]

参见,例如,c2.com或LiteratePrograms.org.合并排序并不难写,在实践中更可靠.在Scheme中也可以这样做:

(define (sort xs)
  (if (null? xs)
    '()
    (let* ((p (car xs)) (xs (cdr xs)))
      (call-with-values (lambda () (partition (lambda (x) (<= x p)) xs))
                        (lambda (l r)
                          (append (sort l) (list p) (sort r)))))))

与partition从SRFI-1 (未测试的代码).另见R6RS库的第4章.