常见排序算法归档

  • A+
所属分类:计算机基础
摘要这一篇作为排序算法的归档,其中把每种排序算法都有很详细的介绍。

文章目录(Table of Contents)

简介

最近找到一个把排序算法归纳的很全的博客,故在这里记录一下。

链接如下 : 常见排序算法【归档】, 界面大概是下面这个样子的。

常见排序算法归档

下面用文字简单介绍一些堆排序和快速排序,内容也是来自上面的网站的,方便快速回忆。

堆排序

堆排序就是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束。

在堆中定义以下几种操作:

  • 最大堆调整(Max-Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点;
  • 创建最大堆(Build-Max-Heap):将堆所有数据重新排序,使其成为最大堆;
  • 堆排序(Heap-Sort):移除位在第一个数据的根节点,并做最大堆调整的递归运算;

快速排序

快速排序用到分治法。

分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

利用分治法可将快速排序的分为三步:

  • 在数据集之中,选择一个元素作为” 基准”(pivot)。
  • 所有小于” 基准” 的元素,都移到” 基准” 的左边;所有大于” 基准” 的元素,都移到” 基准” 的右边。这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
  • 对” 基准” 左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

总结

常见排序算法归档 常见排序算法归档
  • 微信公众号
  • 关注微信公众号
  • weinxin
  • QQ群
  • 我们的QQ群号
  • weinxin
王 茂南

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: