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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!