本文主要是介绍2021-09-06,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
邓公数据结构与算法 第十四章排序
- 快速排序算法
- 分而治之
- 轴点
- 构造轴点
- 不变性与单调性
- 快排性能分析
-
- 平均情况
- 快速排序:快速划分( LGU 版)
-
快速排序算法
分而治之
![在这里插入图片描述](/upload/202109/06/202109062339545610.png)
轴点
![在这里插入图片描述](/upload/202109/06/202109062339560419.png)
![在这里插入图片描述](/upload/202109/06/202109062339572417.png)
构造轴点
定义两个端点,不断向中间交替移动,U中元素比对后加入L或G中。
![在这里插入图片描述](/upload/202109/06/202109062339577461.png)
不变性与单调性
- 单调性:左右两端序列逐渐增加,中间序列逐渐减小
- 不变性:中间序列始终存在空缺(除了最后一步)
![在这里插入图片描述](/upload/202109/06/202109062339580600.png)
快排性能分析
最好情况与最坏情况
![在这里插入图片描述](/upload/202109/06/202109062339585957.png)
上图的时间分析公式如下。
![在这里插入图片描述](/upload/202109/06/202109062339588472.png)
平均情况
![在这里插入图片描述](/upload/202109/06/202109062339593828.png)
推导过程.
快速排序:快速划分( LGU 版)
不变性
候选节点pivot
与L和G序列大小保持不变性
![在这里插入图片描述](/upload/202109/06/202109062339597451.png)
单调性
L,G序列实现单调递增,U体现单调递减
![在这里插入图片描述](/upload/202109/06/202109062340000605.png)
实现
注意if 语句后面为什么不用加 else{ k++;}
以及swap(。。,elem【k++】)
,
因为存在 for(。。。;k++)
可省去这两步
![在这里插入图片描述](/upload/202109/06/202109062340005649.png)
选取:众数
选取思想:减而治之
![在这里插入图片描述](/upload/202109/06/202109062340008476.png)
算法实现
![在这里插入图片描述](/upload/202109/06/202109062340012412.png)
这篇关于2021-09-06的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!