Что такое устойчивость в сортировке алгоритмов и почему это важно?
Цвета определяются $LS_COLORS переменная среды. В зависимости от Вашего дистрибутива это сгенерировано автоматически, когда оболочка запускается, с помощью ~/.dircolors или /etc/DIR_COLORS.
Редактирование:
Для списка цветных значений используйте этот сценарий:
eval $(echo "no:global default;fi:normal file;di:directory;ln:symbolic link;pi:named pipe;so:socket;do:door;bd:block device;cd:character device;or:orphan symlink;mi:missing file;su:set uid;sg:set gid;tw:sticky other writable;ow:other writable;st:sticky;ex:executable;"|sed -e 's/:/="/g; s/\;/"\n/g')
{
IFS=:
for i in $LS_COLORS
do
echo -e "\e[${i#*=}m$( x=${i%=*}; [ "${!x}" ] && echo "${!x}" || echo "$x" )\e[m"
done
}
5 ответов
Алгоритм сортировки называется стабильным , если два объекта с одинаковыми ключами появляются в отсортированном выводе в том же порядке, что и во входном массиве для сортировки. Некоторые алгоритмы сортировки стабильны по своей природе, такие как сортировка вставкой, сортировка слиянием, пузырьковая сортировка и т. Д. А некоторые алгоритмы сортировки - нет, например, сортировка по куче, быстрая сортировка и т. Д.
Предпосылки : «стабильный» алгоритм сортировки сохраняет элементы с одинаковым ключом сортировки по порядку. Предположим, у нас есть список из 5-буквенных слов:
peach
straw
apple
spork
Если мы отсортируем список только по первой букве каждого слова, то стабильная сортировка выдаст:
apple
peach
straw
spork
В нестабильном алгоритме сортировки, соломинку или spork можно менять местами, но в стабильной они остаются в тех же относительных положениях (то есть
В конце концов, он будет правильно отсортирован. Убедитесь в этом сами. (кстати, этот алгоритм называется поразрядной сортировкой)
Теперь, чтобы ответить на ваш вопрос, предположим, что у нас есть список имен и фамилий. Нас просят отсортировать «по фамилии, потом по первому». Мы можем сначала отсортировать (стабильный или нестабильный) по имени, а затем стабильный отсортировать по фамилии. После этих сортировок список в первую очередь сортируется по фамилии. Однако, если фамилии совпадают, имена сортируются.
Нестабильные сортировки нельзя складывать таким же образом.
Стабильность сортировки означает, что записи с одним и тем же ключом сохраняют свой относительный порядок до и после сортировки.
Таким образом, стабильность имеет значение тогда и только тогда, когда вы решаете проблему требует сохранения этого относительного порядка.
Если вам не нужна стабильность, вы можете использовать быстрый алгоритм с потерей памяти из библиотеки, например, heapsort или quicksort, и забудьте об этом.
Если вам нужна стабильность, все сложнее. Стабильные алгоритмы потребляют больше ресурсов ЦП и / или памяти, чем нестабильные алгоритмы. Поэтому, когда у вас большой набор данных, вам нужно выбирать между нагрузкой на ЦП или память. Если вы ограничены как в процессоре, так и в памяти, у вас проблема. Хорошим компромиссным стабильным алгоритмом является сортировка двоичного дерева; В статье в Википедии есть жалко простая реализация C ++ на основе STL.
Вы можете превратить нестабильный алгоритм в стабильный, добавив исходный номер записи в качестве ключа последнего места для каждой записи. 118275] вам нужно выбирать между нагрузкой на процессор или память. Если вы ограничены как в процессоре, так и в памяти, у вас проблема. Хорошим компромиссным стабильным алгоритмом является сортировка двоичного дерева; В статье в Википедии есть жалко простая реализация C ++ на основе STL.
Вы можете превратить нестабильный алгоритм в стабильный, добавив исходный номер записи в качестве ключа последнего места для каждой записи. 118275] вам нужно выбирать между нагрузкой на процессор или память. Если вы ограничены как в процессоре, так и в памяти, у вас проблема. Хорошим компромиссным стабильным алгоритмом является сортировка двоичного дерева; В статье Википедии есть жалкая простая реализация C ++ на основе STL.
Вы можете превратить нестабильный алгоритм в стабильный, добавив исходный номер записи в качестве ключа последней записи для каждой записи. 118275]
Есть несколько причин, по которым стабильность может быть важна. Во-первых, если две записи не нужно менять местами, поменяв их местами, вы можете вызвать обновление памяти, страница помечается как грязная и ее необходимо перезаписать на диск (или другой медленный носитель).
Это зависит от того, что вы делаете.
Представьте, что у вас есть записи о людях с полями имени и фамилии. Сначала вы сортируете список по имени. Если вы затем отсортируете список с помощью стабильного алгоритма по фамилии, вы получите список, отсортированный по имени И фамилии.
Стабильная сортировка всегда будет возвращать одно и то же решение (перестановку) на одном и том же входе.
Например, [2,1,2] будет отсортировано с использованием стабильной сортировки как перестановки [2,1,3 ] (сначала индекс 2, затем индекс 1, затем индекс 3 в отсортированном выводе). Это означает, что вывод всегда перетасовывается одинаково. Другой нестабильной, но все же правильной перестановкой является [2,3,1].
Быстрая сортировка не является стабильной сортировкой, и различия в перестановках между одними и теми же элементами зависят от алгоритма выбора точки поворота. Некоторые реализации выбирают случайным образом, и это может привести к быстрой сортировке, приводящей к различным перестановкам на одном и том же входе с использованием одного и того же алгоритма.
Алгоритм стабильной сортировки необходим детерминированный.