КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Сортировки слиянием
Begin End Begin Begin Begin Repeat Begin Var Быстрая сортировка Хоара Дополнительно о сортировках Begin Begin Begin Begin Begin Whiletrue do Begin Var Сортировка Шелла Begin Begin Begin Begin Repeat Begin Var j,k,L,R: integer; x,y: single; nMove:=0; nCompare:=0;
L:=2; R:=nCurr; k:=nCurr;
for j:=R downto L do x:=A[j-1]; y:=A[j]; nMove:=nMove+2; nCompare:=nCompare+1;
if x>y then A[j-1]:=y; A[j]:=x; k:=j; nMove:=nMove+2; end; end;
L:=k+1;
for j:=L to R do x:=A[j-1]; y:=A[j]; nMove:=nMove+2; nCompare:=nCompare+1;
if x>y then A[j-1]:=y; A[j]:=x; k:=j; nMove:=nMove+2; end; end;
R:=k-1;
until L>R; end;
procedure ShellSort; i, j, k, L, m, nSteps: integer; x: Single; mSteps: array of integer; nSteps:= 1; i:= 1; SetLength(mSteps, nSteps); mSteps[nSteps - 1]:= i;
i:= 3 * i + 1; if 3 * i >= nCurr then break; Inc(nSteps); SetLength(mSteps, nSteps); mSteps[nSteps - 1]:= i; end;
nCompare:= 0; nMove:= 0;
for m:= nSteps downto 1 do k:= mSteps[m - 1];
for L:= 1 to k do i:= L + k;
while i <= nCurr do x:= A[i]; Inc(nMove);
j:= i; while (j > k) and (x < A[j - k]) do Inc(nCompare); A[j]:= A[j - k]; Inc(nMove, 2); j:= j - k; end;
if j > k then Inc( nCompare);
A[j]:= x; Inc(nMove);
i:= i + k; end; end; end; end;
Далее будет рассмотрено несколько видов сортировок, которые работают статистически быстрее всех ранее изученных. Слово «статистически» означает, что быстрота наблюдается в большинстве случаев заполнения массивов случайными значениями. Однако в некоторых, редких, т.н. вырожденных случаях, быстрые сортировки могут утратить свою скорость. Примером вырождения можно считать расположение элементов массива в порядке, обратном требуемому.
procedure QuickSort; procedure InnerSort(L,R: integer); i,j: integer; x,y,z: single; i:=L; j:=R; y:=A[(L+R) div 2]; nMove:=nMove+1;
x:=A[i]; nMove:=nMove+1;
nCompare:=nCompare+1; while x<y do nCompare:=nCompare+1; i:=i+1; x:=A[i]; nMove:=nMove+1; end;
z:=A[j]; nMove:=nMove+1;
nCompare:=nCompare+1; while y<z do nCompare:=nCompare+1; j:=j-1; z:=A[j]; nMove:=nMove+1; end;
if i<=j then
A[i]:=z; A[j]:=x; nMove:=nMove+2; inc(i); dec(j); until i>j;
if L<j then InnerSort(L,j); if i<R then InnerSort(i,R);
end; // InnerSort
nMove:=0; nCompare:=0;
InnerSort(1,nCurr); end;
Эта группа сортировок не подвержена вырождению. Скорость работы практически такая же, как у сортировки Хоара. Есть некоторый недостаток: для хранения сортируемых массивов требуется вдвое больше памяти, чем у сортировки Хоара. Элементы, требующие упорядочения (по возрастанию) занимают в массиве A, как и прежде, места с 1-е по nCurr-е. Следующие nCurr мест зарезервированы под временное хранение данных.
Сортировка простым слиянием
Идея сортировки состоит в следующем. Сортируемый массив из элементов делится пополам (ясно, что это имеет смысл при ). Каждая из его половин сортируется, затем две отсортированные половины «сливаются», образуя отсортированное целое. Фрагмент процедуры, выполняющей такую сортировку, может выглядеть так:
i:=1; // Место, с которого начинается левая половина q:= (n+1) div 2; j:=q+1; // Место, с которого начинается правая половина k:= nCurr; // Место, после которого временно помещается «слитый массив»
СортировкаЛевойПоловины; СортировкаПравойПоловины;
while (i<=q) and (j<=n) do // Цикл выполняется, пока обе половины ещё не иссякли
Дата добавления: 2014-01-04; Просмотров: 212; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |