排序算法第一篇-排序算法介绍

在面试中，现在无论大小公司都会有算法的。其中排序算法也是一种很常见的面试题。比如冒泡，快排等。这些，排序算法自己看了一次又一次，可是过一段时间，又忘掉了。所以，这次就把算法是怎么推导出来的，详细记录下来。看看这次多久还会忘记。

本文主要介绍排序算法的分类、时间复杂度、空间复杂。为了后面的学习做准备的。

通过本文学习，将收获到：排序算法分几类？什么是算法的时间复杂度？是怎么算出来的？什么是算法的空间复杂度？常见的时间复杂度比较。

如果这些您都已经知道了，可以不用耽误时间看了。

约定：

文中的n2表示的是n的2次方(n²),n^2也是表示n的2次方；

n3表示的是n的3次方；

n^k表示的是n的k次方；

long2n表示的是以2为底的对数。

本文出自：凯哥Java(微信：kaigejava)学习Java版数据结构与算法笔记。

一：介绍

排序又称排序算法(Sort Algorithm),排序是将一组数据，依据指定的顺序进行排序的过程。

二：分类

排序的分类分为两大类

2.1：内部排序

内部排序是指将需要处理的所有数据一次性都加载到内存中进行排序的。

如：冒泡、快排等这些算法都是内部排序的

2.2：外部排序

数据量过大，无法全部加载到内存中，需要借助于外部存储进行排序的。

如：数据库中数据8个G，内存只有4个G的这种。

2.3：参加分类如下图：

三：算法的时间复杂度

3.1：分类

衡量一个程序(算法)执行时间有两种方法

3.1.1：事后统计的方法

所谓的事后统计方法，顾名思义，就是程序(算法)已经写完了，运行后得到的结果。

这种方法虽然是可行的，但是有两个问题：

①：要想对设计的算法运行的性能进行评估，需要实际运行该程序(浪费时间)；

②：运行所得的时间统计严重依赖于机器的硬件、软件等环境因为。

这种方法有个严苛的要求：要在同一台机器在相同状态(软硬件)下运行，才能比较哪个算法更快。

3.1.2：事前估算的方法

通过分析某个算法的时间复杂度来判断哪个算法更优。

3.2：时间频度

概念：一个算法花费的时间与算法中语句执行的次数成正比。哪个算法中语句执行次数多，那么这个算法所花费的时间就多(这不废话吗)。

一个算法中语句执行次数称为语句频度或时间频度。记为：T(n).

(复杂的概念是，时间频度：一个算法执行所消耗的时间，从理论上是 不能算出来的，想要具体数值，必须要将程序上机运行测试才能知道。但是我们不可能也没必要对每个算法都上机进行测试的，只需要知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句执行的次数成正比的，哪个算法中语句执行次数多，那么这个程序花费的时间就多。一个算法中的语句执行次数称为语句频度或者时间频度，记为：T(n))

例如：我们知道的技术从1到100所有数字的和。这个就有两种算法。分别如下：

①：使用for循环，从1到100循环出来，然后累加出来。代码如下：

根据上面概念(注意对概念的理解,total和end这两行相对于for循环来说，可以忽略。后面我们还会详细讲解还会忽略哪些)，我们来看下这个算法的时间频度是多少呢？

在for循环中，实际需要执行101次(+1的原因是因为，在for循环的时候，需要做最后一次判断，才能推出。因此n个数的计算一共是n+1次操作)。所以其时间频度就是：T(n)=n+1;

我们再来看看第二种算法：

是不是很简单，只要一行代码就执行完成了。所以第二种算法的T(n)=1了。是不是很快呢？

时间频度是不是一眼就看出来了？是不是不用在代码运行下来比较运行时间了？

(ps：从上面简单的从1到100求和算法中，我们是不是感受到算法的魅力了？感受到编程之美了？)

3.3：时间复杂度

在上面3.2中提到的时间频度中,n称为问题的规模，当n不断变化的时候，时间频度T(n)也会不断变化。但是有时我们想知道它在变化的时候呈现什么样的规律呢？为此，我们引入了时间复杂度概念。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示。若有某个辅助函数f(n)，是的当n趋近于无穷大的时候，T(n)/f(n)的极限值为不等于零的藏书，则称为f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进的时间复杂度。简称时间复杂度。这就是大O法。

在计算时间复杂度的时候，我们会忽略以下几个数据值

3.3.1：忽略常数项

比如上面，我们计算1到100的第一种算法中，有两行int total=0；和 int end = 100;这两行代码，这个数值是2，我们一般计算时间复杂度的时候，会忽略这个常数项的。为什么呢？请看下面四个函数，随着n的增大而增大运行时间。

T(n) = 2n+20

T(n) = 2*n

T(n)=3n+10

T(n)=3*n

请看下图随这n的增大锁呈现的规律：

我们来看看，把这些数据使用折线图展示：

图例说明：上面两个是3*n及3n+10的，下面两个是2n及2n+10的

从上面两个图表中我们可以得到以下结论：

①：2n+20和2*n随着n的增加，执行曲线无限接近(折线图中下面两个)，常量值20可以忽略了

②：3n+10和3*n随着n的增加，执行曲线无限接近(折线图中上面两个)，常量值10可以忽略了

所以，综上所述，在计算程序(算法)时间复杂度的时候,常量值是可以忽略的

3.3.2：忽略低次项

请看下面四个函数，随着n的增大又会呈现什么规律吗？

T(n)=2n^2+3n+10

T(n)=2n^2

T(n)=n^2+5n+20

T(n)=n^2

说明：n^2表示n的2次方

我们来看看随着n的增加，运行所消耗的时间。如下图：

把上面数据，用折线图表示，如下图：

图例说明：上面两个是2n^2及2n^2+3n+10，下面两个是n^2及 n^2+5n+20

从上面两个图中我们可以得到如下结论：

①：2n^2+3n+10和2n^2随着n的增大，执行曲线无限接近，可以忽略低次项及常量项：3n+10

②：n^2+5n+20和n^2随着n的增大，执行曲线无限接近，可以忽略低次项及常量项：5n+20

综上所述，我们可以得到结论：在计算程序(算法)时间复杂度的时候，低次项(3n=3*n^1比n^2项数少)是可以忽略的

3.3.3：忽略系数

我们在来看看下面四个函数，看看它们随着n的增大呈现出什么样的规律

T(n)=3n^2+2n

T(n)=5n^2+7n

T(n)=n^3+5n

T(n)=6n^3+4n

随着n的增加，运行时间所消耗耗时如下图：

折线图如下：

从上图可以得到如下：

①：随着n值变大，5n^2+7n和3n^2+2n，执行曲线重合，说明这种情况下，系数5和3可以忽略；

②：n^3+5n和6n^3+4n，执行曲线分离，说明多少次防是关键

3.3.4：总结：

• 计算时间复杂度的时候忽略常数项、忽略低次项、忽略系数
• T(n)不同，但时间复杂度可能相同。

如：T(n)=n2+7n+6与T(n)=3n^2+2n+2它们的T(n)不同，但时间复杂相同，都为O(n^2).

• 计算时间复杂度的方法
  • 用常数1代替运行时间中的所有加法常数T(n)=n^2+7n+6 =>T(n)=n^2+7n+1
  • 修改后的运行次数函数中，只保留最高阶项T(n)=n^2+7n+1 => T（n）=n^2
  • 去除最高阶项的系数T(n)=n^2 =>T(n)=n^2 => O(n^2)

3.4：常见的时间复杂度

• 常数阶O(1)
• 对数阶O(log2n)
• 线性阶O(n)
• 线性对数阶O(nlog2n)
• 平方阶O(n^2)
• 立方阶O(n^3)
• K次方阶(n^k)
• 指数阶O(2^n)

各个时间复杂度复杂度折线图如下图：

总结：

• 常见算法时间复杂度由小到大依次为：

O(1)<O(log2n)<O(n)<O(nlong2n)<O(n^2)<O(n^3)<O(n^K)<O（2^n）。随着问题规模n的不断增大，上述时间复杂度不断增大,算法的执行效率也越低；

• 从上图折线图中，我们可以看出，程序(算法)尽可能的避免使用指数阶段的算法。

3.5：常见算法时间复杂度举例

3.5.1：常数阶O(1)

无论代码执行多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就是O(1)

(计算时间复杂度的时候，忽略常数项)

代码demo:

上述代码在执行的时候，消耗的时间并不是随着某个变量的增长而增长，那么无论这类代码有多长，即使有有几万几十万行，都是可以用O(1)来表示它的时间复杂度。

3.5.2：对数阶O(log2n)

代码敬上：

说明：

在while循环里面，没吃都是将i*2的。n的值是固定的，所以在i乘完之后，i距离n就越来越近了。假设循环x次之后，i就大于n了，此时这个循环就退出了。也就是说2的x次方等于n了。那么x=log2n。也就是说当循环了log2n次以后，代码就结束了。因此这个代码的时间复杂度就是

O(log2n)。

O(log2n)的这个2时间上是随着代码变化的。如果i = i*3，那么时间复杂度就是O(log3n)

回顾下log的理解(这是初中知识点)：

如果a的x次方等于N（a>0,且a≠1），那么熟x就叫做以a为底的对数(logarithm)，记作x=logaN.

其中，a叫做对数的底数，N叫做真数，x叫做“以a为底N的对数”。

3.5.3：线性阶O(n)

代码如下：

说明：

这段代码，for循环里面的代码会执行n次。因此它所消耗的时间随着n的变化而变化的，因此这类代码都是可以用O(n)来表示它的时间复杂度。

3.5.4：线性对数阶O(nlogn)

代码如下：

说明：

线性对数阶O(nlogN)其实非常容易理解的。将时间复杂度为O(logn)的代码循环了N次的话，那么它的时间复杂度就是n*O(logn)，也就是O(nlogN)

3.5.5：平方阶O(n2)

代码：

说明：

平方阶O(n2)就容易理解了。如果把O(n)的代码再嵌套循环一遍，它的时间复杂度就是O(n2)，

上图中的代码起始就是嵌套了2层n循环，它的时间复杂度就是O(n*n)，即时O(n2)。如果将其中一层循环的n修改成m，那么它的时间复杂度就变成了O(m*n).

3.5.6：立方阶O(n3)、K次方阶O(n^k)

说明：参考上面的O(n2)去理解就好了。O(n3)起始就相当于是三层n循环了。其他的一次类推。

3.6：平均时间复杂度和最坏时间复杂度

平均时间复杂度：

是指所有可能的输入实例均以概率出现的情况下，该算法的运行时间

最坏时间复杂度：

是指在最坏情况下的时间复杂度称为最坏时间复杂度。一般讨论时间复杂度均是最坏情况下的时间复杂度。

这样做的原因：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限。这就保证了算法的运行时间不会比最坏情况更长了。

平均时间复杂度和最坏时间复杂度是否一致，和算法有关。具体如下图：

排序算法	平均时间	最坏情况	稳定度	额外空间	备注
冒泡	O(n^2)	O(n^2)	稳定	O(1)	n小的时候比较好
交换	O(n^2)	O(n^2)	不稳定	O(1)	n小的时候比较好
选择	O(n^2)	O(n^2)	不稳定	O(1)	n小的时候比较好
插入	O(n^2)	O(n^2)	稳定	O(1)	大部分已经排序时比较好
基数	O(logRB)	O(logRB)	稳定	O(n)	B是真书(0-9) R是基数(个十百)
Shell(希尔)	O(nlogn)	O(n^s) 1<s<2	不稳定	O(1)	s是所选分组
快排	O(nlogn)	O(n^2)	不稳定	O(nlogn)	n大时候较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时候较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时候较好

四：算法的空间复杂度

空间复杂度介绍

• 类似于时间复杂度的讨论。一个算法的空间复杂度(Space Complexity)定义为该算法锁消耗的存储空间，它也是问题规模n的函数；
• 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用临时工作单元数与解决问题的规模n有关。它们随着n的增大而增大，当n较大的时候，将占用较多的存储单元(存储空间)。例如：在快排(快速排序)和归并排序算法就属于这种情况。
• 在做算法分析的时候，主要讨论的是时间的复杂度。因为从用户的使用体验上来看，更看重的是程序执行的速度的快慢。一般缓存产品(比如Redis)和技术排序算法本质就是拿空间换时间的。

下节预告：

下节我们将讲讲冒泡排序和选择排序。使用的是图解+代码一步一步推导出来演示的。欢迎大家一起学习。