sorting - 按功能编程语言排序

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 + B和 A都是列表，则为

B是通过串联

获得的列表

[x]是仅包含单个元素的列表x

PS:请注意，上面的python代码只是为了展示概念……在Python中，这不是一种合理的方法。我使用Python是因为如果您知道任何其他常见的命令性语言，它就是最容易阅读的语言。