Я работаю над списком целых чисел из файла. И мне нужно использовать алгоритм сортировки, чтобы классифицировать их в порядке убывания. Я знаком с временем выполнения нескольких алгоритмов сортировки и знаю, что их использование носит ситуативный характер. Итак, мой вопрос: Какой был бы самый быстрый алгоритм сортировки для списка ЛЮБОГО размера, который уже отсортирован на 90%? (в моем файле у меня 10 000 записей, но 9 500 из них уже отсортированы).
Спасибо,
Сортировка вставкой должна быть хорошей, если вы решите кодировать ее самостоятельно, а не использовать функции сортировки, предоставляемые языком.
Представляем реализацию сортировки вставкой в Python.
Программа
def InsertionSort(Array):
Total = 0
for i in xrange(1, len(Array)):
j, I, = i - 1, i
while j >= 0 and Array[I] > Array[j]:
Array[I], Array[j] = Array[j], Array[I]
j, I, Total = j - 1, I - 1, Total + 1
print "Insertion Sort Total Operations :", Total
Вывод
Наихудший случай
TestArray = range(1, 11)
InsertionSort(TestArray)
Insertion Sort Total Operations : 45
Bestcase
TestArray = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
InsertionSort(TestArray)
Insertion Sort Total Operations : 0
90% отсортированный массив
TestArray = [1, 9, 8, 7, 6, 5, 4, 3, 2, 10]
InsertionSort(TestArray)
Insertion Sort Total Operations : 17
Полусортированный массив
TestArray = [10, 9, 8, 7, 6, 1, 2, 3, 4, 5]
InsertionSort(TestArray)
Insertion Sort Total Operations : 10
Алгоритм Timsort, разработанный для Python (и теперь используемый в Java), оптимизирован для работы с частично отсортированные "прогоны" встроены.
Для std :: sort C ++ использует интроспективную сортировку, при которой массив / список сначала сортируется с использованием быстрой сортировки для определенной глубины рекурсии, а затем heapsort. Я не знаю о 90%, но heapsort, похоже, хорошо работает с уже отсортированными массивами / списками ... поэтому я рекомендую вам попробовать это.
