Wiemy, że sortowanie szybkie jest najlepszym algorytmem sortowania.Dlaczego Collections.sort używa sortowania scalonego zamiast quicksort?
W collections.sort zastosowano algorytm sortowania seryjnego zamiast szybkiego sortowania. Ale Arrays.sort używa szybkiego sortowania.
Z jakiego powodu CollectionsSort używa sortowania zamiast szybkiego sortowania?
wysoce prawdopodobne z Joshem Bloch §:
zrobiłem napisać te metody, więc przypuszczam, że jestem przygotowany do odpowiedzi. To jest prawdziwe, że nie ma jednego najlepszego algorytmu sortowania. QuickSort ma dwa główne braki w porównaniu do mergesort:
To nie jest stabilny (jak wspomniano Parsifal).
To nie daje gwarancji n log n wydajność; może obniżyć się do kwadratowej wydajności na wejściach patologicznych.
Stabilność to nie problem dla typów pierwotnych, jak nie ma pojęcia tożsamości jako odrębny od (wartości) równości. Możliwość zachowywania się kwadratów została uznana za nie problem w praktyce dla Implementacji Bentely i McIlroy (lub później dla Dual Pivot Quicksort), dlatego te warianty QuickSorta zostały użyte do sortowania pierwotnego w wersjach .
Stabilność to wielka sprawa przy sortowaniu dowolnych obiektów. Na przykład, załóżmy, że masz obiekty reprezentujące wiadomości e-mail i sortujesz je najpierw według daty, a następnie przez nadawcę. Oczekujesz, że zostaną one posortowane według daty nadania w każdym z nich, ale będzie to prawdą tylko wtedy, gdy sortowanie będzie stabilne na poziomie . Właśnie dlatego wybraliśmy dostarczenie sortowania stabilnego (Sortowanie scalone) do sortowania odniesień do obiektów. (Techincally mówiąc, wiele sekwencyjnych stabilne rodzaju skutkować leksykograficznego zamawiającego na klawiszach w odwrotnej kolejności rodzaju: ostateczny porządek określa najbardziej znaczący podklucz.)
Jest to miły korzyści boczny że Merge Sort gwarantuje n log n (czas) wydajność bez względu na dane wejściowe. Oczywiście jest jeszcze jeden minus: sortowanie szybkie to sortowanie "na miejscu": wymaga tylko log n przestrzeni zewnętrznej (aby zachować stos wywołań). Połącz, sortuj, z drugiej strony, wymaga O (n) przestrzeni zewnętrznej. Wariant TimSort (wprowadzony w Javie SE 6) wymaga znacznie mniej miejsca (O (k)), jeśli tablica wejściowa jest prawie posortowana według tablic wejściowych .
Również following ma znaczenie:
algorytm wykorzystywany przez java.util.Arrays.sort i (pośrednio) java.util.Collections.sort sortowania odwołań do obiektów jest " zmodyfikowano mergesort (w którym pomijanie jest pomijane, jeśli najwyższy element na niższej podliście jest mniejszy niż najniższy element na wysokiej podlistie)."To jest względnie szybkim, stabilnym rodzajem, który gwarantuje wydajność O (n log n) i wymaga O (n) dodatkowej przestrzeni.W jej dniu (napisano w 1997 roku przez Joshua Blocha), był to świetny wybór, ale ale dzisiaj możemy zrobić znacznie lepiej.
Od 2003 Pythona sortowania listy wykorzystał algorytm znany jako timsort (po Tim Peters, który to napisał). jest to stabilny, adaptacyjne, iteracyjny mergesort że wymaga daleko mniej niż n log (n) porównań, gdy działa na częściowo posortowanych tablicach, oferując wydajność porównywalną do tradycyjnej mergesort, gdy jest uruchamiana na losowych tablicach. Podobnie jak , wszystkie poprawne mergesorts timsort jest stabilny i działa w czasie O (n log n) (najgorszy przypadek). W najgorszym przypadku timsort wymaga tymczasowej przestrzeni do przechowywania obiektów odniesienia n/2; w najlepszym przypadku wymaga tylko małej stałej ilości miejsca. Porównaj to z bieżącą implementacją , która zawsze wymaga dodatkowej przestrzeni dla obiektów o numerach i bije n log n tylko na prawie posortowanych listach.
Timsort jest opisany szczegółowo tutaj: http://svn.python.org/projects/python/trunk/Objects/listsort.txt.
oryginalna realizacja Tim Peters jest napisany w C. Joshua Bloch przeniesiony go od C do Java i koniec testowane odwzorować, a dostrojone Otrzymany kod obszernie. Powstały kod jest zamiennikiem zamiennikiem dla java.util.Arrays.sort. W przypadku bardzo uporządkowanych danych ten kod może działać do 25 razy szybciej niż bieżąca implementacja (na maszynie wirtualnej serwera HotSpot). W przypadku danych losowych prędkości starych i nowych implementacji są porównywalne. W przypadku bardzo krótkich list, nowa implementacja jest znacznie szybsza niż stare dane losowe o wartości (ponieważ pozwala uniknąć niepotrzebnego kopiowania danych).
Zobacz także Is Java 7 using Tim Sort for the Method Arrays.Sort?.
Nie ma jednego "najlepszego" wyboru. Podobnie jak wiele innych rzeczy, chodzi o kompromisy.
Jeśli nie możesz poprosić autora JDK o odpowiedź, wszystko, co dostaniesz, to zgadywanie. To nie jest prawdziwe pytanie. – EJP
@EJP Dobra rada, ale na pewno "Nie konstruktywny" jest właściwym powodem zamknięcia. Dla mnie jest jasne, o co tu chodzi. –
Ponieważ faceci Java postanowili zrobić to w ten sposób. Poprosić ich. Nie sądzę, że nie można uzyskać uzasadnionej odpowiedzi. A szybki sort to ** nie ** najlepszy. Jest to najlepsze rozwiązanie dla ** ogólnego zastosowania **. –