排序时以相反顺序附加附加元素的解决方法

Question

我想排序，使列表中的奇数首先出现，偶数最后出现，但我需要偶数与预排序的位置相同，有一个简单的解决方法吗？

let rec first_odd list = match list with
| [] -> []
| h::t when h mod 2==0 -> first_odd t@[h]
| h::t -> h::first_odd t;;

first_odd[3;1;7;3;4;5;4;3;6;-1;0;3];;
first_odd[1;0;1;5;6;6;1;10;-8;4; -9];;

Answer 1

您可以使用

List.stable_sort

，它实现了合并排序，并带有一个比较每个元素是奇数还是偶数的函数：

let first_odd =
  List.stable_sort
    (fun a b -> compare (a mod 2 = 0) (b mod 2 = 0))

first_odd[3;1;7;3;4;5;4;3;6;-1;0;3];;
- : int list = [3; 1; 7; 3; 5; 3; -1; 3; 4; 4; 6; 0]

first_odd[1;0;1;5;6;6;1;10;-8;4; -9];;
- : int list = [1; 1; 5; 1; -9; 0; 6; 6; 10; -8; 4]

Answer 2

这看起来像是一项家庭作业，所以我只发表一些评论。

首先，

list @ [elt]

这个表达看起来很糟糕。如果对列表中的 n 个元素重复此操作，则其复杂度为 n^2，因为添加到列表末尾需要线性时间。此外，有必要复制整个列表才能将元素添加到末尾。所以这绝对是要避免的事情。

其次，如果你编写了一个给出你想要的顺序的比较函数，你可以只使用

List.stable_sort

。这将比您当前的解决方案快得多（因为它将是 n log n 而不是 n^2）。

第三，如果您想使用当前的方法，我会保留两个列表并在最后将它们组合起来。

Answer 3

作为一项学术练习，以折叠的方式实现这一点可能会有所帮助。使用折叠时，初始状态至关重要。让我们在一个元组中使用两个列表。一种是奇数，一种是偶数。

每次迭代我们都会考虑初始值和列表中的第一个元素。我们提供的函数使用该信息为下一次迭代提供更新的初始值，该迭代考虑列表中的下一个元素。

let list1 = [3; 1; 7; 3; 4; 5; 4; 3; 6; -1; 0; 3]
let list2 = [1; 0; 1; 5; 6; 6; 1; 10; -8; 4; -9]

let sort lst =
  List.fold_left (* function *) ([], []) lst

现在，我们只需要一个在每次迭代时更新初始值的函数。如果该值是偶数，我们会将其添加到事件列表的前面。否则，进入赔率表的前面。

let sort lst =
  List.fold_left 
    (fun (odds, evens) x -> 
       if x mod 2 = 0 then (odds, x :: evens)
       else (x :: odds, evens)) 
    ([], []) 
    lst

如果我们用

list2

进行测试：

# sort list2;;
- : int list * int list = ([-9; 1; 5; 1; 1], [4; -8; 10; 6; 6; 0])

两个列表是倒序的。我们可以用

List.rev

解决这个问题。

let sort lst =
  let odds, evens = 
    List.fold_left 
      (fun (odds, evens) x -> 
         if x mod 2 = 0 then (odds, x :: evens)
         else (x :: odds, evens)) 
      ([], []) lst
  in
  List.(rev odds, rev evens)

# sort list2;;
- : int list * int list = ([1; 1; 5; 1; -9], [0; 6; 6; 10; -8; 4])

本质上我们现在已经重新发明了

List.partition

。

现在，我们只需连接这两个列表即可。

let sort lst =
  let odds, evens = 
    List.fold_left 
      (fun (odds, evens) x -> 
         if x mod 2 = 0 then (odds, x :: evens)
         else (x :: odds, evens)) 
      ([], []) 
      lst
  in
  List.(rev odds @ rev evens)

# sort list2;;
- : int list = [1; 1; 5; 1; -9; 0; 6; 6; 10; -8; 4]