![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Использование связанного списка для хранения информации о промежуточных максимумах.Стр 1 из 5Следующая ⇒
Сортировка посредством выбора.
{сортировка выбором, пример 1} procedure Selekt (var item: DataArray; count: integer); Var i, j, k: integer; x: DataItem; Begin for i: = i to count-1 do Begin k: = i; x: = item[i]; for j: = i+1 to count do { найти элемент с наименьшим значением } if item[j]< x then Begin k: = j; x: = item[j]; end; item[k]: = item[i]; { обмен } item[i]: = x; end; end; Идея метода довольно проста: найти наибольший элемент файла и поставить его на место N, найти следующий максимум и поставить его на место N-1 и т.д. до 2-го элемента. Схема алгоритма имеет следующий вид.
{сортировка выбором, пример 2} for i: =1 to n-1 do Begin k: =i; max: =a[i]; for j: =i+1 to n do if a[j]> max then Begin max: =a[j]; k: =j; end; A[k]: =a[i]; a[i]: =max; end; Время работы алгоритма t примерно оценивается формулой: Использование связанного списка для хранения информации о промежуточных максимумах. В приведенном выше алгоритме максимум среди K[1]... K[j-1] определяется в цикле от j-1 до 1 c целью обеспечить меньшее число обменов в случае равенства ключей и сохранении прежнего порядка равных элементов. Однако, если изменить порядок просмотра элементов на противоположный и изменить структуру данных, введя дополнительные указатели, можно примерно в два раза сократить число повторений в цикле поиска максимума. Каждый ключ K[i] снабжается указателем L[i] на элемент, максимальный среди первых i-1 элементов так, как показано ниже. Тогда после обмена элементов K[j] и K[m] поиск максимума в следующем цикле по j можно осуществлять среди элементов K[L[m]]... K[j] при начальных значениях X=K[L[m]], m=L[m], т.к. максимум может " обновиться" только за счет элементов, лежащих правее локального максимума. Таким образом среднее количество просматриваемых при поиске максимума элементов сокращается примерно в два раза. Модифицированный алгоритм имеет следующий вид. Время работы алгоритма t примерно оценивается формулой:
|