Источник статьи: Структуры данных и алгоритмы (Python)
#сортировать и искать
Алгоритм сортировки — это алгоритм, который упорядочивает строку данных в определенном порядке.
№ 1. Пузырьковая сортировка
**Пузырьковая сортировка** — это простой алгоритм сортировки. Он перебирает последовательность для сортировки, сравнивая два элемента за раз и меняя их местами, если они находятся в неправильном порядке. Работа по обходу последовательности состоит в том, чтобы повторяться до тех пор, пока перестановки не понадобятся, то есть последовательность не будет отсортирована. Название этого алгоритма происходит от того факта, что меньшие элементы медленно «вплавляются» в верхнюю часть последовательности путем замены.
Алгоритм пузырьковой сортировки работает следующим образом:
- Сравните соседние элементы. Если первое больше второго (в порядке возрастания), поменяйте их местами.
- Сделайте то же самое для каждой пары соседних элементов, от первой пары в начале до последней пары в конце. После этого шага последний элемент будет самым большим числом.
- Повторите вышеуказанные шаги для всех элементов, кроме последнего.
- Продолжайте повторять описанные выше шаги для все меньшего и меньшего количества элементов каждый раз, пока не останется пар чисел для сравнения. ##Анализ пузырьковой сортировки
Иллюстрация процесса обмена (впервые):
Затем нам нужно выполнить n-1 процессов барботирования, и количество сравнений, соответствующее каждому времени, показано на следующем рисунке:
def bubble_sort(alist):
for j in range(len(alist)-1,0,-1):
# j表示每次遍历需要比较的次数，是逐渐减小的
for i in range(j):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
print(li)
##время сложности
- Оптимальная временная сложность: O(n) (указывает, что нет элементов, которые можно было бы обменять после однократного обхода, и сортировка заканчивается.)
- Наихудшая временная сложность: O(n2)
- Стабильность: стабильная
##Демонстрация пузырьковой сортировки Эффект:
№ 2. Сортировка выбором Сортировка выбором — это простой и интуитивно понятный алгоритм сортировки. Это работает следующим образом. Сначала найдите наименьший (самый большой) элемент в несортированной последовательности, сохраните его в начале отсортированной последовательности, затем продолжайте находить наименьший (самый большой) элемент из оставшихся несортированных элементов и поместите его в конец отсортированной последовательности. И так до тех пор, пока все элементы не будут отсортированы.
Основное преимущество сортировки выбором связано с перемещением данных. Если элемент находится в правильном конечном положении, он не будет перемещен. Каждый раз, когда сортировка выбором меняет местами пару элементов, по крайней мере один из них будет перемещен в его конечную позицию, поэтому сортировка таблицы из n элементов требует в общей сложности не более n-1 перестановок. Из всех методов сортировки, которые полностью полагаются на обмен для перемещения элементов, сортировка выбором является очень хорошей.
##Анализ сортировки выбором Процесс сортировки:
def selection_sort(alist):
n = len(alist)
# 需要进行n-1次选择操作
for i in range(n-1):
# 记录最小位置
min_index = i
# 从i+1位置到末尾选择出最小数据
for j in range(i+1, n):
if alist[j] < alist[min_index]:
min_index = j
# 如果选择出的数据不在正确位置，进行交换
if min_index != i:
alist[i], alist[min_index] = alist[min_index], alist[i]
alist = [54,226,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)
##время сложности
- Оптимальная временная сложность: O(n2)
- Наихудшая временная сложность: O(n2)
- Стабильность: нестабильная (рассмотрим случай, когда каждый раз выбирается наибольшее значение в порядке возрастания) ##Демонстрация сортировки выбором
№ 3. Сортировка вставками
Сортировка вставками — это простой и интуитивно понятный алгоритм сортировки. Он работает, создавая упорядоченную последовательность, и для несортированных данных сканирует назад и вперед в отсортированной последовательности, находит соответствующую позицию и вставляет ее. При реализации сортировки вставками в процессе сканирования сзади наперед необходимо многократно шаг за шагом перемещать отсортированные элементы на задний план, чтобы обеспечить место для вставки самого последнего элемента.
##Анализ сортировки вставками
def insert_sort(alist):
# 从第二个位置，即下标为1的元素开始向前插入
for i in range(1, len(alist)):
# 从第i个元素开始向前比较，如果小于前一个元素，交换位置
for j in range(i, 0, -1):
if alist[j] < alist[j-1]:
alist[j], alist[j-1] = alist[j-1], alist[j]
alist = [54,26,93,17,77,31,44,55,20]
insert_sort(alist)
print(alist)
##время сложности
- Оптимальная временная сложность: O(n) (в порядке возрастания последовательность уже находится в порядке возрастания)
- Наихудшая временная сложность: O(n2)
- Стабильность: стабильная ##Демонстрация сортировки вставками
№ 4. Быстрая сортировка
Быстрая сортировка (англ. Quicksort), также известная как сортировка с обменом разделами (partition-exchange sort), делит данные, подлежащие сортировке, на две независимые части за один проход, и все данные в одной части меньше, чем все данные в другая часть. , а затем используйте этот метод для быстрой сортировки двух частей данных соответственно, и весь процесс сортировки может выполняться рекурсивно, так что все данные становятся упорядоченной последовательностью.
Шаги:
1. Выберите элемент из последовательности, называемый «стержнем». 2. Переупорядочить последовательность.Все элементы, меньшие эталонного значения, помещаются перед эталонным значением, а все элементы, превышающие эталонное значение, помещаются в конце эталонного значения (одно и то же число может идти с любой стороны). После того, как этот раздел заканчивается, эталон находится в середине последовательности. Это называется операцией разделения. Рекурсивно отсортируйте подмассивы элементов меньше эталонного значения и подмассивы элементов больше эталонного значения. 3. Нижний случай рекурсии — размер последовательности равен нулю или единице, то есть она всегда была отсортирована. Хотя он продолжает повторяться, алгоритм всегда будет заканчиваться, потому что на каждой итерации он помещает хотя бы один элемент в свою последнюю позицию.
##Быстрый анализ сортировки
def quick_sort(alist, start, end):
"""快速排序"""
# 递归的退出条件
if start >= end:
return
# 设定起始元素为要寻找位置的基准元素
mid = alist[start]
# low为序列左边的由左向右移动的游标
low = start
# high为序列右边的由右向左移动的游标
high = end
while low < high:
# 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
while low < high and alist[high] >= mid:
high -= 1
# 将high指向的元素放到low的位置上
alist[low] = alist[high]
# 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
while low < high and alist[low] < mid:
low += 1
# 将low指向的元素放到high的位置上
alist[high] = alist[low]
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
# 将基准元素放到该位置
alist[low] = mid
# 对基准元素左边的子序列进行快速排序
quick_sort(alist, start, low-1)
# 对基准元素右边的子序列进行快速排序
quick_sort(alist, low+1, end)
alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)
##время сложности
- Оптимальная временная сложность: O(nlogn)
- Наихудшая временная сложность: O(n2)
- Стабильность: Нестабильный Не очевидно, что быстрая сортировка занимает в среднем O(n log n) времени с самого начала. Но нетрудно наблюдать за операцией разбиения, элементы массива посещаются один раз в каждом цикле, используя время O(n). В версии с конкатенацией эта операция также O(n).
В лучшем случае каждый раз, когда мы запускаем партицию, мы делим массив на две почти равные части. Это означает, что каждый рекурсивный вызов обрабатывает массив вдвое меньшего размера. Следовательно, нам нужно только сделать log n вложенных вызовов, прежде чем будет достигнут массив размером один. Это означает, что глубина дерева вызовов равна O(log n). Но в двух вызовах программы одной и той же иерархии одна и та же часть исходной последовательности не обрабатывается, поэтому каждая иерархия вызовов программы в сумме занимает только O(n) времени (каждый вызов имеет некоторую общую дополнительную стоимость, но поскольку существуют только O(n) вызовов на иерархию, они суммируются в коэффициентах O(n)). В результате этот алгоритм занимает всего O(n log n) времени.
##Демонстрация быстрой сортировки
№ 5. Сортировка холмов Сортировка Шелла — это тип сортировки вставками. Также известная как инкрементная сортировка с сокращением, это более эффективная и улучшенная версия алгоритма прямой сортировки вставками. Сортировка по Хиллу — неустойчивый алгоритм сортировки. Этот метод обусловлен DL. Shell была названа в честь того, что была предложена в 1959 году. Сортировка по холму состоит в том, чтобы группировать записи по определенному приращению индекса и использовать алгоритм сортировки с прямым вставкой для сортировки каждой группы, по мере постепенного уменьшения приращения каждая группа содержит все больше и больше ключевых слов. весь файл просто группируется, и алгоритм завершается.
##Процесс сортировки холмов
Основная идея сортировки Хилла: перечислите массивы в таблице и вставьте столбцы отдельно, повторите этот процесс, но каждый раз используйте более длинные столбцы (размер шага больше, количество столбцов меньше) для выполнения. Наконец, вся таблица имеет только один столбец. Преобразование массива в таблицу нужно для лучшего понимания алгоритма, который сам по-прежнему использует массив для сортировки.
Например, если задан набор чисел [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ], если мы начнем сортировку с шагом 5, мы сможем лучше описать алгоритмы в таблицах, поэтому они должны выглядеть так (вертикальные элементы — это ступени):
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Затем мы сортируем каждый столбец:
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
При последовательном соединении вышеуказанных четырех строк чисел получаем:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. На данный момент 10 перемещено в правильное положение, а затем выполняется сортировка с шагом 3:
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
После сортировки получается:
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
Наконец, отсортируйте по 1 шагу (это простая сортировка вставками)
##Анализ сортировки по холмам
def shell_sort(alist):
n = len(alist)
# 初始步长
gap = n / 2
while gap > 0:
# 按步长进行插入排序
for i in range(gap, n):
j = i
# 插入排序
while j>=gap and alist[j-gap] > alist[j]:
alist[j-gap], alist[j] = alist[j], alist[j-gap]
j -= gap
# 得到新的步长
gap = gap / 2
alist = [54,26,93,17,77,31,44,55,20]
shell_sort(alist)
print(alist)
##время сложности
Оптимальная временная сложность: варьируется в зависимости от последовательности шагов Наихудшая временная сложность: O(n2) Стабильная мысль: нестабильная ## Демонстрация сортировки по холму
№ 6. Сортировка слиянием Сортировка слиянием — очень типичное применение метода «разделяй и властвуй». Идея сортировки слиянием состоит в том, чтобы сначала рекурсивно разложить массив, а затем объединить массив.
После разложения массива на наименьший и последующего слияния двух упорядоченных массивов основная идея состоит в том, чтобы сравнить первое число двух массивов, в зависимости от того, что меньше, и соответствующий указатель перемещается на один бит назад. Затем сравните, пока один массив не станет пустым, и, наконец, скопируйте остальную часть другого массива.
## Анализ сортировки слиянием
def merge_sort(alist):
if len(alist) <= 1:
return alist
# 二分分解
num = len(alist)/2
left = merge_sort(alist[:num])
right = merge_sort(alist[num:])
# 合并
return merge(left,right)
def merge(left, right):
'''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
#left与right的下标指针
l, r = 0, 0
result = []
while l<len(left) and r<len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
return result
alist = [54,26,93,17,77,31,44,55,20]
sorted_alist = mergeSort(alist)
print(sorted_alist)
##время сложности
- Оптимальная временная сложность: O(nlogn)
- Наихудшая временная сложность: O(nlogn)
- Стабильность: стабильная
№ 7. Сравнение эффективности распространенных алгоритмов сортировки
№ 8. Поиск
Поиск — это алгоритмический процесс поиска определенного элемента в наборе элементов. Поиск обычно дает ответ «истина» или «ложь», поскольку элемент существует. Несколько распространенных методов поиска: последовательный поиск, бинарный поиск, поиск по бинарному дереву, поиск по хэшу.
бинарный поиск
Двоичный поиск, также известный как половинный поиск, имеет преимущества меньшего количества сравнений, высокой скорости поиска и хорошей средней производительности; его недостаток состоит в том, что таблица, в которой нужно искать, должна быть упорядоченной таблицей, а вставка и удаление затруднены. Поэтому половинный метод поиска подходит для редко меняющихся, но часто просматриваемых упорядоченных списков. Сначала, предполагая, что элементы в таблице расположены в порядке возрастания, сравните ключевые слова, записанные в середине таблицы, с ключевыми словами поиска.Если они равны, поиск успешен, в противном случае таблица делится на две подгруппы. -таблицы до и после использования записи средней позиции.Если ключ, записанный в средней позиции, больше ключа поиска, то выполняется дальнейший поиск в предыдущей подтаблице, в противном случае - во второй подтаблице. Описанный выше процесс повторяется до тех пор, пока не будет найдена запись, удовлетворяющая условию, и поиск будет успешным, или пока подтаблица не будет существовать, а поиск в это время не увенчается успехом.
## реализация бинарного поиска
## (нерекурсивная реализация)
def binary_search(alist, item):
first = 0
last = len(alist)-1
while first<=last:
midpoint = (first + last)/2
if alist[midpoint] == item:
return True
elif item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))
## (рекурсивная реализация)
def binary_search(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist)//2
if alist[midpoint]==item:
return True
else:
if item<alist[midpoint]:
return binary_search(alist[:midpoint],item)
else:
return binary_search(alist[midpoint+1:],item)
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))
##время сложности
- Оптимальная временная сложность: O(1)
- Наихудшая временная сложность: O(logn)