二分查找
lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
def binary_search(lst,item):
low = 0
high = len(lst)-1
while low <= high:
mid = (low + high)/2
guess = lst[mid]
if guess == item:
return mid
elif guess > item:
high = mid - 1 # 注意索引的变更
else:
low = mid + 1 # 注意索引的变更
return None
ret = binary_search(lst,17)
if ret:
print('Index is {}'.format(ret))
else:
print('Not found.')
选择排序
raw_lst = [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
# 方法一：两层for循环实现
def sort(lst):
for i in range(len(lst) - 1):
# 记录最小数的索引
minIndex = i
for j in range(i + 1, len(lst)):
if lst[j] < lst[minIndex]:
minIndex = j
# i 不是最小数时，将 i 和最小数进行交换
if i != minIndex:
lst[i], lst[minIndex] = lst[minIndex], lst[i]
return lst
# 方法二：for循环+递归实现（耗时更短）
def sort_recursion(lst):
if 1 == len(lst):
return lst
min_idx = 0
min_num = lst[min_idx]
for i in range(1,len(lst)):
if lst[i]<min_num:
min_idx = i
min_num = lst[min_idx]
lst[min_idx] = lst[0]
lst[0] = min_num
tmp = sort(lst[1:])
tmp.insert(0,lst[0])
return tmp
lst = sort(raw_lst)
print(lst)
冒泡排序
import time
raw_lst = [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
# 方法一：两层for循环实现
def bubbleSort(lst):
for passnum in range(len(lst)-1,0,-1):
for i in range(passnum):
if lst[i]>lst[i+1]:
tmp = lst[i]
lst[i] = lst[i+1]
lst[i+1] = tmp
return lst
# 方法二：for循环+递归实现（耗时更短）
def bubbleSort_recursion(lst):
length = len(lst)
if 1==length:
return lst
for idx in range(length):
if idx<length-1:
if lst[idx]>lst[idx+1]:
tmp = lst[idx]
lst[idx] = lst[idx+1]
lst[idx+1] = tmp
pre_lst = bubbleSort(lst[:-1])
pre_lst.append(lst[-1])
return pre_lst
s1 = time.time()
lst1 = bubbleSort(raw_lst)
print((time.time()-s1)*1000000) # 49.591064453125
s2 = time.time()
lst2 = bubbleSort_recursion(raw_lst)
print((time.time()-s2)*1000000) # 28.848648071289
print(lst1)
print(lst2)
插入排序
希尔排序
快速排序
# 基于 divide&conquer 的快速排序的Python实现
lst = [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
def quicksort(lst):
if len(lst) < 2:
return lst
pivot = lst[0]
left = [ ele for ele in lst[1:] if ele < pivot ]
right = [ ele for ele in lst[1:] if ele >= pivot ]
return quicksort(left) + [pivot,] + quicksort(right)
sorted_lst = quicksort(lst)
print(lst)
print(sorted_lst)
归并排序
典型的分治思想：
- 分 即 将一个大的乱序序列分成很多个不能再分割的子序列，将各个子序列分别排序。
- 治 即 将两个相邻的已经排好序的子序列合并成一个有序序列。
整个过程是递归实现的。
import math
raw_lst = [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
def merge(left,right):
'''
归并
'''
lst = []
num1 = left.pop(0)
num2 = right.pop(0)
while True:
if num1 < num2:
lst.append(num1)
if 0 == len(left):
lst.append(num2)
for num in right:
lst.append(num)
break
else:
num1 = left.pop(0)
else:
lst.append(num2)
if 0 == len(right):
lst.append(num1)
for num in left:
lst.append(num)
break
else:
num2 = right.pop(0)
return lst
def sort(lst):
'''
先拆分 在归并
'''
if 1==len(lst):
return lst
mid = math.floor(len(lst)/2)
left = lst[:mid]
right = lst[mid:]
return merge(sort(left),sort(right)) # 递归
lst = sort(raw_lst)
print(lst)
归并那块写的很不Pythonic，后来看到了 https://www.runoob.com/w3cnote/merge-sort.html
def merge(left,right):
'''
归并
'''
lst = []
while left and right:
if left[0]<right[0]:
lst.append(left.pop(0))
else:
lst.append(right.pop(0))
while left:
lst.append(left.pop(0))
while right:
lst.append(right.pop(0))
return lst
归并排序在处理大文件排序问题中有很好的应用：大文件排序/外存排序问题
堆排序
参考: https://www.cnblogs.com/chengxiao/p/6129630.html
堆的定义和基本性质
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
任意节点（索引为K）的父节点的索引是 (K-1)/2 。
任意节点（索引为K）的左叶子节点的索引是 2*K+1 ,右叶子节点的索引是 2*K+2 。
假设节点数为 N，那么最后一个非叶子节点的索引是 N/2-1 。
堆排序的基本思想
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。 将其与末尾元素进行交换，此时末尾就为最大值。 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。 如此反复执行，便能得到一个有序序列了。
堆排序代码实现
class HeapSort(object):
def __init__(self, lst):
self._list = lst
def adjust(self, parent_idx, length):
parent_val = self._list[parent_idx]
child_idx = parent_idx*2+1
while child_idx < length:
# 比较左叶子节点和右叶子节点的大小, 取较大的一个
if child_idx+1<length and self._list[child_idx]<self._list[child_idx+1]:
child_idx += 1
# 比较叶子节点和父节点的大小, 把较大值赋给父节点
if self._list[child_idx] > parent_val:
self._list[parent_idx] = self._list[child_idx] # 因为可能还需要进行下一层的替换, 所以这里替换操作只做一半
parent_idx = child_idx
child_idx = child_idx*2+1
else:
break
self._list[parent_idx] = parent_val # 把当前循环的父节点的值放到最终位置
def heap_build(self):
# Step1: 构建大顶堆
# 从最后一个非叶子节点开始调整, 从下至上 从右直左
length = len(self._list)
parent_idx = length//2-1
while parent_idx >= 0:
self.adjust(parent_idx, length)
parent_idx -= 1
def head_sort(self):
# Step2: 堆排序
length = len(self._list)
for sub_length in range(length-1,-1,-1):
# Step2.1: 交换堆顶元素与末尾元素
tmp = self._list[0]
self._list[0] = self._list[sub_length]
self._list[sub_length] = tmp
# Step2.2: 把最大值沉到列表末端, 重新调整堆结构
# 注意: 这次调整堆结构是从堆顶开始的, 并且需要重排的列表也是随着最大值的下沉而逐渐减少, 即保证前一次得到的最大值不会参与到本次的堆调整
self.adjust(0, sub_length)
lst = [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
obj = HeapSort(lst)
obj.heap_build()
obj.head_sort()