Ich habe versucht, eine Implementierung von QuickSort (mit Median von 3 Partitionierungselement und Insertion Sortierung für kleine Arrays) und vergleichen Sie es mit einer Implementierung von MergeSort, aber auch wenn QuickSort durchschnittliche Zeit sollte besser sein als die von MergeSort, Jedes Mal, wenn ich es ausführe, scheint es mehr Zeit zu benötigen, ein Array zu sortieren (sogar eines in zufälliger Reihenfolge). Irgendeine Idee, warum kann das geschehen?
QuickSort:
%Vor%MergeSort:
%Vor%Wenn ich beispielsweise diesen Algorithmus für 10 zufällige Arrays mit der Länge 10 ^ 8 ausführte, benötigte MergeSort durchschnittlich 13385,8 ms für die Ausführung, während QuickSort im Durchschnitt 14096,7 ms benötigte.
Zur Klarstellung, so habe ich die Ausführungszeiten gemessen
%Vor% Nachdem ich viele Dinge ausprobiert habe, um herauszufinden, wo das Problem lag, habe ich die Funktion geändert, die das zufällige Array erstellt hat, und es stellt sich heraus, dass QuickSort tatsächlich jetzt schneller arbeitet. Ich weiß nicht wirklich warum, aber anscheinend hat die Art, wie ich das Array erstellt habe, die Performance von QuickSort beeinträchtigt. Nun, was ich getan habe, war, dass, anstatt ein Array von zufälligen Ganzzahlen zu erzeugen, ich eine Array-Form von 1 bis n erzeugte und dann wie folgt mixte: