第7章 排序算法

在本章里,我们讨论对数组元素的排序问题。

为了简化问题,我们会假设数组中只包含整数。本章大部分内容假设排序能在内存完成,以便数组元素的个数相对较小,比如少于几百万个。不能在内存中执行、必须在硬盘上完成的排序也是非常重要的。本章结尾会讨论这类外部排序。

我们对内部排序的探讨将展示:

  • 存在若干种容易的O(N^2)排序算法,比如插入排序。
  • 存在一种叫希尔的排序,编码很简单,运行时间为O(N^2),在实践中很有效。
  • 存在若干种稍微复杂点的O(N\log N)的排序算法。
  • 任何通用型的排序算法都需要\Omega(N\log N)次比较。

本章剩余部分会描述和分析各种各样的排序算法。这些算法包含了有趣且重要的代码优化思路和算法设计思路。

排序算法也是一类能够被精确分析的算法。我们会在合适的地方做尽可能多的分析。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 本文首发于我的个人博客:尾尾部落 排序算法是最经典的算法知识。因为其实现代码短,应该广,在面试中经常会问到排序算法...
    繁著阅读 4,592评论 3 119
  • 搞懂基本排序算法 上篇文章写了关于 Java 内部类的基本知识,感兴趣的朋友可以去看一下:搞懂 JAVA 内部类;...
    醒着的码者阅读 1,242评论 3 4
  • 最近在学习算法,对此也做一个总结: 排序对于任何一个程序员来说,可能都不会陌生。你学的第一个算法,可能就是排序。大...
    被吹落的风阅读 3,214评论 0 28
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    zwb_jianshu阅读 1,257评论 0 0
  • 波浪线在Word文档中有红色波浪线和绿色波浪线,它们的意思分别如下。 红色波浪线:word的系统认为该处可能存在单...
    吾极阅读 681评论 0 0