算法基础
算法概念
时间复杂度
空间复杂度
复习:递归
算法（Algorithm）：一个计算过程，解决问题的方法
Niklaus Wirth："程序 = 数据结构 + 算法"
时间复杂度
类比生活中的一些事件，估计时间：
- 眨一下眼 一瞬间/几毫秒
- 口算"26+68" 几秒
- 烧一壶水 几分钟
- 睡一觉 几小时
- 完成一个项目 几天/几星期/几月
- 飞船从地球飞出太阳系 几年
时间复杂度：用来评估算法运行效率的一个式子
小结
- 时间复杂度是用来估计算法运行时间的一个式子（单位）
- 一般来说，时间复杂度高的算法比复杂度低的算法慢
常见的时间复杂度（按效率排序）
- O(1) < O(logn) < O(n) < O(nlogn) < O(n²)<O(n²logn) < O(n三次方)
复杂问题的时间复杂度
- O(n!) O(2的n次方) O(n的n次方).....
如何简单快速地判断算法复杂度
快速判断算法复杂度（适用于绝大多数简单情况）
确定问题规模n
循环减半过程 -> logn
k层关于n的循环 -> n的k次方
- 复杂情况：根据算法执行过程判断
空间复杂度
- 空间复杂度：用来评估算法内存占用大小的式子
空间复杂度的表示方式与时间复杂度完全一样
- 算法使用了几个变量：O(1)
- 算法使用了长度为n的一维列表：O(n)
- 算法使用了m行n列的二维列表：O(mn)
空间换时间
复习：递归
递归的两个特点：
- 调用自身
- 结束条件
递归实例：汉诺塔问题
大梵天创造世界的时候做了了三根金刚石柱⼦，在一根柱⼦上从下往上按照大小顺序摞着64片⻩金圆盘。
大梵天命令婆罗⻔门把圆盘从下⾯面开始按大小顺序重新摆放在另一根柱⼦子上。
在小圆盘上不能放⼤圆盘，在三根柱子之间一次只能移动一个圆盘。
64根柱⼦移动完毕之日，就是世界毁灭之时。
n = 2时：
1、把小圆盘从A移动到B
2、把大圆盘从A移动到C
3、把小圆盘从B移动到C
n个盘子时：
1、把n-1个圆盘从A经过C移动到B
2、把第n个圆盘从A移动到C
3、把n-1个小圆盘从B经过A移动到C
def hanoi(n, a, b, c):
if n > 0:
hanoi(n - 1, a, c, b)
print("#%d:moving from %s to %s." % (n, a, c))
hanoi(n - 1, b, a, c)
hanoi(3, "a", "b", "c")
- 汉诺塔移动次数的递推式: h(x)= 2h(x-1) + 1
- h(64) = 18446744073709551615
- 假设婆罗⻔门每秒钟搬⼀一个盘⼦子，则总共需要5800亿年!
列表查找
- 什么是列表查找
- 顺序查找
- 二分查找
查找
- 查找：在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程
列表查找（线性表查找）：从列表中查找指定元素
- 输入：列表、待查找元素
- 输出：元素下标（未找到元素时一般返回None或-1）
内置列表查找函数: index()
顺序查找(Linear Search)
顺序查找：也叫线性查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后一个元素为止
时间复杂度：O(n)
def linear_search(data_set,value): for i in range(len(data_set)): if data_set[i] == value: return i return print(linear_search([1,2,3,4,9,6,5],4))
二分查找(Binary Search)
- 二分查找：又叫折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半
实例
- 从列表中查找元素3：
- 时间复杂度: O(logn)
def bin_saerch(data_set,value):
# 下标
low = 0
high = len(data_set) -1
while low <= high:
mid = (low+high)//2
if data_set[mid] == value:
return mid
# 左边
elif data_set[mid] > value:
high = mid - 1
# 右边
else:
low = mid + 1
# _*_coding:utf-8_*_
# created by Alex Li on 11/5/17
import time
def cal_time(func):
def wrapper(*args, **kwargs):
t1 = time.time()
result = func(*args, **kwargs)
t2 = time.time()
print("%s running time: %s secs." % (func.__name__, t2 - t1))
return result
return wrapper
# _*_coding:utf-8_*_
# created by Alex Li on 11/5/17
from cal_time import *
@cal_time
def linear_search(li, val):
for ind, v in enumerate(li):
if v == val:
return ind
else:
return None
@cal_time
def binary_search(li, val):
left = 0
right = len(li) - 1
while left <= right: # 候选区有值
mid = (left + right) // 2
if li[mid] == val:
return mid
elif li[mid] > val: # 带查找的值在mid左侧
right = mid - 1
else: # li[mid] < val 带查找的值在mid右侧
left = mid + 1
else:
return None
li = list(range(10000000000))
# linear_search(li, 3890000)
binary_search(li, 3890000)
列表排序
- 什么是列表排序
- 常见排序算法介绍
- 排序算法分析
- 排序：将一组"无序"的记录序列调整为"有序"的记录序列
列表排序：将无序列表变为有序列表
- 输入：列表
- 输出：有序列表
升序与降序
- 内置排序函数: sort()
常见排序算法
排序Low B三人组
- 冒泡排序
- 选择排序
- 插入排序
排序NB三人组
- 快速排序
- 堆排序
- 归并排序
其他排序
- 希尔排序
- 计数排序
- 基数排序
冒泡排序(Bubble Sort)
- 列表每两个相邻的数，如果前面比后面大，则交换这两个数
- 一趟排序完成后，则无序区减少一个数，有序区增加一个数
- 代码关键点：趟、无序区范围
def bubble_sort(li):
for i in range(len(li)-1):
# 需要的趟数 需要n-1趟，最后一个数不需要排序
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
- 时间复杂度: O(n²)
冒泡排序-优化
- 如果冒泡排序中的一趟排序都没有发生交换，则说明列表已经有序，可以直接结束算法
def bubble_sort_1(li):
for i in range(len(li) - 1):
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
exchange = True
if not exchage:
return
选择排序(Select Sort)
- 一趟排序记录最小的数，放到第一个位置
- 在一趟排序记录列表无序区最小的数，放到第二个位置
- ......
- 算法关键点：有序区和无序区、无序区最小数的位置
def select_sort_simple(li):
li_new = []
for i in range(len(li)):
min_val = min(li)
li_new.append(min_val)
li.remove(min_val)
return li_new
def select_sort(li):
# 默认拿一个最小值，排除最小的
for i in range(len(li)-1):
min_loc = i
for j in range(i+1,len(li)):
if li[j] < li[min_loc]:
min_loc = j
# 列表最小不相等，交换位置，最小的数放到第一个位置
if min_loc != i:
li[i],li[min_loc] = li[min_loc],li[i]
- 时间复杂度：O(n²)
插入排序
- 初始时手里（有序区）只有一张牌
- 每次（从无序区）摸一张牌，插入到手里已有牌的正确位置
def insert_sort(li):
#i 表示摸到的牌的下标
for i in range(1,len(li)):
tmp = li[i]
#j指的是手里的牌的下标
j = i - 1
# 每次往右移动 找插入的位置 j的位置
while j>=0 and tmp < li[j]:
li[j+1] = li[j]
j = j -1
li[j+1] = tmp
# _*_coding:utf-8_*_
# created by Alex Li on 11/5/17
def insert_sort(li):
for i in range(1, len(li)): #i 表示摸到的牌的下标
tmp = li[i]
j = i - 1 #j指的是手里的牌的下标
while j >= 0 and li[j] > tmp:
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
print(li)
li = [3,2,4,1,5,7,9,6,8]
print(li)
insert_sort(li)
#print(li)
- 时间复杂度: O(n²)
快速排序
快速排序：快
快速排序思路：
- 取一个元素P(第一个元素)，使元素P归位
- 列表被P分成两部分，左边都比P小，右边都比P大
- 递归完成排序
框架
def quick_sort(data,left,right):
if left < right:
mid = partition(data,left,right)
#每次找到mid排序，每次减半
quick_sort(data,left,mid-1)
quick_sort(data,mid+1,right)
partition函数
def partition(data,left,right):
tmp = data[left]
while left < right:
# 从右面找比tmp小的数
while left < right and data[right] >= tmp:
# 往左走一步
right -= 1
# 把右边的值写到左边的空位上
data[left] = data[right]
while left < right and data[left] <= tmp:
left += 1
# 把左边的值写到右边空位上
data[right] = data[left]
# 把tmp归位
data[left] = tmp
return left
快速排序的效率：
- 快速排序的时间复杂度 O(nlogn) 比如 n=1024 n²=10241024 nlogn 1024 10 2的10次方(n=10) 跟n²对比3242亿 42亿 42亿
快速排序的问题：
- 最坏情况 （倒序情况range(1000,0,-1)，解决:随机找值，跟第一步交换） O(n²)
- 递归
# _*_coding:utf-8_*_
# created by Alex Li on 11/5/17
import random
from cal_time import *
import copy
import sys
sys.setrecursionlimit(100000)
@cal_time
def bubble_sort(li):
for i in range(len(li)-1): #第i趟
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
if not exchange:
return
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp: #从右面找比tmp小的数
right -= 1 # 往左走一步
li[left] = li[right] #把右边的值写到左边空位上
print(li, 'right')
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left] #把左边的值写到右边空位上
print(li, 'left')
li[left] = tmp # 把tmp归位
return left
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)
@cal_time
def quick_sort(li):
_quick_sort(li, 0, len(li)-1)
# li = list(range(10000, 0, -1))
# random.shuffle(li)
#
# li1 = copy.deepcopy(li)
# li2 = copy.deepcopy(li)
#
# quick_sort(li)
# bubble_sort(li2)
#
# print(li1)
# print(li2)
li = [9,8,7,6,5,4,3,2,1]
partition(li, 0, len(li)-1)
print(li)
堆排序
堆排序前传-树与二叉树
- 树是一种数据结构 比如：目录结构
- 树是一种可以递归定义的数据结构
- 树是由n个节点组成的集成：
- 如果n=0，那这是一颗空数
- 如果n>0,那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树
一些概念
根节点、叶子节点
树的深度（高度）
树的度（有几个分叉）
孩子节点/父节点
子树
二叉树
- 二叉树：度不超过2的树
- 每个节点最多有两个孩子节点
- 两个孩子节点被区分为左孩子节点和右孩子节点
完全二叉树
- 满二叉树：一个二叉树，如果每一个层的节点数都达到最大值，则这个二叉树就是满二叉树
- 完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
二叉树的存储方式
- 二叉树的存储方式（表示方式）
- 链式存储方式
- 顺序存储方式
二叉树顺序存储方式
父节点和左孩子节点的编号下标有什么关系？
- 0-1 1-3 2-5 3-7 4-9
- i --> 2i + 1
父节点和右孩子节点的编号下标有什么关系？
- 0-2 1-4 2-6 3-8 4-10
- i --> 2i + 2
- 通过孩子找到父节点 2//i + 1
小结
- 树
- 二叉树
- 完全二叉树
- 完全二叉树的顺序存储方式
什么是堆
- 堆：一种特殊的完全二叉树结构
- 大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大
- 小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小
堆的向下调整性质
- 假设根节点的左右子树都是堆，但根节点不满足堆的性质
- 可以通过一次向下的调整来将其变成一个堆
构造堆
从最小的子孩子开始构造，农村包围城市
从最下面的非叶子节点开始
挨个出数
实现从小到大排序
堆排序过程
1、建立堆
2、得到堆顶元素，为最大元素
3、去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序
4、堆顶元素为第二大元素
5、重复步骤3，直到堆变空
def sift(data,low,high):
"""
:param li: 列表
:param low: 堆的根节点位置
:param high: 堆的最后一个元素的位置
:return:
"""
i = low # i最开始指向根节点
j = 2 * i + 1 # j开始是左孩子
tmp = data[i] # 把堆顶存起来
while j <= high: # 只要j位置有数
if j<high and data[j] < data[j+1]: # 如果右孩子有并且比较大
j += 1 # j指向右孩子
if tmp < data[j]:
data[i] = data[j]
i = j # 往下看一层
j = 2 * i + 1
else: # tmp更大，把tmp放到i的位置上
break
data[i] = tmp # 把tmp放到叶子节点上
def heap_sort(data):
n = len(data)
# 创建堆 农村包围城市
# i表示建堆的时候调整的部分的根的下标 (n-1-1)//2 从最下层子孩子开始
for i in range(n//2-1,-1,-1):
sift(data,i,n-1)
# 建堆完成了
for i in range(n-1,-1,-1):
# i 指向当前堆的最后一个元素
data[0],data[i] = data[i],data[0]
sift(data,0,i-1) #i-1是新的high
# _*_coding:utf-8_*_
# created by Alex Li on 12/3/17
def sift(li, low, high):
"""
:param li: 列表
:param low: 堆的根节点位置
:param high: 堆的最后一个元素的位置
:return:
"""
i = low # i最开始指向根节点
j = 2 * i + 1 # j开始是左孩子
tmp = li[low] # 把堆顶存起来
while j <= high: # 只要j位置有数
if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有并且比较大
j = j + 1 # j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j # 往下看一层
j = 2 * i + 1
else: # tmp更大，把tmp放到i的位置上
li[i] = tmp # 把tmp放到某一级领导位置上
break
else:
li[i] = tmp # 把tmp放到叶子节点上
def heap_sort(li):
n = len(li)
for i in range((n-2)//2, -1, -1):
# i表示建堆的时候调整的部分的根的下标
sift(li, i, n-1)
# 建堆完成了
for i in range(n-1, -1, -1):
# i 指向当前堆的最后一个元素
li[0], li[i] = li[i], li[0]
sift(li, 0, i - 1) #i-1是新的high
li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)
heap_sort(li)
print(li)
内置模块
python内置模块 --- heapq
常用函数
heapify(x) # 建堆
heappush(heap,item)
Heappop(heap)
import heapq #q->queue 优先队列 可以大的先出 or 小的先出 import random li = list(range(100)) random.shuffle(li) print(li) heapq.heapify(li) #建堆 n=len(li) for i in range(n): print(heapq.heappop(li), end=',')
topk问题
- 现在有n个数，设计算法得到前k大的数。（k<n）
解决思路：
- 排序后切片 O(nlogn)
- 排序LowB三人组 O(kn)
- 堆排序思路 O(nlogk)
取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数
- 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素，如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整
- 遍历列表所有元素后，倒序弹出堆顶
def topk(li,k):
heap = li[0:k]
for i in range(k//2 -1,-1,-1):
sift(heap,i,k-1)
for i in range(k,len(li)):
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap,0,k-1)
for i in range(k-1,-1,-1):
heap[0],heap[i] = heap[i],heap[0]
sift(heap,0,i-1)
return heap
- 关键思路：建立小根堆，每个都比堆顶大，如果比堆顶还小，忽略，如果比堆顶大，替换后就重新向下重排一次，最后输出小根堆，就是前10个最大的数
# _*_coding:utf-8_*_
# created by Alex Li on 12/3/17
# 比较排序
def sift(li, low, high):
i = low
j = 2 * i + 1
tmp = li[low]
while j <= high:
if j + 1 <= high and li[j+1] < li[j]:
j = j + 1
if li[j] < tmp:
li[i] = li[j]
i = j
j = 2 * i + 1
else:
break
li[i] = tmp
def topk(li, k):
heap = li[0:k]
for i in range((k-2)//2, -1, -1):
sift(heap, i, k-1)
# 1.建堆
for i in range(k, len(li)-1):
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap, 0, k-1)
# 2.遍历
for i in range(k-1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
sift(heap, 0, i - 1)
# 3.出数
return heap
import random
li = list(range(1000))
random.shuffle(li)
print(topk(li, 10))
归并排序
归并
- 假设现在的列表分两段有序，如何将其合成为一个有序列表
- 这种操作称为一次归并
一次归并代码
def merge(li,low,mid,high):
i = low
j = mid + 1
ltmp = []
while i<=mid and j<=high:
if li[i] <= li[j]:
ltmp.append(li[i])
i+=1
else:
ltmp.append(li[j])
j+=1
while i <= mid:
ltmp.append(li[i])
i+=1
while j<=high:
ltmp.append(li[j])
j+=1
# 写回到新列表
li[low:high+1]=ltmp
使用归并
- 分解：将列表越分越小，直至分成一个元素
- 终止条件：一个元素是有序的
- 合并：将两个有序列表归并，列表越来越大
# 分解和重组 递归的思想
def mergesort(li,low,high):
if low < high:
mid = (low+high)//2
mergesort(li,low,mid)
mergesort(li,mid+1,high)
mergesort(li,low,mid,high)
# _*_coding:utf-8_*_
# created by Alex Li on 12/3/17
def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i<=mid and j<=high: # 只要左右两边都有数
if li[i] < li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
# while执行完，肯定有一部分没数了
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp
# li = [2,4,5,7,1,3,6,8]
# merge(li, 0, 3, 7)
# print(li)
def merge_sort(li, low, high):
if low < high: #至少有两个元素，递归
mid = (low + high) //2
merge_sort(li, low, mid)
merge_sort(li, mid+1, high)
merge(li, low, mid, high)
li = list(range(1000))
import random
random.shuffle(li)
print(li)
merge_sort(li, 0, len(li)-1)
print(li)
- 时间复杂度: O(nlogn)
- 空间复杂度: O(n)
NB三个组小结
- 三种排序算法的时间复杂度都是O(nlogn)
一般情况下，就运行时间而言：
- 快速排序 < 归并排序 < 堆排序
三种排序算法的缺点：
- 快速排序：极端情况下排序效率低
- 归并排序：需要额外的内存开销
- 堆排序：在块的排序算法中相对较慢
# _*_coding:utf-8_*_
# created by Alex Li on 12/3/17
from cal_time import *
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp: #从右面找比tmp小的数
right -= 1 # 往左走一步
li[left] = li[right] #把右边的值写到左边空位上
# print(li, 'right')
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left] #把左边的值写到右边空位上
# print(li, 'left')
li[left] = tmp # 把tmp归位
return left
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)
@cal_time
def quick_sort(li):
_quick_sort(li, 0, len(li)-1)
def sift(li, low, high):
"""
:param li: 列表
:param low: 堆的根节点位置
:param high: 堆的最后一个元素的位置
:return:
"""
i = low # i最开始指向根节点
j = 2 * i + 1 # j开始是左孩子
tmp = li[low] # 把堆顶存起来
while j <= high: # 只要j位置有数
if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有并且比较大
j = j + 1 # j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j # 往下看一层
j = 2 * i + 1
else: # tmp更大，把tmp放到i的位置上
li[i] = tmp # 把tmp放到某一级领导位置上
break
else:
li[i] = tmp # 把tmp放到叶子节点上
@cal_time
def heap_sort(li):
n = len(li)
for i in range((n-2)//2, -1, -1):
# i表示建堆的时候调整的部分的根的下标
sift(li, i, n-1)
# 建堆完成了
for i in range(n-1, -1, -1):
# i 指向当前堆的最后一个元素
li[0], li[i] = li[i], li[0]
sift(li, 0, i - 1) #i-1是新的high
def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i<=mid and j<=high: # 只要左右两边都有数
if li[i] < li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
# while执行完，肯定有一部分没数了
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp
def _merge_sort(li, low, high):
if low < high: #至少有两个元素，递归
mid = (low + high) //2
_merge_sort(li, low, mid)
_merge_sort(li, mid+1, high)
merge(li, low, mid, high)
@cal_time
def merge_sort(li):
return _merge_sort(li, 0, len(li)-1)
import random,copy
li = list(range(100000))
random.shuffle(li)
li1 = copy.deepcopy(li)
li2 = copy.deepcopy(li)
li3 = copy.deepcopy(li)
quick_sort(li1)
heap_sort(li2)
merge_sort(li3)
希尔排序
- 希尔排序(shell sort)是一种分组插入排序算法
- 首先取一个整数d1=n/2,将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序
- 取第二个整数d2=d1/2，重复上述分组排序过程，直到d1=1，即所有元素在同一组内进行直接插入排序
- 希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序，最后一趟排序使得所有数据有序
def shell_sort(li):
gap = len(li) //2
while gap >0:
for i in range(gap,len(li)):
tmp = li[i]
j = i - gap
while j>=0 and tmp <li[j]:
li[j + gap] = li[j]
j -= gap
li[j + gap] = tmp
gap /= 2
# _*_coding:utf-8_*_
# created by Alex Li on 12/3/17
from cal_time import *
def insert_sort_gap(li, gap):
for i in range(gap, len(li)): #i 表示摸到的牌的下标
tmp = li[i]
j = i - gap #j指的是手里的牌的下标
while j >= 0 and li[j] > tmp:
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp
@cal_time
def shell_sort(li):
d = len(li) // 2
while d >= 1:
insert_sort_gap(li, d)
d //= 2
@cal_time
def insert_sort(li):
for i in range(1, len(li)): #i 表示摸到的牌的下标
tmp = li[i]
j = i - 1 #j指的是手里的牌的下标
while j >= 0 and li[j] > tmp:
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
def sift(li, low, high):
"""
:param li: 列表
:param low: 堆的根节点位置
:param high: 堆的最后一个元素的位置
:return:
"""
i = low # i最开始指向根节点
j = 2 * i + 1 # j开始是左孩子
tmp = li[low] # 把堆顶存起来
while j <= high: # 只要j位置有数
if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子有并且比较大
j = j + 1 # j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j # 往下看一层
j = 2 * i + 1
else: # tmp更大，把tmp放到i的位置上
li[i] = tmp # 把tmp放到某一级领导位置上
break
else:
li[i] = tmp # 把tmp放到叶子节点上
@cal_time
def heap_sort(li):
n = len(li)
for i in range((n-2)//2, -1, -1):
# i表示建堆的时候调整的部分的根的下标
sift(li, i, n-1)
# 建堆完成了
for i in range(n-1, -1, -1):
# i 指向当前堆的最后一个元素
li[0], li[i] = li[i], li[0]
sift(li, 0, i - 1) #i-1是新的high
import random,copy
li = list(range(100000))
random.shuffle(li)
li1 = copy.deepcopy(li)
li2 = copy.deepcopy(li)
li3 = copy.deepcopy(li)
shell_sort(li1)
#insert_sort(li2)
heap_sort(li3)
- 希尔排序的时间复杂度讨论比较复杂，并且和选取的gap序列有关
计数排序
- 对列表进行排序，已知列表中的数范围都在0到100之间，设计时间复杂度为O(n)的算法
def count_sort(li,max_num):
count = [0 for i in range(max_num + 1)]
for num in li:
count[num] += 1
i = 0
for num,m in enumerate(conut):
for j in range(m):
li[i] = num
i += 1
# _*_coding:utf-8_*_
# created by Alex Li on 12/3/17
from cal_time import *
@cal_time
def count_sort(li, max_count=100):
count = [0 for _ in range(max_count+1)]
for val in li:
count[val] += 1
li.clear()
for ind, val in enumerate(count):
for i in range(val):
li.append(ind)
@cal_time
def sys_sort(li):
li.sort()
import random, copy
li = [random.randint(0,100) for _ in range(100000)]
li1 = copy.deepcopy(li)
li2 = copy.deepcopy(li)
count_sort(li1)
sys_sort(li2)
桶排序
在计数排序中，如果元素的范围比较大（比如在1到1亿之间），如何改造算法？
桶排序（Bucket Sort）：首先将元素分在不同的桶中，在对每个桶中的元素排序
- 桶排序的表现取决于数据的分布，也就是需要对不同数据排序时采取不同的分桶策略
- 平均情况时间复杂度：O(n+k)
- 最坏情况时间复杂度：O(n²k)
- 空间复杂度: O(nk)
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 2017/12/10
import random
def bucket_sort(li, n=100, max_num=10000):
buckets = [[] for _ in range(n)] # 创建桶
for var in li:
i = min(var // (max_num // n), n-1) # i 表示var放到几号桶里
buckets[i].append(var) # 把var加到桶里边
# 保持桶内的顺序
for j in range(len(buckets[i])-1, 0, -1):
if buckets[i][j] < buckets[i][j-1]:
buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
else:
break
sorted_li = []
for buc in buckets:
sorted_li.extend(buc)
return sorted_li
li = [random.randint(0,10000) for i in range(100000)]
# print(li)
li = bucket_sort(li)
print(li)
基数排序
多关键字排序：加入现在有一个员工表，要求按照薪资排序，年龄相同的员工按照年龄排序
- 先按照年龄进行排序，在按照薪资进行稳定的排序
对32，13，94，52，17，54，93排序，是否可以看做多关键字排序？
def list_to_backets(li,base,iteration):
backets = [[] for _ in range(base)]
for number in li:
digit = (number // (base ** iteration)) % base
buckets[digit].append(number)
return buckets
def buckets_to_list(buckets):
return [x for bucket in backets for x in bucket]
def radix_sort(li,base=10):
maxval = max(li)
it =0
while base ** it <= maxval:
li = buckets_to_list(list_to_buckets(li,base,it))
it += 1
return li
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 2017/12/10
# O(n) O(kn)
#NB O(nlogn)
from cal_time import *
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp: #从右面找比tmp小的数
right -= 1 # 往左走一步
li[left] = li[right] #把右边的值写到左边空位上
# print(li, 'right')
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left] #把左边的值写到右边空位上
# print(li, 'left')
li[left] = tmp # 把tmp归位
return left
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)
@cal_time
def quick_sort(li):
_quick_sort(li, 0, len(li)-1)
@cal_time
def radix_sort(li):
max_num = max(li) # 最大值 9->1, 99->2, 888->3, 10000->5
it = 0
while 10 ** it <= max_num:
buckets = [[] for _ in range(10)]
for var in li:
# 987 it=1 987//10->98 98%10->8; it=2 987//100->9 9%10=9
digit = (var // 10 ** it) % 10
buckets[digit].append(var)
# 分桶完成
li.clear()
for buc in buckets:
li.extend(buc)
# 把数重新写回li
it += 1
import random,copy
li = [random.randint(0,100000000) for _ in range(100000)]
random.shuffle(li)
li1 = copy.deepcopy(li)
li2 = copy.deepcopy(li)
li3 = copy.deepcopy(li)
quick_sort(li1)
radix_sort(li2)
讨论
- 时间复杂度：O(kn)
- 空间复杂度: O(k+n)
- k表示数字位数
查找排序面试题
1、给两个字符串s和t，判断t是否为s的重新排列后组成的单词（再leetcode上面解答）
- s = "anagram" ，t="nagaram"，return ture.
- s = "rat", t="car",return false
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
return sorted(list(s)) == sorted(list(t))
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
ss = list(s)
tt = list(t)
ss.sort()
tt.sort()
return ss == tt
2、给定一个m*n的二维列表，查找一个数是否存在。列表有下列特性：
每一行的列表从左到右已经排序好
每一行第一个数比上一行最后一个数大
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
h = len(matrix)
if h == 0:
return False
w = len(matrix[0])
if w == 0:
return False
left = 0
right = w * h -1
while left <= right:
mid = (left + right) // 2
i = mid // w
j = mid % w
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
right = mid -1
else:
left = mid +1
else:
return False
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
for line in matrix:
if target in line:
return True
return False
3、给定一个列表和一个整数，设计算法找到两个数的下标，使得两个数之和为给定的整数。保证肯定仅有一个结果
- 例如，列表[1,2,5,4]与目标整数3，1+2=3，结果为(0,1)
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
for i in range(n):
for j in range(i):
if nums[i] + nums[j] == target:
return sorted([i,j])