查找（二分查找），经典排序（冒泡排序、选择排序/插入排序、谢尔排序、归并排序、快速排序）
常考问题：topk 即找出前k大或者前k小的数，使用快排和堆排序实现。补充二叉堆的概念理解和功能实现。
二分查找
二分查找的递归算法
——返回T F
### 二分查找的递归算法
### 如果只剩下1个数字，直接对比，如果不是则不存在
def binarySearch(alist,item):
# 停止条件
if not alist:
return False
if len(alist) == 1:
return alist[0]==item
# 递归
mid = len(alist)//2
return binarySearch(alist[:mid], item) or binarySearch(alist[mid:], item)
print(binarySearch([1,3,5,8,12,19,25], 8))
True
二分查找的双指针算法（重要）
稍微改造一下可以返回下标值，并且复杂度更优
def binarysearch(nums, target):
if not nums:
return False
l, r = 0, len(nums) - 1
while l <= r:
if target < nums[l] or target > nums[r]:
return False
mid = (l + r) // 2
if target == nums[mid]:
return True
if target > nums[mid]:
l = mid + 1
if target < nums[mid]:
j = mid -1
return False
print(binarySearch([1,3,5,8,12,19,25], 2))
False
排序
冒泡排序
- 对无序表多趟比较，每趟多次相邻对比交换，并交换。第i躺排序第i大的项。
- 稍加改进的版本：加入exchange， 如果这一趟没有exchange 说明排序完成了， 直接break
### 1.原始版本
nums = [34,82,66,14,56,80,9,44,69,21,60,65]
for i in range(len(nums)):
for idx in range(len(nums)-1):
if nums[idx] > nums[idx+1]:
nums[idx], nums[idx+1] = nums[idx + 1], nums[idx]
print(nums)
print('\n改进版本:\n')
### 2.加入exchange的改进版本
nums = [34,82,66,14,56,80,9,44,69,21,60,65]
for i in range(len(nums)):
exchange = False
for idx in range(len(nums)-1):
if nums[idx] > nums[idx + 1]:
exchange = True
nums[idx], nums[idx + 1] = nums[idx + 1], nums[idx]
if not exchange: break
print(nums)
[34, 66, 14, 56, 80, 9, 44, 69, 21, 60, 65, 82]
[34, 14, 56, 66, 9, 44, 69, 21, 60, 65, 80, 82]
[14, 34, 56, 9, 44, 66, 21, 60, 65, 69, 80, 82]
[14, 34, 9, 44, 56, 21, 60, 65, 66, 69, 80, 82]
[14, 9, 34, 44, 21, 56, 60, 65, 66, 69, 80, 82]
[9, 14, 34, 21, 44, 56, 60, 65, 66, 69, 80, 82]
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
改进版本:
[34, 66, 14, 56, 80, 9, 44, 69, 21, 60, 65, 82]
[34, 14, 56, 66, 9, 44, 69, 21, 60, 65, 80, 82]
[14, 34, 56, 9, 44, 66, 21, 60, 65, 69, 80, 82]
[14, 34, 9, 44, 56, 21, 60, 65, 66, 69, 80, 82]
[14, 9, 34, 44, 21, 56, 60, 65, 66, 69, 80, 82]
[9, 14, 34, 21, 44, 56, 60, 65, 66, 69, 80, 82]
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
选择排序/插入排序
和动态规划的感觉类似，每一次迭代完成前i项的排序
前k项已经从小到大排序了，现在看第k+1个：
- 顺序对比第k+1个应该插入到前K项的哪里，即对于前k项从右向左遍历，如果大于k+1项则往后挪1
- 直到前K项中，所有大于第K+1项的都已经依次往后挪了一位，空出来的那位插入第K+1项
- 结果——前k+1项已经从小到大排序了
nums = [34,82,66,14,56,80,9,44,69,21,60,65]
for idx in range(1, len(nums)):
tmp = nums[idx]
j = 1
while j <= idx and nums[idx - j] > tmp: # 前面所有小于tmp 的都依次往后挪1
nums[idx - j + 1] = nums[idx - j]
j += 1
nums[idx - j + 1] = tmp # 多出来的位置插入tmp
print(nums)
[34, 82, 66, 14, 56, 80, 9, 44, 69, 21, 60, 65]
[34, 66, 82, 14, 56, 80, 9, 44, 69, 21, 60, 65]
[14, 34, 66, 82, 56, 80, 9, 44, 69, 21, 60, 65]
[14, 34, 56, 66, 82, 80, 9, 44, 69, 21, 60, 65]
[14, 34, 56, 66, 80, 82, 9, 44, 69, 21, 60, 65]
[9, 14, 34, 56, 66, 80, 82, 44, 69, 21, 60, 65]
[9, 14, 34, 44, 56, 66, 80, 82, 69, 21, 60, 65]
[9, 14, 34, 44, 56, 66, 69, 80, 82, 21, 60, 65]
[9, 14, 21, 34, 44, 56, 66, 69, 80, 82, 60, 65]
[9, 14, 21, 34, 44, 56, 60, 66, 69, 80, 82, 65]
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
谢尔排序
- 按照间隔划分子列表，分别插入排序后，整体更加接近有序。
- 间隔越来越小，最后间隔为1时进行的插入排序，复杂度和对无序进行插入排序完全不同。
- 复杂度为o(n^1.5)
nums = [34,82,66,14,56,80,9,44,69,21,60,65]
def gapsort(nums, gap):
for i in range(gap, len(nums), gap):
# 进行排序
tmp = nums[i]
j = gap
while j <= i and nums[i - j] > tmp:
nums[i - j + gap] = nums[i - j]
j += gap
nums[i - j + gap] = tmp
print([nums[i] for i in range(0, len(nums), gap)]) # 输出子列的排序结果
return nums
def shellsort(nums):
gap = len(nums)//2
while gap>0:
nums = gapsort(nums, gap)
print(nums) # 一次gap排序的结果
gap = gap // 2
return nums
shellsort(nums)
[9, 34]
[9, 82, 66, 14, 56, 80, 34, 44, 69, 21, 60, 65]
[9, 14, 21, 34]
[9, 82, 66, 14, 56, 80, 21, 44, 69, 34, 60, 65]
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
归并排序
def mergesort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = mergesort(nums[:mid])
right = mergesort(nums[mid:])
# merge
merged = []
while left and right:
if left[0] <= right[0]:
merged.append(left.pop(0))
else:
merged.append(right.pop(0))
merged.extend(left if left else right)
return merged
nums = [34,82,66,14,56,80,9,44,69,21,60,65]
mergesort(nums)
[9, 14, 21, 34, 44, 56, 60, 65, 66, 69, 80, 82]
快速排序
思想：首先找一个基准值，设置一个左标和右标，从两侧开始：
- 左标对应数字应该小于基准值，如果大于，左标暂时不动，等待与右标交换
- 右标对应数字应该大于基准值，如果小于，右标暂时不动，等待与左标交换
- 左标往右移动，右标往左移动
使得list前面的都小于基准值，后面的都大于基准值
对前面的部分和后面的部分分别递归——最后+连接起来，递归终值条件为长度<=1
def fastsort(nums):
if len(nums) <= 1:
return nums
baseline = nums[0]
left, right = 1, len(nums) - 1
while left < right:
if nums[left] < baseline:
left += 1
elif nums[right] > baseline:
right -= 1
elif nums[left] > baseline > nums[right]:
nums[left], nums[right] = nums[right], nums[left]
if nums[left] < nums[0]:
nums[left], nums[0] = nums[0], nums[left]
print(nums)
l = fastsort(nums[:left])
r = fastsort(nums[left:])
return l + r
nums = [32,34,82,66,14,56,80,9,44,69,21,60,65]
fastsort(nums)
[32, 21, 9, 14, 66, 56, 80, 82, 44, 69, 34, 60, 65]
[14, 21, 9, 32]
[14, 9, 21]
[9, 14]
[66, 56, 65, 60, 44, 34, 69, 82, 80]
[34, 56, 65, 60, 44, 66]
[34, 56, 65, 60, 44]
[56, 44, 60, 65]
[44, 56]
[60, 65]
[69, 82, 80]
[80, 82]
[9, 14, 21, 32, 34, 44, 56, 60, 65, 66, 69, 80, 82]
topk 类问题
- 简单的可以用排序稍微变换一下，比如用快排
- 用堆排序
快排
e.g. 剑指 Offer 40. 最小的k个数
# topk 快排问题
nums = [32,34,82,66,14,56,80,9,44,69,21,60,65]
def minK(nums, k):
if k < 1:
return []
if k >= len(nums):
return nums
tmp = nums[0]
left, right = 1, len(nums) - 1
while left < right:
if nums[right] < tmp < nums[left]:
nums[right], nums[left] = nums[left], nums[right]
elif nums[left] <= tmp:
left += 1
elif nums[right] >= tmp:
right -= 1
if nums[left] < tmp:
nums[0], nums[left] = nums[left], nums[0]
# 递归
if left >= k:
return minK(nums[:left], k)
if left < k:
return nums[:left] + minK(nums[left:], k - left)
# 测试
minK([32,21,82,66,14,56,80,9,44,69,21,60,66], k = 5)
[32, 21, 21, 9, 14]
堆排序
我们可以使用一个大小为 k 的最大堆（大顶堆），将数组中的元素依次入堆，当堆的大小超过 k 时，便将多出的元素从堆顶弹出
什么是堆——https://www.bilibili.com/video/BV1K4411X7fq?from=search&seid=15213146471374609847
class Solution:
def getLeastNumbers(self, arr, k):
if k == 0:
return list()
hp = [-x for x in arr[:k]] # python 里面是最小堆，也就是根节点是最小值，所以用负号逆转过来
heapq.heapify(hp) # 前k项先直接加入堆
for i in range(k, len(arr)):
if -hp[0] > arr[i]: # 如果当前值 > 堆里最大值
heapq.heappop(hp) # 就把最大值pop出来，把当前值加进去
heapq.heappush(hp, -arr[i])
ans = [-x for x in hp]
return ans
二叉堆
二叉堆的概念理解
理论部分：
用来做什么的？实现优先队列
用二叉堆来实现“优先队列”。优先队列和队列一样队尾进队首出，但是优先队列内有次序，优先级高的要作为VIP插队到前排。
当然我们可以简单的用插入+排序来实现优先队列，但是插入复杂度o(n)排序复杂度o(nlogn)。如果用二叉堆实现，出入队列复杂度都是o(logn)！
二叉堆的结构？完全二叉树
二叉堆是一颗完全二叉树，即节点都有左右两个子节点，最多可有一个节点例外。这个性质使得树可以用数组（比self.left&right这种链式存储更简单高效）来存储：
当第一个元素放在索引为0的位置上时：
-
索引为 i 的左孩子的索引为（2*i + 1）
-
索引为 i 的右孩子的索引为 （2*i + 2）
-
索引为 i 的父节点的索引为 （i - 1）// 2
堆次序？最大堆和最小堆
分为两种：最大堆和最小堆。
- 最大堆：父结点的键值总是大于或等于任何一个子节点的键值；
- 最小堆：父结点的键值总是小于或等于任何一个子节点的键值
实现二叉堆的功能
这里以最大堆为例
1. insert
先放到列表尾，如果新加入的数据项比父节点要大，把它与父节点互换位置——不断上浮直到正确位置。
class MaxHeap:
def __init__(self):
self.heapList = []
def insert(self, new):
self.heapList.append(new) # 1.插入到队尾
self.percUp() # 2.上浮操作
def percUp(self):
cur = len(self.heapList) - 1
while cur >= 1:
parent = (cur - 1) //2
if self.heapList[parent] < self.heapList[cur]:
self.heapList[parent], self.heapList[cur] = self.heapList[cur], self.heapList[parent]
cur = parent
else: break
def getMax(self):
return self.heapList[0]
hp = MaxHeap()
hp.insert(1);hp.insert(4);hp.insert(3);hp.insert(11);hp.insert(7);
print(hp.heapList)
print(hp.getMax())
[11, 7, 3, 1, 4]
11
2. delMax
跟节点是最大的，但困难的是移走根节点后如何恢复堆结构和堆次序——分两步走：
- 用最后一个节点来代替根节点。
- 将新节点“下沉”来恢复堆次序，同样通过交换——如果小于子节点，和左右子节点中较大的进行交换。
class MaxHeap(MaxHeap):
def maxChild(self, i): # 返回最大child 的索引
left, right = 2 * i + 1, 2 * i + 2
length = len(self.heapList) - 1
if length >= right: # 左右都存在
return left if self.heapList[left] > self.heapList[right] else right # return maxchild
if length < left: # 没有子节点
return None
else: # 只有左节点
return left
def percDown(self): # 下沉
cur = 0
while self.maxChild(cur):
maxchild = self.maxChild(cur)
if self.heapList[cur] < self.heapList[maxchild]:
self.heapList[cur], self.heapList[maxchild] = self.heapList[maxchild], self.heapList[cur]
cur = maxchild
def delMax(self):
tmp = self.heapList[0]
if len(self.heapList) == 1:
self.heapList.pop()
if len(self.heapList) > 1:
self.heapList[0] = self.heapList.pop()
self.percDown()
return tmp
利用del操作可以实现排序:
hp = MaxHeap()
hp.insert(1);hp.insert(4);hp.insert(7);hp.insert(11);hp.insert(3);
print(hp.heapList)
# 测试删除操作
res_sorted = []
while hp.heapList:
res_sorted.append(hp.delMax())
print(hp.heapList)
res_sorted # 每次删掉的都是最大值——组成从大到小的顺序list，完成了堆排序
[11, 7, 4, 1, 3]
[7, 3, 4, 1]
[4, 3, 1]
[3, 1]
[1]
[]
[11, 7, 4, 3, 1]
3.用自己的函数进行堆排序——min k 问题
输入：数字list + k
输出：最小的k个数字——用大根堆
def getLeastNumbers(arr, k):
if k >= len(arr):
return arr
hp = MaxHeap()
# 1.先加入k个
for i in range(k):
hp.insert(arr[i])
# 2.只保留当前最小的k个
for j in range(k, len(arr)):
if hp.getMax() > arr[j]:
hp.delMax()
hp.insert(arr[j])
return hp.heapList
arr = [32,21,82,66,14,56,80,9,44,69,21,60,66]
getLeastNumbers(arr, k = 4)
[21, 21, 14, 9]