排序算法之比较排序

本贴最后更新于 2416 天前,其中的信息可能已经天翻地覆

    本文主要是记录在学习《算法笔记》等书籍中的排序算法,排序算法按照是否基于“比较”操作可以分为比较排序和非比较排序两大类,这一篇文章主要是记录比较排序算法时的知识点和相关总结!

一、概述

    排序算法是非常基础和重要的一类算法,本文主要是介绍比较排序算法的思想,主要涉及到冒泡排序、梳排序、堆排序、归并排序(递归版与非递归版)、快速排序(递归版与非递归版)、内省排序、Timsort!

(1)基于比较的排序算法,也即根据待排序对象之间的大小关系进行排序的,比较规则必然是需要满足传递性和全序性!

    排序算法下界 O(nlog2(n))推导:

2^f(n) >= n!

=>

f(n) >= log2(n!) = nlog2(n)

(2)“合并多个有序列”问题

(3)“前 k 个小数”问题

二、冒泡排序与梳排序

1、冒泡排序

    冒泡排序是最最最基本的一个排序算法,如果连这个都手写不出来伪代码,那也还是不要做程序员了早点滚蛋算了!

    思想:调整相邻两个对象的位置,每进行一次内循环,就可以将最大值调整到最后!

因此,在经过 n-1 次内循环之后就可以得到整个完整的有序列!时间复杂度 O(n^2)

伪代码如下:

for i = 1,2,……,n-1 do for j = 1,2,……,n-i do if a(j) > a(j+1) then 交换a(j) 和 a(j+1) end if end for end for

2、梳排序

    梳排序是冒泡排序的一种改进,虽然没有很好的理论结果,但是实际效果非常好!

    思想:对固定距离处的对象进行比较和交换,即在冒泡排序之前做了一些排序工作!

固定距离是待排序列长度 n 除以 1.3 向下取整(若小于 1 则取 1)!时间复杂度 O(nlog1.3(n))

伪代码如下:

j <- n, s <- 1.3, flag <- false while j > 1 或者 flag = true do i <- 0, j <- max{j/s,1}, flag <- false while i + j <= n do if a(i) > a(i+j) then 交换a(j) 和 a(j+1) flag <- true end if i <- i+1 end while end while

三、堆排序

    堆排序,即借助堆这个数据结构来进行排序的!

    思想:对全部待排序对象建堆,然后反复查找并删除最小值(最大值)!

    应用

(1)多个序列合并问题:n 个有序列,第 i 个序列长度为 m(i)

    将每个有序列中的第 1 个对象即最小值放入堆中,进行建堆 => 然后查找并删除最小值 => 若最小值来自第 j 个序列,则将第 j 序列中的下一个尚未处理的对象放入堆中 => 继续查找并删除最小值 => 直至全部比较完

    建堆时间复杂度 O(n),每次查找并删除最小值的复杂度是 O(log(n))共需要次数 sum[m(i)]「i=1……n」,每次插入的复杂度是 O(log(n))共需要次数 sum[m(i)-1]「i=1……n」 => 总的时间复杂度是 O(sum[m(i)log(n)]「i=1……n」)

(2)查找前 k 个数问题:    将每个有序列中的第 1 个对象即最小值放入堆中,进行建堆 => 然后查找并删除最小值 => 若最小值来自第 j 个序列,则将第 j 序列中的下一个尚未处理的对象放入堆中 => 继续查找并删除最小值 => 直至第 k 个最小值即可

    建堆时间复杂度 O(n),,每次查找并删除最小值的复杂度是 O(log(n))共需要次数 k => 总的时间复杂度是 O(n+klog(n))

四、归并排序

五、快速排序

六、内省排序

七、Timsort

  • 算法
    424 引用 • 254 回帖 • 24 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • OneDrive
    2 引用 • 6 关注
  • B3log

    B3log 是一个开源组织,名字来源于“Bulletin Board Blog”缩写,目标是将独立博客与论坛结合,形成一种新的网络社区体验,详细请看 B3log 构思。目前 B3log 已经开源了多款产品:SymSoloVditor思源笔记

    1063 引用 • 3455 回帖 • 150 关注
  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 50 关注
  • 职场

    找到自己的位置,萌新烦恼少。

    127 引用 • 1708 回帖
  • SendCloud

    SendCloud 由搜狐武汉研发中心孵化的项目,是致力于为开发者提供高质量的触发邮件服务的云端邮件发送平台,为开发者提供便利的 API 接口来调用服务,让邮件准确迅速到达用户收件箱并获得强大的追踪数据。

    2 引用 • 8 回帖 • 507 关注
  • 笔记

    好记性不如烂笔头。

    311 引用 • 794 回帖
  • Thymeleaf

    Thymeleaf 是一款用于渲染 XML/XHTML/HTML5 内容的模板引擎。类似 Velocity、 FreeMarker 等,它也可以轻易的与 Spring 等 Web 框架进行集成作为 Web 应用的模板引擎。与其它模板引擎相比,Thymeleaf 最大的特点是能够直接在浏览器中打开并正确显示模板页面,而不需要启动整个 Web 应用。

    11 引用 • 19 回帖 • 394 关注
  • 旅游

    希望你我能在旅途中找到人生的下一站。

    98 引用 • 903 回帖 • 1 关注
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 696 关注
  • Git

    Git 是 Linux Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。

    211 引用 • 358 回帖 • 1 关注
  • 开源中国

    开源中国是目前中国最大的开源技术社区。传播开源的理念,推广开源项目,为 IT 开发者提供了一个发现、使用、并交流开源技术的平台。目前开源中国社区已收录超过两万款开源软件。

    7 引用 • 86 回帖
  • BND

    BND(Baidu Netdisk Downloader)是一款图形界面的百度网盘不限速下载器,支持 Windows、Linux 和 Mac,详细介绍请看这里

    107 引用 • 1281 回帖 • 34 关注
  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    345 引用 • 755 回帖
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    240 引用 • 224 回帖
  • Bug

    Bug 本意是指臭虫、缺陷、损坏、犯贫、窃听器、小虫等。现在人们把在程序中一些缺陷或问题统称为 bug(漏洞)。

    76 引用 • 1742 回帖 • 1 关注
  • Jenkins

    Jenkins 是一套开源的持续集成工具。它提供了非常丰富的插件,让构建、部署、自动化集成项目变得简单易用。

    54 引用 • 37 回帖
  • Windows

    Microsoft Windows 是美国微软公司研发的一套操作系统,它问世于 1985 年,起初仅仅是 Microsoft-DOS 模拟环境,后续的系统版本由于微软不断的更新升级,不但易用,也慢慢的成为家家户户人们最喜爱的操作系统。

    229 引用 • 476 回帖
  • GAE

    Google App Engine(GAE)是 Google 管理的数据中心中用于 WEB 应用程序的开发和托管的平台。2008 年 4 月 发布第一个测试版本。目前支持 Python、Java 和 Go 开发部署。全球已有数十万的开发者在其上开发了众多的应用。

    14 引用 • 42 回帖 • 823 关注
  • Flume

    Flume 是一套分布式的、可靠的,可用于有效地收集、聚合和搬运大量日志数据的服务架构。

    9 引用 • 6 回帖 • 661 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 86 关注
  • sts
    2 引用 • 2 回帖 • 241 关注
  • Sandbox

    如果帖子标签含有 Sandbox ,则该帖子会被视为“测试帖”,主要用于测试社区功能,排查 bug 等,该标签下内容不定期进行清理。

    440 引用 • 1238 回帖 • 591 关注
  • React

    React 是 Facebook 开源的一个用于构建 UI 的 JavaScript 库。

    192 引用 • 291 回帖 • 367 关注
  • 以太坊

    以太坊(Ethereum)并不是一个机构,而是一款能够在区块链上实现智能合约、开源的底层系统。以太坊是一个平台和一种编程语言 Solidity,使开发人员能够建立和发布下一代去中心化应用。 以太坊可以用来编程、分散、担保和交易任何事物:投票、域名、金融交易所、众筹、公司管理、合同和知识产权等等。

    34 引用 • 367 回帖 • 3 关注
  • 微软

    微软是一家美国跨国科技公司,也是世界 PC 软件开发的先导,由比尔·盖茨与保罗·艾伦创办于 1975 年,公司总部设立在华盛顿州的雷德蒙德(Redmond,邻近西雅图)。以研发、制造、授权和提供广泛的电脑软件服务业务为主。

    8 引用 • 44 回帖 • 2 关注
  • 房星科技

    房星网,我们不和没有钱的程序员谈理想,我们要让程序员又有理想又有钱。我们有雄厚的房地产行业线下资源,遍布昆明全城的 100 家门店、四千地产经纪人是我们坚实的后盾。

    6 引用 • 141 回帖 • 605 关注
  • 反馈

    Communication channel for makers and users.

    120 引用 • 906 回帖 • 277 关注