Java教程

2021-09-06

本文主要是介绍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的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航