11

SML 中有标准的排序功能吗？Internet 上的文档非常稀缺，我找不到任何文档。

4

5 回答 5

16

瑞秋只说对了一部分。SML 基础库中确实没有定义排序功能，但是大多数实现都扩展了基础库并添加了额外的功能。

因此，MosML 有一个ArraySort和一个Listsort模块，而 SML/NJ 有一个带有 ListMergeSort 实现的LIST_SORT签名。它还具有一些其他的数组排序功能，如 MosML。有关完整列表，请参阅SML /NJ 库手册的目录。

于 2013-01-19T09:03:20.543 回答
5

正如 Jesper Reenberg 指出的那样，标准 ML 编译器都有自己的（非标准的，具有讽刺意味的）排序库。由于这些文档缺少示例，以下是如何使用各种模块按升序对字符串列表进行排序：

  1. 在 SML/NJ 和 MLton 中，使用ListMergeSort.sort函数：

    - fun sortStrings ss = ListMergeSort.sort (fn (s : string, t) => s > t) ss;
[autoloading]
[library $SMLNJ-LIB/Util/smlnj-lib.cm is stable]
[autoloading done]
val sortStrings = fn : string list -> string list
- sortStrings ["World","Hello"];
val it = ["Hello","World"] : string list

    这个库函数的怪癖是它需要一个“大于”布尔谓词。由于标准 ML 的>运算符被重载，但默认为int，我必须以某种方式明确注释我正在比较strings。

  2. 在莫斯科 ML 中，使用以下Listsort.sort函数：

    - load "Listsort";
> val it = () : unit
- fun sortStrings ss = Listsort.sort String.compare ss;
> val sortStrings = fn : string list -> string list
- sortStrings ["World", "Hello"];
> val it = ["Hello", "World"] : string list

    这个库的怪癖是莫斯科 ML 的交互式 REPL 不会自动加载Listsort。load "Listsort";仅在交互式 REPL 中需要键入；编译程序时，load不使用。

  3. 在 Poly/ML 中，没有用于排序的库，因此您必须定义自己的排序函数。

如果这些排序函数都不够用，这里有一些用标准 ML 编写的其他排序函数：

  1. 标准 ML 中的 True QuickSort将一个简单的QuickSort（这并不是真正的 QuickSort）与John Coleman的Hoare 算法的实现进行了比较。

  2. Rosetta Code 在标准 ML 中的 MergeSort：

    fun merge cmp ([], ys) = ys
  | merge cmp (xs, []) = xs
  | merge cmp (xs as x::xs', ys as y::ys') =
      case cmp (x, y) of
           GREATER => y :: merge cmp (xs, ys')
         | _       => x :: merge cmp (xs', ys)

fun sort cmp [] = []
  | sort cmp [x] = [x]
  | sort cmp xs =
    let
      val ys = List.take (xs, length xs div 2)
      val zs = List.drop (xs, length xs div 2)
    in
      merge cmp (sort cmp ys, sort cmp zs)
    end
于 2018-05-14T23:29:09.307 回答
2

这是一个标准的快速排序

fun qsort(func) =
    let fun sort [] = []
          | sort (lhd :: ltl) =
                sort (List.filter (fn x => func (x, lhd)) ltl)
              @ [lhd]
              @ sort (List.filter (fn x => not (func(x, lhd)) ltl)
    in sort
    end

只需放入一些比较器（接受两个具有相同类型的元素并返回布尔值的函数），它将为您返回一个排序函数如果您还有问题，请不要犹豫。:)

于 2017-01-25T17:46:49.687 回答
0

这个排序列表怎么样？你总是可以使用 reverse 来获得相反的结果。

- fun sort(L) =
   if L=[] then []
   else if tl(L)=[] then L
   else merge(sort(take(L)), sort(skip(L)));
 val sort = fn : int list -> int list

见这里。

于 2013-01-19T07:02:22.270 回答
0

这是我的 sml 排序算法

fun sort list = foldr (fn (x,lst)=> List.filter (fn a => a < x) lst @ [x] @ List.filter (fn a => a >= x) lst ) [] list;

sort [5,1,5,0,2,5,~2,5,~10,0];

output: [~10,~2,0,0,1,2,5,5,5,5]

我希望它有帮助

于 2020-05-18T11:45:28.940 回答