本文主要是介绍2021-09-06，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

邓公数据结构与算法 第十四章排序

• 快速排序算法
• • 分而治之
  • 轴点
  • 构造轴点
  • 不变性与单调性
  • 快排性能分析
  • • 最好情况与最坏情况
  • 平均情况
• 快速排序：快速划分（ LGU 版）
• • 不变性
  • 单调性
  • 实现
  • 选取：众数
  • • 选取思想：减而治之
    • 算法实现

快速排序算法

分而治之

轴点

构造轴点

定义两个端点，不断向中间交替移动，U中元素比对后加入L或G中。

不变性与单调性

• 单调性：左右两端序列逐渐增加，中间序列逐渐减小
• 不变性：中间序列始终存在空缺（除了最后一步）

快排性能分析

最好情况与最坏情况

上图的时间分析公式如下。

平均情况

推导过程.

快速排序：快速划分（ LGU 版）

不变性

候选节点pivot 与L和G序列大小保持不变性

单调性

L,G序列实现单调递增，U体现单调递减

实现

注意if 语句后面为什么不用加 else{ k++；}以及swap（。。，elem【k++】），
因为存在 for（。。。;k++）可省去这两步

选取：众数

选取思想：减而治之

算法实现

这篇关于2021-09-06的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！