прикладная логика сортировки слиянием - PullRequest
1 голос
/ 15 июня 2011

Я пытаюсь решить проблему, в которой я использую сортировку слиянием, чтобы получить следующий случай: в массиве из n элементов

получить наименьшее число в массиве, а затем получить наибольшее число SOих вычитание (или разница между этими числами самая большая)

например: n = 8 обр. {7,8,10,20,4,19,50,70} Я хочу получить 4 и 70, потому чтоих разница составляет 66. На самом деле не имеет значения, получу ли я самые низкие и самые большие цифры, я забочусь только о самой большой разнице в их вычитании.ТАКЖЕ, ПЕРВЫЙ НОМЕР ДОЛЖЕН БЫТЬ НАИМЕНЬШЕ, ЧЕМ ВТОРОЙ ОДИН, 70 и 4 не допускаются.

, поскольку эта проблема требует от меня изменения кода сортировки слиянием, я думал: 1) разделить все числа на массивыиз 1, 2) сравните число i в массиве с числом i + 1, и, если число i наименьшее, получите их разницу и продолжайте перемещаться по всем позициям в массиве.

что вы думаете?Также у меня проблемы с настройкой базового варианта: S, пожалуйста, помогите!

Ответы [ 2 ]

0 голосов
/ 15 июня 2011

Философия сортировки слиянием заключается в объединении результатов из меньших сегментов в большие.

В сортировке слиянием сначала вы объединяете 2 элемента (2 массива по 1 элементу) в отсортированный массив из 2 элементов, изатем объединить 2 отсортированных массива из 2 элементов в отсортированный массив из 4 элементов (поскольку 2 массива отсортированы, вам нужно только пройти и сравнить, более мелкие элементы всегда идут первыми в обоих массивах в порядке возрастания), а затем объединить 2 отсортированныхмассивы из 4 элементов в отсортированный массив из 8 элементов.

|   |   |   |   |   |   |   |   |
|sorted |       |       |       |
|sorted         |               |
|sorted                         |

Теперь вам нужно только найти самый большой и самый маленький, таким образом, вам нужно только найти самый большой и самый маленький из 2 элементов.Сравните 2 самых больших элемента из 2 массивов из 2 элементов и найдите больше, а затем сравните 2 самых больших элемента из 2 массивов из 4 элементов и найдите больше и так далее.(То же самое для маленькой стороны.)

|   |   |   |   |   |   |   |   |
|S     L|       |       |       |
|Smllst    Lrgst|               |
|only need to care about S & L  |

Другими словами, вы больше не сортируете весь массив, а находите самые большие и самые маленькие и объединяете результаты, чтобы получить окончательный ответ.

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

0 голосов
/ 15 июня 2011

Базовая сортировка слиянием сортирует ваш массив, так что вы легко можете получить самые большие и самые маленькие числа.Но вы просто пытаетесь изменить массив так, чтобы вы получали только самые большие и самые маленькие числа - вас не волнуют те, что в середине.Они фактически являются мусором, как только вы их идентифицируете.

Как вы можете определить, является ли число, на которое вы смотрите, бесполезным?Что ж, если это так, то это не самое маленькое и не самое большое число в вашей текущей области.

Начните с просмотра псевдо-кода для сортировки слиянием.Какие наименьшие изменения вы можете внести, чтобы более точно решить эту проблему?

...