F# 使用 head::tail 排序

发布于 2024-11-09 12:57:34 字数 195 浏览 0 评论 0 原文

我正在尝试编写一个使用 head::tail 的递归函数。据我所知，列表的第一个元素中的 head 和列表中的所有其他元素。我也了解递归是如何工作的。我想知道如何对列表中的元素进行排序。有没有办法将头部与尾部的每个元素进行比较，然后选择最小的元素？我有 C++ 背景，并且不允许使用 List.sort()。知道如何去做吗？我已经查看了 msdn 网站上的教程，但仍然没有运气

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

烟织青萝梦 2024-11-16 12:57:34

这是 F# 中基于递归列表的快速排序算法的实现

let rec quicksort list =
    match list with
    | [] -> []
    | h::t ->
        let lesser = List.filter ((>) h) t
        let greater = List.filter ((<=) h) t
        (quicksort lesser) @[h] @(quicksort greater)

Here is recursive list-based implementation of quicksort algorithm in F#

let rec quicksort list =
    match list with
    | [] -> []
    | h::t ->
        let lesser = List.filter ((>) h) t
        let greater = List.filter ((<=) h) t
        (quicksort lesser) @[h] @(quicksort greater)

回复收藏 0 原文

梦里南柯 2024-11-16 12:57:34

在担心使用的数据结构之前，您需要决定排序方法。例如，如果要进行插入排序，您可能希望从列表的末尾开始，并在每个递归级别插入一个项目，并注意如何处理插入本身。

从技术上讲，在任何特定级别，您只能访问一个数据元素，但是您可以将特定数据元素作为参数传递以保留它。例如，这里是插入排序算法的插入部分，它假设列表已排序。

let rec insert i l =
    match l with
    | [] -> [i]
    | h::t -> if h > i then
                  i::l
              else
                  h::(insert i t)

请注意我现在如何访问两个元素：缓存的元素和其余元素。另一种变体是合并排序，其中您有两个排序列表，因此有两个项目可以处理任何特定的迭代。

如果您感兴趣，丹尼尔的评论答案提到了一个特定的实现（快速排序）。

最后，由于其严格的结构和所需的分配数量，列表对于排序算法来说并不是最佳的。假设所有已知的排序算法都是> O(n) 复杂度，您可以将列表转换为数组或从数组转换列表，以提高性能而不损害渐近性能。

编辑：
请注意，上面不是尾递归格式，您需要执行以下操作：

let insert i l =
    let rec insert i l acc =
        match l with
        | [] -> List.foldBack (fun e a -> e :: a) acc [i]
        | h::t -> if h > i then
                      List.foldBack (fun e a -> e :: a) acc i::l
                  else
                      insert i l (i::acc)
    insert i l []

我不记得立即反转列表的最佳方法，因此使用 https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/lists

You need to decide a sorting methodology before worrying about the data structure used. If you were to do, say, insertion sort, you would likely want to start from the end of the list and insert an item at each recursion level, being careful how you handle the insertion itself.

Technically at any particular level you only have access to one data element, however you can pass a particular data element as a parameter to preserve it. For instance here is the inserting part of an insertion sort algorithm, it assumes the list is sorted.

let rec insert i l =
    match l with
    | [] -> [i]
    | h::t -> if h > i then
                  i::l
              else
                  h::(insert i t)

Note how I now have access to two elements, the cached one and the remainder. Another variation would be a merge sort where you had two sorted lists and therefore two items to work with any particular iteration.

Daniel's commented answer mentions a particular implementation (quicksort) if you are interested.

Finally list's aren't optimal for sorting algorithms due to their rigid structure, and the number of allocations required. Given that all known sorting algorithms are > O(n) complexity, you can translate you list to and from an array in order to improve performance without hurting your asymptotic performance.

EDIT:
Note that above isn't in tail recursive format, you would need to do something like this:

let insert i l =
    let rec insert i l acc =
        match l with
        | [] -> List.foldBack (fun e a -> e :: a) acc [i]
        | h::t -> if h > i then
                      List.foldBack (fun e a -> e :: a) acc i::l
                  else
                      insert i l (i::acc)
    insert i l []

I don't remember offhand the best way to reverse a list so went with an example from https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/lists

回复收藏 0 原文

~没有更多了~