Doba běhu pro metodu Arrays.Sort v Javě

Ví někdo dobu běhu ve velkém O zápisu pro java metodu arrays.sort? Potřebuji to pro svůj projekt vědeckého veletrhu.

Odpověď

Z oficiálních dokumentů

Všiml jsem si, že existují především dva přístupy. Záleží tedy na tom, co třídíte a jaká přetížená metoda z sort skupina metod, které voláte.

Dokumenty to zmiňují u primitivních typů například long , byte (Příklad:static void sort(long[]) ):

Algoritmus třídění je vyladěný quicksort, převzatý z knihy Jon L.Bentley a M. Douglas McIlroy „Engineering a Sort Function“, Software-Practice and Experience, sv. 23(11) str. 1249-1265 (listopad 1993). Tento algoritmus nabízí výkon n*log(n) na mnoha souborech dat, které způsobují degradaci jiných rychlých tříd na kvadratický výkon.

Pro typy objektů: (Příklad:void sort(Object list[]) )

Zaručený výkon O(nlogn)

Algoritmus řazení je modifikovaný mergesort (ve kterém je sloučení vynecháno, pokud je nejvyšší prvek v dolním podseznamu menší než nejnižší prvek v horním podseznamu). Tento algoritmus nabízí zaručený výkon n*log(n).

Doufám, že to pomůže!