Problem polega na tym, że mam listę 1 miliona numerów, ale chcę tylko 10 pierwszych posortowanych list, ale nie chcę sortować cała lista? Czy to jest możliwe?Jak uzyskać pierwsze 10 posortowanych pozycji z listy bez sortowania całej listy?
Tak. Po prostu przeszukujesz listę raz i przechowujesz dziesięć najmniejszych liczb. Algorytm będzie miał postać O (n) (właściwie, O (n * 10) worstcase)
Foreach (list)
- Check if current item is smaller than the biggest item in the sorted Array[10]
- If so, put the current item at the right spot (sorted) in the array (insertionsort), bumping away the biggest item.
To, czego potrzebujesz, to kolejka priorytetowa. Wstaw każdy numer do kolejki priorytetowej. Jeśli rozmiar kolejki przekracza 10, usuń najmniejszą (lub największą) wartość. Wartości pozostające w kolejce na końcu to 10 największych (lub najmniejszych).
Jeśli kolejka jest zaimplementowana za pomocą sterty, może to być bardzo skuteczny algorytm.
Możesz zmienić to 10 w stałą opartą na lg, używając sterty dla twojej "listy" 10. :-) – corsiKa
O (n * 10) = O (n). – recursive
rekursywny: kurs, ale to wyjaśnia, że gdy liczba 10 jest wyższa (powiedzmy, że chcesz połowę posortowanej listy), O zmieni się, a prosta tablica nie będzie. Będziesz wtedy potrzebował lepszej bazy danych, takiej jak glowcoder. – Konerak