Метода - сортировка
Cтраница 4
 |
Итоговые характеристики семи основных методов сортировки. Приблизительные результаты для сортировки списка из N элементов. [46] |
Методы сортировки, описанные в главах 1 и 2, не следует использовать, когда надо на глаз выбрать сортировку с целью минимизации или точного прогнозирования производительности. Поэтому в итоговой таблице использованы не точные числа, а их оценки. Таким образом, рис. 2.7 является лишь приблизительным указанием производительности рассмотренных методов. [47]
На самом деле желательно бы иметь более лучшие методы сортировки, которые бы требовали еще меньше времени. Все методы сортировки могут быть отнесены к одному из трех основных типов: ( 1) распределительные сортировки - сортируют путем анализа элементов по одной цифре за раз; ( 2) сравнительные сортировки - сортируют путем сравнения ключевых слов по два за раз и ( 3) сортировки вычислением адреса - преобразуют ключ в адрес, близкий к тому месту, где ожидается окончательное расположение символа. [48]
Здесь же мы не пытаемся охватить даже те из них, которые считаются важными; скорее, мы ограничимся методами, оказавшимися полезными в разработке алгоритмов и в практической их реализации. Рассматриваемые здесь методы сортировки активно используются при разработке алгоритмов во многих разделах данного пособия. Полезно изучить характеристики каждого метода сортировки, чтобы можно было производить разумный выбор для конкретных приложений. К счастью, задача изучения этих алгоритмов не столь уж громоздка. [49]
 |
Три вида алгоритмов сортировки. [50] |
Наша модель сортировки упрощена в нескольких отношениях. Например, некоторые методы сортировки основаны на знании статистического распределения имеющихся ключей или их конкретного представления1); мы не будем пользоваться такими методами. [51]
 |
Сортировка по основанию. [52] |
Применение к таким числам описанного выше метода сортировки называют сортировкой по основанию системы счисления. После трех операций распределяющей сортировки при объединении колод карты окажутся в нужном порядке. При этом существовала опасность того, что колоду карт, например программы, могли по небрежности уронить и в результате нарушить порядок перфокарт в колоде; неудобство состояло в том, что карты должны были пробиваться в строго определенных колонках. [53]
Сортировка методом Шелла выбирается для многих приложений, поскольку она обеспечивает приемлемое время сортировки даже для достаточно больших файлов и реализуется в виде компактной программы, которую легко заставить работать. В следующих главах мы ознакомимся с методами сортировки, которые, возможно, более ют всего лишь в два раза быстрее ( а то и того меньше) при но при этом они существенно сложнее. [54]
Это улучшение приводит к самому лучшему на сегодняшний день методу сортировки массивов, который можно назвать обменной сортировкой с разделением. Он основан на сравнениях и обменах элементов, стоящих на возможно больших расстояниях друг от друга. [55]
Бывает, что программист не рассматривает производительность сортировки как решающий фактор, хотя она и интересует его. Он заинтересован лишь в том, чтобы производительность предлагаемого им метода сортировки находилась бы в определенных пределах. [56]
В отличие от методов обмена, рассмотренных в предыдущих разделах, методы сортировки вставками предполагают перемещение записей из одной позиции в другую, а не взаимный обмен позициями. Поэтому каждое перемещение данных составляет примерно половину работы как по вставке, так и по обмену. Точное различие между функциями обмена и перемещения определяется, конечно, спецификой машины. На машине с быстрой командой пересылки память-память и переменной длиной поля перемещение набора записей вниз списка может быть очень эффективным. [57]
В этом разделе мы воспользуемся удобным случаем, чтобы дать более систематический обзор алгоритмов, представленных в этой главе, раскрывая соответствующие им методы сортировки. [58]
Вертим Пр тта сортирпвки методом Шелл л ( см. рз с Е и, 6) служит еще одним примером не ала п т и много метода сортировки. [59]
Страницы: 1 2 3 4