NB三⼈组：快速排序堆排序归并排序
快速排序：
'''
快速排序：时间复杂度O(nlog2n)
利⽤归位函数进⾏递归调⽤
归位函数-左边都是⽐某元素⼩的，右边都是⽐某元素⼤的
快速排序⾄少⽐传统排序快100倍以上
快排弱点：
1.递归，⽐较消耗系统资源
2.最坏情况，如果⼀个倒序列表，时间复杂度O(n²)，可以在归位前，随机选择⼀个数和第⼀个数交换，来尽可能避免最坏情况的出现。
'''
import sys
import random
sys.setrecursionlimit(100000) # Python默认递归最⼤深度999，可以修改为100000
def partition(li, left, right):
# 归位函数
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp:
right -= 1
li[left] = li[right]
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left]
li[left] = tmp
return left
def _quick_sort(li, left, right):
# 递归
if left < right: # 保证⾄少有两个元素才继续归位，有⼀个或0个元素就结束归位
random_loc = random.randrange(left, right)
li[left], li[random_loc] = li[random_loc], li[left] # 随机交换位置，使快排最坏情况出现⼏率降到极低
mid = partition(li, left, right)
_quick_sort(li, left, mid - 1)
_quick_sort(li, mid + 1, right)
def quick_sort(li):
_quick_sort(li, 0, len(li) - 1)
# li = list(range(10000, 0, -1)) # 快速排序最坏情况
堆排序：
堆排序--什么是堆
堆：⼀种特殊的完全⼆叉树结构
⼤根堆：⼀颗完全⼆叉树，满⾜任意节点都⽐其孩⼦节点⼤
⼩根堆：⼀颗完全⼆叉树，满⾜任意节点都⽐其孩⼦节点⼩
堆的向下调整：
假设根节点的左右⼦树都是堆，但根节点不满⾜堆的性质，可以通过⼀次向下的调整将其变成⼀个堆
当根节点的左右⼦树都是堆时，可以通过⼀次向下的调整将其变换成⼀个堆
堆排序过程：
1、构造堆：调整最后⼀个节点和其⽗节点的⽗⼦关系，再调整前⼀个节点的⽗⼦关系，按从下->上，从右->左的顺序依次调整，直到变成⼀个堆
2、挨个出数：把堆顶元素拿出来（最⼤的），把最后⼀个⼦节点放到堆顶，再进⾏堆的向下调整变成⼀个堆，循环，直到全部取完
堆排序代码：
堆排序可以不⽤再开⼀个列表存有序值，可以记录堆的当前处理到的元素下标(第⼀次为最后⼀个⼦节点，依次向前循环记录)，
把堆顶元素拿出来，跟下标的值进⾏交换
def sift(li, low, high):
'''
堆排序--堆的向下调整，此处是实现⼀个 “⼤根堆”，⽗节点的值⼤于两个⼦节点的值
根节点的左右⼦树都是堆，但根节点不满⾜堆的性质，可以通过⼀次向下的调整将其变成⼀个堆 :param li: 列表
:param low: 堆顶节点的下标
:param high: 堆的最后⼀个节点的下标，⽤来判断下标是否越界
:return:
'''
# 技巧：⽤变量i和j保存当前的⽗节点下标和当前⼦节点中最⼤的数的下标，
# 如果i的值>j的值，就结束循环，否则，ij⼀直向下
i = low
j = 2 * low + 1
tmp = li[low] # 先把堆顶保存起来，⽤于后⾯进⾏移动
while j <= high:
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:
li[i] = tmp # 如果⽗亲⼤，把tmp放在i的位置上
break
else:
li[i] = tmp # 如果i到底了，就把tmp赋值给i
def heap_sort(li):
# 第⼀步：建堆，由下向上建
n = len(li)
for i in range((n - 2) // 2, -1, -1):
sift(li, i, n - 1) # 建堆的时候最多就三个节点，可以让high=len(li)-1
# 第⼆步：取数+向下调整
for i in range(n - 1, -1, -1):
li[0], li[i] = li[i], li[0]
sift(li, 0, i - 1)
import random
li = [i for i in range(100)]
random.shuffle(li)
heap_sort(li)
print(li)
堆排序代码
堆排序的时间复杂度为：O(nlog2n) 快速排序⽐堆排序稍微快⼀点
补充知识：
树的概念：
根节点、叶⼦节点
树的深度（⾼度）
树的度（最⼤分叉） 6
孩⼦节点/⽗节点
⼦树
⼆叉树：
度为2的树，每个⽗节点最多有两个⼦节点
满⼆叉树：
如果每⼀个层的节点数都达到最⼤值，则这个⼆叉树是满⼆叉树
完全⼆叉树：
叶⼦节点只能出现在最下层和次下层，且最下⾯⼀层的节点都集中
在该层最左边的若⼲位置的⼆叉树
⼆叉树存储⽅式：1、链式存储 2、顺序存储
import heapq
import random
# 可以实现⼀个叫“优先队列”的数据结构：⼤的先出，或⼩的先出
li = list(range(100))
random.shuffle(li)
heapq.heapify(li) # 建堆，默认为⼩根堆
m = heapq.heappop(li) # 每次弹出⼀个最⼩的元素，相当于弹出堆顶print(m)
heapq.heappush(li, -1)
m = heapq.heappop(li)
print(m)
>####
# 0
# -1
>####
Python内置的堆排序，可以实现“优先队列”
topk问题
需求：有n个数，设计算法取前k⼤的数。(k < n)
解决⽅法：
1、排序后切⽚ O(nlogn)
2、排序LowB三⼈组 O(kn)
3、堆排序 O(nlogk)
堆排序解决topk问题的思路：
1、取列表前k个元素建⽴⼀个⼩根堆。堆顶就是⽬前第k⼤的数
2、依次向后遍历原列表，对于列表中的元素，如果⼩于堆顶，则
忽略该元素；如果⼤于堆顶，则将堆顶更换为该元素，并且
进⾏⼀次向下调整
def sift(li, low, high):
# topk需要⼩根堆
i = low
j = 2 * low + 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:
li[i] = tmp
break
else:
li[i] = tmp
def topk(li, k):
# 1，建⼩根堆
heap = li[0:k]
for i in range((k - 2) // 2, -1, -1):
sift(heap, i, k - 1)
# 2，遍历
for i in range(k, len(li) - 1):
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap, 0, k - 1)
# 3，出数
for i in range(k - 1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
sift(heap, 0, i - 1)
return heap
import random
li = [i for i in range(100)]
random.shuffle(li)
hp = topk(li, 10)
print(hp)
topk的堆排序实现
归并排序过程：
归并：两个有序列表变成⼀个有序列表的过程
1、分解：长度n的列表分两半，两半分四半，...直到为1
2、归并：从1归并为2,2归并为4，...直到n
def merge(li, low, mid, high):
'''
归并⽅法，把两个有序列表归并成⼀个有序列表
[1,3,4,6,] [2,5,7,8,9,10,]
:
param li: 待归并的列表，两个列表合起来的
:param low: 第⼀个列表的起始下标
:param mid: 第⼀个列表的结束下标
:param high: 第⼆个列表的结束下标
:return:
'''
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 _merge_sort(li, low, high):
'''
:param li: 待排序的列表
:param low: 起始下标
:param high: 终⽌下标
快速排序python实现:return:
'''
if low < high: # 递归终⽌条件
mid = (low + high) // 2
_merge_sort(li, low, mid) # 归并左边
_merge_sort(li, mid + 1, high) # 归并右边
merge(li, low, mid, high) # 左右归并
def merge_sort(li):
_merge_sort(li, 0, len(li) - 1)
import random
li = [i for i in range(100)]
random.shuffle(li)
merge_sort(li)
print(li)
归并排序
NB三⼈组对⽐
时间⽽⾔：
快速排序 < 归并排序 < 堆排序
缺点：
快速排序：有最坏情况
堆排序：速度相对较慢
归并排序：占⽤内存
稳定性：相同的对象，排序后不改变其在原列表中的先后位置，就是稳定的，否则不稳定（跳着交换的不稳定，挨着交换的稳定）空间复杂度：是递归的空间复杂度，有递归的就存在空间复杂度
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
python算法详解
« 上一篇
Python中的代码性能分析与调优技巧
下一篇 »
发表评论