DasMedian of medians Ansatz ist sehr beliebt inquicksort Geben Sie Partitionierungsalgorithmen ein, um einen recht guten Pivot zu erzielen, sodass das Array gleichmäßig partitioniert wird. Seine Logik ist in Wikipedia wie folgt angegeben:

Der gewählte Drehpunkt ist sowohl kleiner als auch größer als die Hälfte der Elemente in der Liste der Mediane, dh ungefähr n / 10 Elemente (1/2 * (n / 5)) für jede Hälfte. Jedes dieser Elemente ist ein Median von 5, was bedeutet, dass es weniger als 2 andere Elemente und mehr als 2 andere Elemente außerhalb des Blocks enthält. Daher ist der Drehpunkt kleiner als 3 (n / 10) Elemente außerhalb des Blocks und größer als andere 3 (n / 10) Elemente außerhalb des Blocks. Somit teilt der gewählte Median die Elemente irgendwo zwischen 30% / 70% und 70% / 30% auf, was ein lineares Verhalten des Algorithmus im ungünstigsten Fall sicherstellt.

Kann mir jemand das ein bisschen klar erklären. Ich finde es schwierig, die Logik zu verstehen.