Какая сортировка алгоритма подходит лучше всего для курорта почти полностью отсортированный список?
Язык Objective C имел "Категории" с начала 1990-х; это по существу то же самое как Методы Расширения.NET. При поиске лучших практик Вы могли бы хотеть видеть что Objective C эмпирических правил (Какао & NeXT), разработчики придумали вокруг них.
Brent Simmons (автор RSS-ридера NetNewsWire для Mac OS X и iPhone) просто отправленный сегодня о его модернизированные правила для использования категорий и было немного обсуждение в сообществе Какао вокруг того сообщения.
3 ответа
Сортировка вставкой хорошо работает с небольшими или почти отсортированными списками.
Из этого Документа ACM :
Тесты на случайно сгенерированных списках различные комбинации длины списка и небольшие коэффициенты сортировки указывают что прямая вставка лучше всего для небольших или почти отсортированных списков и что Quickersort лучше всего в противном случае.
Из вики статьи Сортировка вставкой :
Если входной массив уже отсортирован, сортировка вставкой выполняет всего n-1 сравнения, таким образом делая вставку сортировка более эффективна, если задано отсортировано or "nearly-sorted" arrays.
SO Question: Is there ever a good reason to use Insertion Sort?
Есть доступ к обеим операциям поиска? Если да, вы можете построить некоторое хэш-дерево во время первого процесса сортировки и использовать его для других операций сортировки
Как я понял, ваш список данных уже отсортирован (скажем, по порядку кодировки ascii / страны), но без некоторых правил словаря, применяемых для конкретной страны. Например, Германия и их умляуты
см. Germanic_umlaut в википедии
, вы не вставляете новые элементы, вы просто хотите применить к ним более строгие правила сортировки.
как вы можете прочитать, например, здесь
http://www.softpanorama.org/Algorithms/Sorting/bubblesort.shtml
пузырьковая сортировка хорошо работает для уже отсортированных списков всего с несколькими перестановками. Похоже, пузырьковая сортировка - хороший алгоритм для начала. Также обратите внимание, что пузырьковая сортировка - это «стабильный» алгоритм сортировки. Это может быть важно для вашего сценария.