排序NB三人组（快速排序/堆排序/归并排序）
2021-01-19 17:15
标签：思路 现在 组成 col while 二叉树 nbsp pre span 时间复杂度：O(nlogn) 思路：取一个元素p(第一个元素)，使其归位；列表被p分成两部分，左边都比p小，右边都比p大；递归完成排序。 树：树是一种数据结构，可以递归定义的数据结构，树由n个节点组成的集合： 如果 n=0 ，那这是一颗空树； 如果 n>0 ，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。 树的深度（高度）；树的度（等于多少个子节点） 二叉树：度不超过2的树；每个节点最多由两个孩子节点；两个孩子节点被区分为左孩子节点和右孩子节点。 满二叉树：一个二叉树，如果每一层的节点都达到最大值，则这个二叉树就是满二叉树。 完全二叉树：叶子节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树。 排序NB三人组（快速排序/堆排序/归并排序） 标签：思路 现在 组成 col while 二叉树 nbsp pre span 原文地址：https://www.cnblogs.com/xiangxiaolin/p/12905846.html快速排序
def partition(li, left, right):
tmp = li[left]
while left right:
while left and li[right] >= tmp: # 从右边找比tmp小的数
right -= 1 # 往左走一步
li[left] = li[right] # 把右边的值写到左边空位上
while left and li[left] tmp:
left += 1
li[right] = li[left] # 把左边的值写到右边空位上
li[left] = tmp # tmp归位
return left
def _quick_sort(li, left, right):
if left # 至少两个元素
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)
堆排序
文章标题：排序NB三人组（快速排序/堆排序/归并排序）
文章链接：http://soscw.com/index.php/essay/44162.html