查找
二分查找
import time
def binary_find(test_list, value): #迭代法
start_time = time.time()
low = 0
high = len(test_list) - 1
while low <= high:
mid = (low + high) // 2
if test_list[mid] == value:
print("binary find cost time:", time.time() - start_time)
return 1
if test_list[mid] < value:
low = mid + 1
else:
high = mid - 1
def recur_find(test_list, value): #递归法
start_time = time.time()
low = 0
high = len(test_list) - 1
mid = (low + high) // 2
if test_list[mid] == value:
print("recursion find cost time:", time.time() - start_time)
return 1
if test_list[mid] < value:
recur_find(test_list[mid+1:], value)
else:
recur_find(test_list[:mid+1], value)
test_list = []
for each in range(9999999):
test_list.append(each)
binary_return = binary_find(test_list, 166)
recur_return = recur_find(test_list, 166)
排序
对于排序来说，首先最简单同时也是效率最低的三个就是冒泡、选择和插入，其中冒泡是最简单和实用的，时间复杂度都是n^2级；然后快排、堆排和归并平均时间复杂度都是nlogn级，所以相对较快，而快排是这三个里最简单的，也是用的最多的排序，但一般情况下这三者快慢程度为：快排>归并>堆排，其中快排在极端下效率低，归并需要额外的内存开销，堆排相对较慢，而且复杂，但堆排也是最稳定的，不会因为极端情况而导致效率反差大。
冒泡排序
（顾名思义，就是从下往上，两个两个相邻的相比，小的就上去，大的就不变，比如把5,3,2,1,6,4,7从小到大排序，那么就5比3大，所以5和3对调，接着5和2相邻，5比2大，又和2对调，一直到6，比6小，所以第一轮排序后结果为：3,2,1,5,6,4,7）
import random
def bubble_sort(li):
for i in range(len(li) - 1):
for each in range(len(li) - i - 1): #每一轮结束就有一个数已经排好，所以i轮可以减去多余的i
if li[each] > li[each + 1]:
li[each], li[each + 1] = li[each + 1], li[each] #相邻两个交换
def bubble_sort_plus(li): #对上面算法的优化
for i in range(len(li) - 1):
exchange = False #判断是否本轮交换过，没交换说明已经排序完成
for each in range(len(li) - i - 1):
if li[each] > li[each + 1]:
li[each], li[each + 1] = li[each + 1], li[each]
exchange = True
if not exchange:
break #排序已完成，直接退出，减少多余无用排序
li = list(range(1000))
li2 = li.copy()
random.shuffle(li) #打乱列表
bubble_sort_plus(li)
print(li == li2)
选择排序
（每一轮找出最小的数，放在第一位）
import random
def select_sort(li):
for i in range(len(li) - 1):
min_li = i
for j in range(i+1, len(li)):
#因为range范围里最大值是len(li)-1，所以这里要到len(li)，也就是在i+1到999之间的值比较
#外面一层的for-1是因为最后一轮已经没必要了
if li[j] < li[min_li]:
min_li = j
li[i], li[min_li] = li[min_li], li[i]
print(li)
li = []
for each in range(1000):
li.append(each)
random.shuffle(li)
print(li)
select_sort(li)
插入排序
（就是有一个有序区和无序区，依次把无序区的放到有序区对应位置里，类似打牌的时候那种感觉，一开始有一张牌，放手上，然后抽一张牌，然后比前一张大就放其左边，否则右边，依次循环，这里手上的牌就是有序区，抽牌的地方就是无序区）
import random
def insert_sort(li):
for i in range(1, len(li)): # 第一个元素默认为有序区，每次遍历开始时，当前位置的左边都为有序区，右边为无序区
j = i
while (j - 1) >= 0 and li[j] < li[j - 1]: # 当前元素当比左边的小时，则交换位置，并继续往前找，直到合适的位置停止
li[j - 1], li[j] = li[j], li[j - 1]
j -= 1
li = []
for each in range(1000):
li.append(each)
random.shuffle(li)
print(li)
insert_sort(li)
print(li)
另一种写法
import random
def insert_sort(li):
li_temp = [li.pop(0)] #分一个新区用来插入数据并排序
for each in li:
for j in range(len(li)-1):
if each <= li_temp[j]: #遍历到比新数据小的位置则插入
li_temp.insert(j, each)
break
elif j >= len(li_temp)-1: #当超出新区长度时则说明遍历完成，直接在尾部插入
li_temp.append(each)
break
print(li_temp)
li = []
for each in range(100):
li.append(each)
random.shuffle(li)
print(li)
insert_sort(li)
快速排序
（取最左边的数，然后一轮下来要求左边的数都比他小，右边的都比他大，每轮开始时先在头尾都有一个指针，因为取了最左边的数A，所以第一个位置是空的，然后看右边的指针指向的数是否比取出来的那个数A小，小的话就把这数移到那个空位去，否则右边的指针往左移一位，继续比较是否小于A；然后如果右边的数移到了左边那个空位，那么右边那个位置就空了，此时就判断左边的指针是否大于数A，大于就移到那个空位去，否则左边的指针往右移一位，继续比较是否大于A，两边一直循环操作，直到两边指针指到一个地方，就完成一轮遍历）
import random
def quick_sort(li, left, right):
if left < right:
mid = partition(li, left, right)
quick_sort(li, left, mid - 1) #左右分别递归快排
quick_sort(li, mid + 1, right)
def partition(li, left, right):
temp = li[left] #先取出最左边的数，然后最左边空了
while left < right:
while li[right] >= temp and left < right:
#如果右边的数比取出的数大就指针往左移一位，还要判断left<right是为了防止左移过头了
right -= 1
li[left] = li[right] #比取出的数大，然后放到空位上
while li[left] <= temp and left < right:
left += 1
li[right] = li[left]
li[left] = temp #此时right和left指在一起，然后把取出的数放这里
return left
li = []
for each in range(1000):
li.append(each)
random.shuffle(li)
print(li)
quick_sort(li, 0, len(li) - 1)
print(li)
堆排序
（首先建一个堆，需为完全二叉树，然后要是一个大顶堆，即根节点的值要比子节点的大，比如下面这个，a就要比b、c大，b要比d、e大，那么根节点就是这里面的最大值，于是将其取出，此时顶点就空了，然后把堆的最后一个节点放到堆顶，比如这里是g，然后判断其是否比两个子节点大，如果是则g是最大值，把g取出，否则比较b和c谁大，大的和g换位置，假如b大，那么g和b对调，接着g再和子节点比较，假如比d小，那么d和g再换位置，就这样循环确定位置，然后最大的再取出，一直这样循环取出最大值即完成排序）
a
/ \
b c
/ \ / \
d e f g
注：
将上面的堆按从上到下顺序存入数组当中，比如上面的就是abcdefg（地址从0开始），那么可以发现每个父节点和左子节点的关系是2n+1，和右子节点关系是2n+2
import random
def heap_sort(li):
n = len(li)
# 建堆（大顶堆）
for i in range(((n >> 1) - 1), -1, -1):
siftdown(li, i, n - 1)
# 每次把当前堆的最大值移到末尾，然后堆大小-1，并让堆顶元素下溢
while n > 0:
n -= 1
li[0], li[n] = li[n], li[0]
siftdown(li, 0, n)
def siftdown(li, low, high):
while low < high:
# 左子节点
lc = low * 2 + 1
if lc >= high:
break
# 找到最大的子节点
if lc + 1 < high and li[lc] < li[lc + 1]:
lc += 1
# 拿子节点和父节点进行比较
if li[lc] > li[low]:
li[lc], li[low] = li[low], li[lc]
low = lc
else:
break
a = [i for i in range(100)]
b = a.copy()
random.shuffle(a)
heap_sort(a)
print(a == b)
归并排序
（该排序主要用于整个数组分为两个有序数组时，比如：1,3,4,5,2,6,7,8，那么前四个和后四个都是有序数组，此时就通过将建立两个指针，分别在这两个有序数组开头，然后进行对比，那个小就先把那个加入数组，比如最开始两个指针（A、B）分别指向1和2，然后比较，发现1小，所以1进入数组，指针A往右移动到3,3比2大，然后2进入数组，指针B指到6，…以此类推，最终可能有一边会有剩下的，但都排好序了，所以直接加进去即可），先参考下面代码，了解基本原理：
简单归并示例
import random
def merge(li, low, mid, high):
i = low #指向第一个数组开头
j = mid + 1 #指向第二个数组开头
temp = []
while i <= mid and j <= high: #两个数组都没排完序加入数组
if li[i] <= li[j]: #哪个小，哪个加入数组，然后指针往右一位
temp.append(li[i])
i += 1
else:
temp.append(li[j])
j += 1
while i <= mid: #前面当有一个数组拍完序就到这里了，接下来如果是左边数组没排完，就依次加进数组
temp.append(li[i])
i += 1
while j <= high: #如果是右边数组没排完...
temp.append(li[j])
j += 1
return temp
li = [1,2,5,7,3,4,8,9] #前、后四个分别都是排好序的
print(li)
for each in range(len(li)):
if li[each+1] > li[each]: #当后一个比前一个大，即递增
mid = each + 1 #找到第一个递增数组的最后一个数位置
continue
else:
break
li = merge(li, 0, mid, len(li)-1) #中间位置指针就指向第四个，也就是第二个有序数组的前一位
print(li)
另一种写法：
import random
def merge_sort(left, right):
divide(left, right)
def divide(left, right):
if right - left < 2: # 只有一个元素的时候不用拆分
return
mid = (left + right) // 2
divide(left, mid) # 左边拆分
divide(mid, right) # 右边拆分
merge(left, mid, right) # 合并
def merge(left, mid, right):
pl, pr = left, mid # 合并数组左/右边一半起始位置
t = li[left: mid+1] # 拷贝数组的左边一半
ti = 0 # 拷贝数组比较的索引
while ti < len(t) - 1:
if pr < right and t[ti] > li[pr]:
# 如果右边没有走到尽头并且右边的值小，则存入右边的数据
li[pl] = li[pr]
pr += 1
else:
# 如果右边已经存完了，或者右边的数据大，则存左边的
li[pl] = t[ti]
ti += 1
pl += 1
li = []
for each in range(1000):
li.append(each)
random.shuffle(li)
print(li)
merge_sort(0, len(li))
print(li)
归并算法实例
（上面的是归并基本思想，但实际上一般不会刚好出现由2个有序数组组成的情况，所以真正的归并算法原理应该是这样：将数组不断对半拆分，直至两个时就是最小的数组的，然后再排序，2个之间排好，然后合并成4个，再4个之间排好，一直合并到整个即可，过程当中就都是两边都是有序数组的情况了）
import random
def merge(li, low, mid, high):
i = low #指向第一个数组开头
j = mid + 1 #指向第二个数组开头
temp = []
while i <= mid and j <= high: #两个数组都没排完序加入数组
if li[i] <= li[j]: #哪个小，哪个加入数组，然后指针往右一位
temp.append(li[i])
i += 1
else:
temp.append(li[j])
j += 1
while i <= mid: #前面当有一个数组拍完序就到这里了，接下来如果是左边数组没排完，就依次加进数组
temp.append(li[i])
i += 1
while j <= high: #如果是右边数组没排完...
temp.append(li[j])
j += 1
li[low:high+1] = temp #把排好的部分填进对应位置
def merge_sort(li, low, high):
if low < high: #拆分到2个时再递归，子递归里low=high，就不执行下面的了
mid = (low + high) // 2 #对半拆分
merge_sort(li, low, mid) #当前数组的左半边递归拆分
merge_sort(li, mid+1, high) #...右半边递归拆分
merge(li, low, mid, high) #对拆分后的单元进行排序
li = []
for each in range(1000):
li.append(each)
random.shuffle(li)
print(li)
merge_sort(li, 0, len(li)-1)
print(li)
希尔排序
（其相当于插入排序的改进版，插入排序每次只能移动一位，而希尔排序则是通过分组进行插入排序从而提高效率，比如最开始设置一个间隔值gap等于数组长度的一半，每趟排序结束后都除2，那么排序时，把每组的第一个数进行排序，比如有数组：3,5,2,4,1,6,9,7，第一趟时gap=4，那么就把每组的第一个数3和1比较排序，结果是3和1对调，然后第二个数5和6比较排序，不变，第一趟结果为：1,5,2,4,3,6,9,7，然后接着gap=2，继续照前面的操作）
import random
def shell_sort(li):
gap = len(li) // 2 #先分两半进行希尔排序，即左半边和右半边比较
while gap > 0:
for i in range(gap, len(li)):
while i >= gap and li[i-gap] > li[i]: #每组的同一个位置进行比较排序
li[i], li[i-gap] = li[i-gap], li[i]
i -= gap
gap = gap // 2 #循环对半进行排序比较
li = []
for each in range(1000):
li.append(each)
random.shuffle(li)
print(li)
shell_sort(li)
print(li)
计数排序
只能够对纯数值类型的数组进行排序，在特定情况效率非常高，原理是创建对应长度为max值+1大小的数组，然后给每一个计数，最后再添加回去，非in-place，是典型的空间换时间算法，代码如下：
def cs(li):
"""计数排序基础版"""
tmp = [0] * (max(li) + 1)
for i in li:
tmp[i] += 1
res = []
for i in range(len(tmp)):
if tmp[i] > 0:
res.extend([i] * tmp[i])
return res
对于纯数值情况下，时间复杂度基本取决于数组中的最大值
计数排序优化
上面的排序算法有个问题就是只支持正数，而且如果数组中的数值都特别大，那么也会造成空间浪费和效率的降低，因此我们在创建数组时可以在确定上界的同时也确定下界，代码如下：
def cs(li):
"""计数排序优化版，在创建数组前也确定数组的下界，当数据都特别大时，可以避免空间浪费问题，且可以避免负数无法排序的问题"""
base = min(li)
tmp = [0] * (max(li) + 1 - base)
for i in li:
tmp[i - base] += 1
res = []
for i in range(len(tmp)):
if tmp[i] > 0:
res.extend([i + base] * tmp[i])
return res
