Quicksort с разделом с 3 путями
Вы постоянно изменяете свой источник данных.
Самый простой неугловой способ сделать это - создать filteredRecords копию, которую вы назначаете только , при этом фильтруя оригинал records.
this.filteredRecords = this.records.filter(...)
Если вы хотите быть более осторожным, вы можете создать фильтр-канал, который сделает это для вас на пути к вашему шаблону.
4 ответа
Изобразите массив:
3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0
Быстрая сортировка двух разделов выберет значение, скажем 4, и поместит каждый элемент больше 4 на одну сторону массива и каждый элемент меньше 4 с другой стороны. Примерно так:
3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5
трехраздельная быстрая сортировка выберет два значения для разбиения и разделит массив таким образом. Давайте выберем 4 и 7:
3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9
Это всего лишь небольшой вариант обычной быстрой сортировки.
Вы продолжаете разбивать каждый раздел на разделы, пока массив не будет отсортирован. Технически среда выполнения - nlog 3 (n), что немного отличается от nlog 2 (n) в обычной быстрой сортировке.
3 путями быстрая сортировка в основном делит массив в 3 частях. Первая часть меньше, чем центр, Вторая часть равна центру, и третья часть больше, чем центр. Это - линейно-разовый алгоритм раздела. Этот раздел подобен голландской проблеме Национального флага.
http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf
См. Также:
http://www.sorting-algorithms.com/quick- sort-3-way
Мне показалась интересной и версия вопроса для интервью. Он спрашивает, есть ли четыре версии разделов быстрой сортировки ...
если вы действительно перемалываете математику, используя формулу Акра-Бацци , оставляя количество разделов в качестве параметра, а затем оптимизируете это значение параметр, вы обнаружите, что разделы e (= 2,718 ...) обеспечивают максимальную производительность. на практике, однако, все наши языковые конструкции, процессоры и т. д. оптимизированы для двоичных операций, поэтому стандартное разделение на два набора будет наиболее быстрым.