Powiel możliwe:
Why java Arrays use two different sort algorithms for different types?Java: Arrays.sort quicksort i mergesort
Więc byłem czytania tablic doc na różnych implementacjach sortowania. Zauważyłem, że niektóre implementacje używały dostrojonego quicksortu, podczas gdy inne używały zmodyfikowanego mergesortu. Skąd ta rozbieżność?
Dzięki!
Quicksort jest używany do tablic typów pierwotnych, gdy mergesort do tablic Object [].
Głównym powodem mergesort służy do obiektów, które mergesort jest stabilny - nie zmienić kolejność elementów, które są równe: http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
Dla prymitywów stabilność rodzaju nie ma sensu, ponieważ nie można wyróżnić dwie wartości, które są równy. Dlatego używa się quicksort (z wyjątkiem sortowania tablicy obiektów, dla których wykonywany jest mergesort). Co więcej, quicksort można zrobić na miejscu, więc nie ma potrzeby przydzielania kolejnej tablicy.
W dzisiejszym świecie, mergesort stał się dominującym sorterem, ponieważ można go zaimplementować do używania wielu rdzeni – ControlAltDel
, ale JDK na razie tego nie używa. –
Powiedział, że JDK 7 nie używa już mergesort - używa mitycznego [TimSort] (http://en.wikipedia.org/wiki/Timsort)! –
zaznaczone, dziękuję michael! – OckhamsRazor