任何更简单的方法来实现OCaml中的非原位选择排序？ [英] Any simpler way to implement non-in-place selection sort in OCaml?

问题描述

我在OCaml中实现了一个非就地选择排序版本。

I implemented a non-in-place version of selection sort in OCaml.

let sort compare_fun l = 
    let rec find_min l' min_l origin_l =
      match l' with
    | [] -> 
      if min_l = [] then (min_l, l')
      else 
        let min = List.hd min_l 
        in 
        (min_l, List.filter (fun x -> if x != min then true else false)  origin_l)
    | x::tl -> 
      if min_l = [] then
        find_min tl [x] origin_l
      else 
        let c = compare_fun (List.hd min_l) x
        in 
        if c = 1 then 
          find_min tl [x] origin_l
        else if c = 0 then
          find_min tl (min_l @ [x]) origin_l
        else 
          find_min tl min_l origin_l
    in 
    let rec insert_min l' new_l =
      match l' with
    | [] -> new_l
    | _ -> 
      let (min_l, rest) = find_min l' [] l'
      in 
      insert_min rest (new_l @ min_l)
    in 
    insert_min l [];;

---

我的想法是，我找到最小项目列表（如果有重复值），并将这个 min列表添加到结果列表中，然后在列表的其余部分重新找到finding_min。

---

My idea is that in a list, every time I find the list of minimum items (in case of duplicate values) and add this min list to the result list, then redo the finding_min in the rest of the list.

我使用 List.filter 来过滤 min_list ，所以结果列表将成为下一个 find_min 的列表。

I use List.filter to filter out the min_list, so the resulting list will be the list for next find_min.

我发现我的实现非常复杂，比选择排序的Java就地版本更复杂。

I find my implementation is quite complicated, and far more complicated than the Java in-place version of selection sort.

有什么建议可以改进它？

Any suggestions to improve it?

推荐答案

编辑：这是一个更好的实现： http：// rosettacode。 org / wiki / Sorting_algorithms / Selection_sort＃OCaml

Here's a much better implementation: http://rosettacode.org/wiki/Sorting_algorithms/Selection_sort#OCaml

这里是我自己的一个难题实现

here's my own crappier implementation

(* partial function - bad habit, don't do this. *)
let smallest (x::xs) = List.fold_right (fun e acc -> min e acc) xs x

let remove l y =
  let rec loop acc = function
    | [] -> raise Not_found
    | x::xs -> if y = x then (List.rev acc) @ xs else loop (x::acc) xs
  in loop [] l

let selection_sort = 
  let rec loop acc = function
    | [] -> List.rev acc
    | xs -> 
        let small = smallest xs in
        let rest = remove xs small in
        loop (small::acc) rest
  in loop [] 

这篇关于任何更简单的方法来实现OCaml中的非原位选择排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！