快速排序和堆排序算法的比较与详解_快速排序和堆栈排序区别

快速排序：

原理：

1、通过partion函数将列表最左边的数归位（归位的这个数左边的数都是比他小的，右边都是比他大的数）

2、通过partion函数递归，将每一个数归位

 

 

partion函数解读:

 关键问题：
left<right:保证了至少有两个数，当left和right相等时就把保存的那个数写入（归位）；

循环里面为什么要写left<right判断？

首先、假设tmp右边的所有数都比他大 ，这时就会让left指针和right指针指到一起，这里不写条件right指针就会越界（找不到值了！）,所以这里要加上;其次、当右边找到了比tmp小的数，就会将这个数写到左边的left指针指向的位置上，然后循环调整；最后、这个条件不成立的时候恰好就是left和right指针指向同一个位置的时候，这个位置就是我们要放之前存tmp的位置。

递归：

不断分为两部分，让每个数都归位。

时间复杂度：
O(nlogn)    快速排序默认是最快的排序

快速排序优化：

假如：遇到最坏的情况（9,8,7....）

这时就要考虑修改递归的最大深度了； 

解决方法<生成一个随机数将他对应的值与tmp交换/降低了上面这种随机事件发生的概率>

堆排序：主要就是三步（向下调整、建立堆、挨个出数）

先来了解一些树（一种数据结构）的知识：

 根节点：A;

叶子的节点：位于最外层的位置 BCHIPQKLMN;

树的深度（层数）;

树的度（往下的最多的叉数） 例如这里：上面的数的度就是6;

孩子节点在父节点下面，父亲节点在孩子节点上面;

子树：类似于包含在树树里的小枝丫。

 

 通俗来说：完全二叉树就是最后一层可以的左边部分按顺序不能缺失，右边的部分按顺序可以缺失，除了最后一层其他节点下面都有两个叉；而满二叉树就是对应的每一个节点下面都有两个叉，最后一层是满的。

 堆排序主要采用顺序存储方式。

 父亲：i

左孩子：2*i+1

右孩子：2*i+2

---

孩子：n（不管左孩子还是右孩子）

父亲:(n-1)//2  

 本文主要是用大根堆（父亲比孩子大）

 向下调整的函数优化：

 

堆排序的本质：调整 构建堆 挨个出数

Python第三方库heapq:

 

 最后测试一下快排和堆排谁更快：

通过在函数上面安装装饰器检测两种排序算法的效率 

装饰器安装代码： 

 很显然是快速排序快！！！

不相信的小伙伴可以在自己电脑上试试看，分别调用执行快排和堆排函数注意要修改递归的最大深度！！！