0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Алгоритм быстрой сортировки, как и алгоритм слиянием, относят к алгоритмам "разделяй и властвуй". Однако в отличие от последнего он не требует дополнительной памяти и чрезвычайно эффективен при правильной конфигурации. Давайте рассмотрим особенности его работы и реализации.</p>
1
<p>Алгоритм быстрой сортировки, как и алгоритм слиянием, относят к алгоритмам "разделяй и властвуй". Однако в отличие от последнего он не требует дополнительной памяти и чрезвычайно эффективен при правильной конфигурации. Давайте рассмотрим особенности его работы и реализации.</p>
2
<h2>Описание алгоритма</h2>
2
<h2>Описание алгоритма</h2>
3
<p>Быстрая сортировка начинается при разбиении списка (массива) и выборе одного из элементов списка в качестве опорного. Далее остальные элементы передвигаются таким образом, чтобы опорный элемент встал на своё место. Причём те элементы, которые меньше его, перемещаются влево, а те, которые больше либо равны, - вправо.</p>
3
<p>Быстрая сортировка начинается при разбиении списка (массива) и выборе одного из элементов списка в качестве опорного. Далее остальные элементы передвигаются таким образом, чтобы опорный элемент встал на своё место. Причём те элементы, которые меньше его, перемещаются влево, а те, которые больше либо равны, - вправо.</p>
4
<h2>Реализация алгоритма быстрой сортировки</h2>
4
<h2>Реализация алгоритма быстрой сортировки</h2>
5
<p>Есть множество вариаций данного метода. Рассмотрим способ разбиения массива, соответствующий схеме Хоара, - создателя алгоритма быстрой сортировки.</p>
5
<p>Есть множество вариаций данного метода. Рассмотрим способ разбиения массива, соответствующий схеме Хоара, - создателя алгоритма быстрой сортировки.</p>
6
def partition(nums, low, high): # В качестве опорного выбирается средний элемент # В качестве опорного возможен выбор первого, последнего # либо произвольного элемента pivot = nums[(low + high) // 2] i = low - 1 j = high + 1 while True: i += 1 while nums[i] < pivot: i += 1 j -= 1 while nums[j] > pivot: j -= 1 if i >= j: return j # Когда элемент с индексом i (слева от опорного) больше, чем # элемент с индексом j (справа от опорного), мы меняем элементы местами nums[i], nums[j] = nums[j], nums[i] def quick_sort(nums): # Создаём вспомогательную функцию, вызываемую рекурсивно def _quick_sort(items, low, high): if low < high: split_index = partition(items, low, high) _quick_sort(items, low, split_index) _quick_sort(items, split_index + 1, high) _quick_sort(nums, 0, len(nums) - 1) # Проверка, что всё работает random_list_of_nums = [22, 5, 1, 18, 99] quick_sort(random_list_of_nums) print(random_list_of_nums)<h2>Время выполнения алгоритма</h2>
6
def partition(nums, low, high): # В качестве опорного выбирается средний элемент # В качестве опорного возможен выбор первого, последнего # либо произвольного элемента pivot = nums[(low + high) // 2] i = low - 1 j = high + 1 while True: i += 1 while nums[i] < pivot: i += 1 j -= 1 while nums[j] > pivot: j -= 1 if i >= j: return j # Когда элемент с индексом i (слева от опорного) больше, чем # элемент с индексом j (справа от опорного), мы меняем элементы местами nums[i], nums[j] = nums[j], nums[i] def quick_sort(nums): # Создаём вспомогательную функцию, вызываемую рекурсивно def _quick_sort(items, low, high): if low < high: split_index = partition(items, low, high) _quick_sort(items, low, split_index) _quick_sort(items, split_index + 1, high) _quick_sort(nums, 0, len(nums) - 1) # Проверка, что всё работает random_list_of_nums = [22, 5, 1, 18, 99] quick_sort(random_list_of_nums) print(random_list_of_nums)<h2>Время выполнения алгоритма</h2>
7
<p>Как правило, время выполнения составляет O(n log n).</p>
7
<p>Как правило, время выполнения составляет O(n log n).</p>
8
<p><strong>Примечание</strong>: алгоритм быстрой сортировки станет работать медленно, если опорный элемент будет равен наименьшему либо наибольшему элементу списка (массива).</p>
8
<p><strong>Примечание</strong>: алгоритм быстрой сортировки станет работать медленно, если опорный элемент будет равен наименьшему либо наибольшему элементу списка (массива).</p>
9
<p><a>Источник</a></p>
9
<p><a>Источник</a></p>
10
10