Объяснение алгоритма Медиана медиан
Median of medians
подход очень популярен вquicksort
Используйте алгоритмы разделения типов, чтобы получить довольно хороший поворот, чтобы он равномерно разделял массив. Его логика дана в Википедии как:
The chosen pivot is both less than and greater than half of the elements in the list of medians, which is around n/10 elements (1/2 * (n/5)) for each half. Each of these elements is a median of 5, making it less than 2 other elements and greater than 2 other elements outside the block. Hence, the pivot is less than 3(n/10) elements outside the block, and greater than another 3(n/10) elements outside the block. Thus the chosen median splits the elements somewhere between 30%/70% and 70%/30%, which assures worst-case linear behavior of the algorithm.
Может ли кто-нибудь объяснить это немного доходчиво для меня. Мне трудно понять логику.