В чем разница между быстрой сортировкой и сортировкой слиянием?

Question

Прав ли я, говоря, что в обоих алгоритмах все, что вы делаете - это берете свою структуру, рекурсивно разбиваете ее на две части, а затем строите свою структуру в правильном порядке?

Так в чем же разница?

Edit: я нашел следующий алгоритм для реализации раздела в быстрой сортировке, но я не совсем понимаю, как он работает, в частности, строка swop, которая использует (hi + low) >>> 1 в качестве аргумента! Кто-нибудь может понять это?

private static int partition( int[] items, int lo, int hi ) 
{
    int destination = lo;
    swop( items, (hi + lo) >>> 1, hi );
    // The pivot is now stored in items[ hi ].
    for (int index = lo; index != hi; index ++) 
    {
        if (items[ hi ] >= items[ index ]) 
        {
            // Move current item to start.
            swop( items, destination, index );
            destination ++;
        }

        // items[ i ] <= items[ hi ] if lo <= i < destination.
        // items[ i ] > items[ hi ] if destination <= i <= index.
    }

    // items[ i ] <= items[ hi ] if lo <= i < destination.
    // items[ i ] > items[ hi ] if destination <= i < hi.
    swop( items, destination, hi );
    // items[ i ] <= items[ destination ] if lo <= i <= destination.
    // items[ i ] > items[ destination ] if destination < i <= hi.
    return destination;
}

Answer 1

Прав ли я, говоря, что в обоих алгоритмах все, что вы делаете, - это берете свою структуру, рекурсивно разделяете ее на две части, а затем строите свою структуру в правильном порядке?

Да. Разница, однако, заключается в том, когда структура построена в правильном порядке. В быстрой сортировке фактический шаг сортировки выполняется во время разделения (перемещение элементов в левую или правую половину, в зависимости от сравнения с элементом сводки), и нет шага слияния для возврата к дереву (как видно из точки данных Конечно, ваша реализация может иметь разматывание стека), в то время как в Mergesort сортировка выполняется по пути вверх - шаг разделения вообще не перемещает элементы, но при возврате необходимо объединить два отсортированных списка .

Что касается сравнений производительности: безусловно, верно, что поведение Quicksort в худшем случае хуже, чем в Mergsesort, но постоянный коэффициент для среднего случая (который наблюдается почти исключительно на практике) меньше, что делает Быстрая сортировка обычно является победителем для общего, несортированного ввода. Не так много людей должны сами реализовывать общие процедуры сортировки ...

Answer 2

В худшем случае быстрая сортировка будет иметь O (n ^ 2), где сортировка слиянием будет O (n * log n)

Быстрая сортировка использует сводную точку и сортирует две части с помощью сводной точки в качестве контрольной точки с риском.что ось будет максимальным или минимальным из отсортированного массива.Если вы выберете неправильные пивоты, вы получите сложность n ^ 2 (n ^ 2 сравнения)

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

Answer 3

Quicksort имеет худший наихудший случай, тогда как Mergesort всегда гарантированно O (n log n), но типичные реализации Quicksort на практике быстрее, чем Mergesort.

Кроме того, Mergesort требуется дополнительное хранилище, что является проблемой во многих случаях (например, библиотечные процедуры). Вот почему Quicksort почти всегда используется библиотечными процедурами.

Редактировать: я нашел следующее Алгоритм реализации раздел в быстрой сортировке, но я не действительно понимаю, как это работает, в частности, линия Swop, которая использует (привет + низкий) >>> 1 в качестве аргумента!

Это среднее значение hi и low, эквивалентное (hi + low) / 2.

Answer 4

Детали реализации базовых структур данных также могут быть такими факторами, как эффективный произвольный доступ (необходимый для быстрой сортировки) и изменчивость структур данных будет влиять на требования к памяти (в частности, сортировка слиянием)

Answer 5

Да, Quicksort и Mergesort являются алгоритмами «разделяй и властвуй» .

Страница быстрой сортировки в Википедии содержит краткое сравнение:

Быстрая сортировка также конкурирует с mergesort, другим алгоритмом рекурсивной сортировки, но с преимуществом O (n для наихудшего случая) (nжурнал n) время работы.Mergesort является стабильной сортировкой, в отличие от быстрой сортировки и heapsort, и может быть легко адаптирован для работы со связанными списками и очень большими списками, хранящимися на медленных носителях доступа, таких как дисковое хранилище или сетевое хранилище.Хотя быстрая сортировка может быть написана для работы со связанными списками, она часто страдает от неудачного выбора сводных данных без произвольного доступа.Основным недостатком сортировки слиянием является то, что при работе с массивами в лучшем случае требуется O (n) вспомогательного пространства, тогда как вариант быстрой сортировки с разделением на месте и хвостовой рекурсией использует только пространство O (log n).(Обратите внимание, что при работе со связанными списками для сортировки слиянием требуется только небольшой постоянный объем вспомогательного хранилища.)

Answer 6

http://en.wikipedia.org/wiki/Sorting_algorithm Там у вас есть краткий обзор общих алгоритмов сортировки.Quicksort и Mergesort являются первыми двумя;)

Для получения дополнительной информации прочитайте информацию, приведенную по каждому из этих алгоритмов.Как сказал Ян, Mergesort всегда имеет сложность O (n * log n), а Quicksort до O (n ^ 2) в худшем случае