wiem wykonania dla większości z tych algorytmów, ale nie wiem, na co wielkości zbiorów danych, aby korzystać z nich (oraz dane zawarte):W jakich sytuacjach używam tych algorytmów sortowania?
Przede wszystkim bierzesz wszystkie algorytmy sortowania, które mają złożoność O(n2) i wyrzucasz je.
Następnie należy przeanalizować kilka właściwości algorytmów sortowania i zdecydować, czy każdy z nich będzie lepiej pasował do problemu, który chcesz rozwiązać. Najważniejsze to:
Czy algorytm jest na miejscu? Oznacza to, że algorytm sortowania nie używa żadnej (w rzeczywistości dodatkowej) (O(1)) dodatkowej pamięci. Ta właściwość jest bardzo ważna, gdy używasz aplikacji o krytycznym znaczeniu dla pamięci.
Sortowanie bąbelkowe, sortowanie wtrącone i sortowanie-sortowanie używają pamięci stałej. Istnieje również wariant lokalny dla Merge-sort.
Czy algorytm jest stabilny? Oznacza to, że jeśli dwa elementy x i y są równe podanej przez ciebie metodzie porównania, a na wejściu x zostanie znalezione przed y, to na wyjściu x zostanie znalezione przed y.
Sortowanie między sortami, sortowanie bąbelkowe i sortowanie metodą wstawiania są stabilne.
Czy algorytm można zrównoleglić? Jeśli tworzona aplikacja może wykorzystywać obliczenia równoległe, można wybrać algorytmy sortowania z możliwością równoległego sortowania.
Więcej informacji here.
Należy zauważyć, że zwykle implementacje scalania lub szybkiego sortowania używają sortowania wtrącania dla części podprogramu, w którym podrzędność jest bardzo mała.
Użyj opcji Sortowanie bąbelkowe tylko wtedy, gdy dane do sortowania są przechowywane w pamięci bębna obrotowego.Jest optymalny do tego celu, ale nie do pamięci o dostępie swobodnym. W tych dniach oznacza to "nie korzystaj z sortowania bąbelkowego".
Użyj sortowania lub wyboru Sortuj do określonego rozmiaru, testując go względem innych dostępnych rodzajów. Zwykle wynosi to około 20-30 elementów, ale YMMV. W szczególności przy wdrażaniu sortowania typu "podziel i nawij", takiego jak "Sortuj" i "Szybkie sortowanie", powinieneś "przełamać" sortowanie wsunięcia lub sortowanie zaznaczenia, gdy twój obecny blok danych jest wystarczająco mały.
Stosuj również sortowanie wtrącone w przypadku prawie posortowanych danych, na przykład, jeśli w jakiś sposób wiesz, że twoje dane były sortowane i od tamtej pory się nie zmieniły.
Użyj Połącz Sortuj, gdy potrzebujesz stabilnego sortowania (jest to również dobre podczas sortowania połączonych list), pamiętaj, że dla tablic używa znaczącej dodatkowej pamięci.
Generalnie nie używa się "zwykłego" szybkiego sortowania, ponieważ nawet przy inteligentnym wyborze czopów nadal ma najgorszy przypadek, ale w przeciwieństwie do Sortowania wtrącania nie ma żadnych użytecznych najlepszych przypadków. Przypadki "zabójcy" mogą być budowane systematycznie, więc jeśli sortujesz dane "niezaufane", niektórzy użytkownicy mogą celowo zabić twoją wydajność, a mimo to może istnieć jakiś specyficzny dla domeny powód, dla którego twoje dane są zbliżone do przypadków zabójstw. Jeśli wybierzesz losowe czopy, prawdopodobieństwo wystąpienia zabójczych przypadków jest znikome, więc jest to opcja, ale typowym podejściem jest "IntroSort" - QuickSort, który wykrywa złe przypadki i przełącza się na HeapSort.
Sortowanie radixów jest trochę dziwne. Trudno jest znaleźć typowe problemy, dla których jest najlepszy, ale ma dobry limit asymptotyczny dla danych o stałej szerokości (O(n), gdzie sortowanie porównawcze to Omega(n log n)). Jeśli twoje dane mają ustaloną szerokość, a dane wejściowe są większe niż liczba możliwych wartości (na przykład ponad 4 miliardy 32-bitowych liczb całkowitych), wtedy zaczyna być szansa, że niektóre rodzaje sortowania radix będą działać dobrze.
+1 Najwygodniejsze wyjaśnienie. – dreamcrash