F # сортировка с использованием head :: tail - PullRequest
Новая
       33

F # сортировка с использованием head :: tail

0 голосов
/ 23 мая 2011

Я пытаюсь написать рекурсивную функцию, которая использует head :: tail.Я понимаю, что голова в первом элементе списка и хвост это все остальные элементы в списке.Я также понимаю, как работает рекурсия.Что меня интересует, так это как сортировать элементы в списке.Есть ли способ сравнить голову с каждым элементом в хвосте, а затем выбрать самый маленький элемент?Мой опыт работы в C ++, и мне не разрешено использовать List.sort ().Есть идеи, как это сделать?Я посмотрел учебники на сайте MSDN и до сих пор не повезло

Ответы [ 2 ]

2 голосов
/ 23 мая 2011

Вам нужно выбрать методологию сортировки, прежде чем беспокоиться об используемой структуре данных. Если бы вы делали, скажем, сортировку вставкой, вы, вероятно, захотите начать с конца списка и вставлять элемент на каждом уровне рекурсии, следя за тем, как вы сами обрабатываете вставку.

Технически на любом конкретном уровне у вас есть доступ только к одному элементу данных, однако вы можете передать определенный элемент данных в качестве параметра для его сохранения. Например, здесь вставляемая часть алгоритма сортировки вставок, предполагается, что список отсортирован. 

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

Обратите внимание, что теперь у меня есть доступ к двум элементам: кешированному и оставшемуся. Другим вариантом может быть сортировка слиянием, когда у вас есть два отсортированных списка и, следовательно, два элемента для работы с любой конкретной итерацией.

Комментарий Даниэля с комментариями упоминает конкретную реализацию (быструю сортировку), если вам интересно.

Наконец, списки не являются оптимальными для алгоритмов сортировки из-за их жесткой структуры и необходимого количества выделений. Учитывая, что все известные алгоритмы сортировки имеют сложность> O (n), вы можете преобразовать свой список в массив и из него, чтобы повысить производительность без ущерба для асимптотической производительности.

EDIT:
Обратите внимание, что выше не в хвостовой рекурсивный формат, вам нужно сделать что-то вроде этого: 

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://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/lists

1 голос
/ 13 июля 2011

Вот рекурсивная реализация алгоритма быстрой сортировки на основе списка в 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)
...