算法：解决问题的方法和步骤
评价算法的好坏：渐近时间复杂度和渐近空间复杂度。
渐近时间复杂度的大O标记：
排序算法（选择、冒泡和归并）和查找算法（顺序和折半）
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
函数：
def select_sort(origin_items, comp=lambda x, y: x < y):
"""简单选择排序"""
items = origin_items[:]
for i in range(len(items) - 1):
min_index = i
for j in range(i + 1, len(items)):
if comp(items[j], items[min_index]):
min_index = j
items[i], items[min_index] = items[min_index], items[i]
return items
选择排序例子：
def select_sort(items):
for i in range(len(items)):
min_index = i
for j in range(i+1,len(items)):
if items[min_index] > items[j]:
min_index = j
items[i],items[min_index] = items[min_index],items[i]
print(‘选择排序后的数组：‘)
for i in range(len(items)):
print(‘%d ‘ %items[i],end=‘ ‘)
def main():
items = [64, 25, 12, 22, 11]
select_sort(items)
if __name__ == ‘__main__‘:
main()
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
函数：
def bubble_sort(origin_items, comp=lambda x, y: x > y):
"""高质量冒泡排序(搅拌排序)"""
items = origin_items[:]
for i in range(len(items) - 1):
swapped = False
for j in range(i, len(items) - 1 - i):
if comp(items[j], items[j + 1]):
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
if swapped:
swapped = False
for j in range(len(items) - 2 - i, i, -1):
if comp(items[j - 1], items[j]):
items[j], items[j - 1] = items[j - 1], items[j]
swapped = True
if not swapped:
break
return items
例子1：
def bubble_sort(items):
n = len(items)
for i in range(n):
for j in range(0,n-i-1):
if items[j] > items[j+1]:
items[j],items[j+1] = items[j+1],items[j]
print(‘冒泡排序后的数组：‘)
for i in range(len(items)):
print(‘%d‘ %items[i],end=‘ ‘)
def main():
items = [64,34,25,12,22,11,90]
bubble_sort(items)
if __name__ == ‘__main__‘:
main()
例子2:
def bubble_sort(origin_items, comp=lambda x, y: x > y):
"""高质量冒泡排序(搅拌排序)"""
items = origin_items[:]
for i in range(len(items) - 1):
swapped = False
for j in range(i, len(items) - 1 - i):
if comp(items[j], items[j + 1]):
items[j], items[j + 1] = items[j + 1], items[j]
swapped = True
if swapped:
swapped = False
for j in range(len(items) - 2 - i, i, -1):
if comp(items[j - 1], items[j]):
items[j], items[j - 1] = items[j - 1], items[j]
swapped = True
if not swapped:
break
return items
def main():
items = [64,34,25,12,22,11,90]
bubble_sort(items)
for i in range(len(items)):
print(‘%d‘ %items[i],end=‘ ‘)
if __name__ == ‘__main__‘:
main()
归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
分治法:
函数：
def merge_sort(items, comp=lambda x, y: x <= y):
"""归并排序(分治法)"""
if len(items) < 2:
return items[:]
mid = len(items) // 2
left = merge_sort(items[:mid], comp)
right = merge_sort(items[mid:], comp)
return merge(left, right, comp)
def merge(items1, items2, comp):
"""合并(将两个有序的列表合并成一个有序的列表)"""
items = []
index, index2 = 0, 0
while index1 < len(items1) and index2 < len(items2):
if comp(items1[index1], items2[index2]):
items.append(items1[index1])
index1 += 1
else:
items.append(items2[index2])
index2 += 1
items += items1[index1:]
items += items2[index2:]
return items
例子：
def merge_sort(items, comp=lambda x, y: x <= y):
"""归并排序(分治法)"""
if len(items) < 2:
return items[:]
mid = len(items) // 2
left = merge_sort(items[:mid], comp)
right = merge_sort(items[mid:], comp)
return merge(left, right, comp)
def merge(items1, items2, comp):
"""合并(将两个有序的列表合并成一个有序的列表)"""
items = []
index1, index2 = 0, 0
while index1 < len(items1) and index2 < len(items2):
if comp(items1[index1], items2[index2]):
items.append(items1[index1])
index1 += 1
else:
items.append(items2[index2])
index2 += 1
items += items1[index1:]
items += items2[index2:]
return items
def main():
items = [64,34,25,12,22,11,90]
merge_sort(items)
for i in range(len(items)):
print(‘%d‘ %items[i],end=‘ ‘)
if __name__ == ‘__main__‘:
main()
例子2：
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r - m
# 创建临时数组
L = [0] * (n1)
R = [0] * (n2)
# 拷贝数据到临时数组 arrays L[] 和 R[]
for i in range(0, n1):
L[i] = arr[l + i]
for j in range(0, n2):
R[j] = arr[m + 1 + j]
# 归并临时数组到 arr[l..r]
i = 0 # 初始化第一个子数组的索引
j = 0 # 初始化第二个子数组的索引
k = l # 初始归并子数组的索引
while i < n1 and j < n2:
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# 拷贝 L[] 的保留元素
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# 拷贝 R[] 的保留元素
while j < n2:
arr[k] = R[j]
j += 1
k += 1
def mergeSort(arr, l, r):
if l < r:
m = int((l + (r - 1)) / 2)
mergeSort(arr, l, m)
mergeSort(arr, m + 1, r)
merge(arr, l, m, r)
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print("给定的数组")
for i in range(n):
print("%d" % arr[i])
mergeSort(arr, 0, n - 1)
print("\n\n排序后的数组")
for i in range(n):
print("%d" % arr[i])
顺序查找指按一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止。
函数：def seq_search(items, key):
"""顺序查找"""
for index, item in enumerate(items):
if item == key:
return index
return -1
例子：
def seq_search(items,n,key):
for i in range(0,n):
if items[i] == key:
return i
return -1
def main():
items = [64,34,25,12,22,11]
key = 22
n = len(items)
result = seq_search(items,n,key)
if result == -1:
print(‘元素不在数组中！‘)
else:
print("元素在数组中的索引为",result)
if __name__ == ‘__main__‘:
main()
二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
函数：
def bin_search(items, key): """折半查找"""
start, end = 0, len(items) - 1
while start <= end:
mid = (start + end) // 2
if key > items[mid]:
start = mid + 1
elif key < items[mid]:
end = mid - 1
else:
return mid
return -1
例子：
# 返回 x 在 arr 中的索引，如果不存在返回 -1
def binarySearch(arr, l, r, x):
# 基本判断
if r >= l:
mid = int(l + (r - l) / 2)
# 元素整好的中间位置
if arr[mid] == x:
return mid
# 元素小于中间位置的元素，只需要再比较左边的元素
elif arr[mid] > x:
return binarySearch(arr, l, mid - 1, x)
# 元素大于中间位置的元素，只需要再比较右边的元素
else:
return binarySearch(arr, mid + 1, r, x)
else:
# 不存在
return -1
def main():
# 测试数组
arr = [2, 3, 4, 10, 40]
x = 10
# 函数调用
result = binarySearch(arr, 0, len(arr) - 1, x)
if result != -1:
print("元素在数组中的索引为 %d" % result)
else:
print("元素不在数组中")
if __name__ == ‘__main__‘:
main()
原文：https://www.cnblogs.com/wen-hai/p/11100485.html