Это моя попытка на F #. Реализация обычной сортировки слиянием для справки:
// Sorts a list containing elements of type T. Takes a comparison
// function comp that takes two elements of type T and returns -1
// if the first element is less than the second, 0 if they are equal,
// and 1 if the first element is greater than the second.
let rec sort comp = function
| [] -> [] // An empty list is sorted
| [x] -> [x] // A single element list is sorted
| xs ->
// Split the list in half, sort both halves,
// and merge the sorted halves.
let half = (List.length xs) / 2
let left, right = split half xs
merge comp (sort comp left) (sort comp right)
Теперь попытка натуральной версии. В лучшем случае это будет O (n), но в лучшем случае - когда список ввода находится в обратном порядке.
let rec sort' comp ls =
// Define a helper function. Streaks are stored in an accumulator.
let rec helper accu = function
| [] -> accu
| x::xs ->
match accu with
// If we are not in a streak, start a new one
| [] -> helper [x] xs
// If we are in a streak, check if x continues
// the streak.
| y::ys ->
if comp y x > 0
// x continues the streak so we add it to accu
then helper (x::y::ys) xs
// The streak is over. Merge the streak with the rest
// of the list, which is sorted by calling our helper function on it.
else merge comp accu (helper [x] xs)
helper [] ls
Вторая попытка. Это также будет O (n) в лучшем случае, тогда как в лучшем случае сейчас, когда список ввода уже отсортирован. Я отказался от функции сравнения. Отсортированный список будет построен в обратном порядке, поэтому вам нужно будет перевернуть его в конце.
let rec sort'' comp ls =
// Flip the comparison function
let comp' = fun x y -> -1 * (comp x y)
let rec helper accu = function
| [] -> accu
| x::xs ->
match accu with
| [] -> helper [x] xs
| y::ys ->
if comp' y x > 0
then helper (x::y::ys) xs
else merge comp' accu (helper [x] xs)
// The list is in reverse sorted order so reverse it.
List.rev (helper [] ls)
person
mushroom
schedule
07.12.2012