http://wiki.atp-fivt.org/index.php?action=history&feed=atom&title=Quicksort
Quicksort - История изменений
2026-04-11T07:37:54Z
История изменений этой страницы в вики
MediaWiki 1.30.0
http://wiki.atp-fivt.org/index.php?title=Quicksort&diff=390&oldid=prev
Algocourselecturenotes в 14:58, 7 мая 2020
2020-05-07T14:58:12Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="ru">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Версия 14:58, 7 мая 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Быстрая сортировка</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>(std sort)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">== </ins>Быстрая сортировка(std sort) <ins class="diffchange diffchange-inline">==</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
Algocourselecturenotes
http://wiki.atp-fivt.org/index.php?title=Quicksort&diff=389&oldid=prev
Algocourselecturenotes: Новая страница: «Быстрая сортировка (std sort) p p p p (pivot) <p<p<p<p p >p>p>p…»
2020-05-07T14:49:34Z
<p>Новая страница: «Быстрая сортировка (std sort) p p p p (pivot) <p<p<p<p p >p>p>p…»</p>
<p><b>Новая страница</b></p><div>Быстрая сортировка<br />
(std sort)<br />
<br />
<br />
p<br />
<br />
p<br />
p<br />
<br />
p (pivot)<br />
<p<p<p<p p >p>p>p<br />
<br />
<br />
<br />
Пусть выбран p. Как построить разбиение?<br />
Метод 1. (С доп. памятью)<br />
- исх. массив а<br />
C - результат<br />
i<br />
p<br />
<br />
<br />
<br />
а) for (i = 1…n)<br />
Стабильная.<br />
if (a < i) < p)<br />
c.push_back(a(i))<br />
б) for (i = 1…n)<br />
ai = p<br />
в) for (i = 1…n)<br />
ai > p<br />
pppp<br />
<br />
r<br />
r<br />
l<br />
l<br />
c <br />
<br />
<br />
for (I = 1…n)<br />
Не стабильная.<br />
if (a(i) < p): c (l) = a (i), ++ l<br />
if (a(i) > p): c (r) = a (i), -- r<br />
<br />
Метод 2.<br />
i = 1, i = n<br />
while (i < j): <br />
while (i < j && a(i) p) ++i;<br />
while (i < j && a(j) p) -- j;<br />
if (i < j) <br />
swap (a(i), a(j)), ++i, -- j;<br />
swap (a(micl), a(j));<br />
нач. позиция p (в исх. массиве)<br />
i и j находят разделение p и p<br />
<br />
1) Произвольный детерм. выбор ( mid = 1 / micl = n / …)<br />
В худшем случае может работать <br />
<br />
2) Выбор случайного p.<br />
Теорема (б/д). В среднем quick sort со случайным выбором p работает за</div>
Algocourselecturenotes