【数据结构(六)】排序算法介绍和算法的复杂度计算（1）

1. 排序算法的介绍

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

1.1. 排序的分类

1. 内部排序:
   指将需要处理的所有数据都加载到**内部存储器(内存)**中进行排序。
2. 外部排序法：
   数据量过大，无法全部加载到内存中，需要借助**外部存储(文件等)**进行排序。

常见的排序算法分类(见下图):

2. 算法的时间复杂度

2.1. 度量一个程序(算法)执行时间的两种方法

1. 事后统计的方法
   这种方法可行, 但是有两个问题：
   一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；
   二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。

2. 事前估算的方法
   通过分析某个算法的时间复杂度来判断哪个算法更优。

2.2. 时间频度

基本介绍：

时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 $T(n)$。

举例说明-基本案例

比如计算 1-100 所有数字之和, 可设计两种算法：

2.2.1. 忽略常数项

结论:
① $2n+20$ 和 $2n$ 随着 $n$ 变大，执行曲线无限接近，$20$ 可以忽略
② $3n+10$ 和 $3n$ 随着 $n$ 变大，执行曲线无限接近，$10$ 可以忽略

2.2.2. 忽略低次项

结论:
① $2n^2+3n+10$ 和 $2n^2$ ，随着 $n$ 变大， 执行曲线无限接近, 可以忽略 $3n+10$
② $n^2+5n+20$ 和 $n^2$ ，随着 $n$ 变大，执行曲线无限接近, 可以忽略 $5n+20$

2.2.2. 忽略系数

结论:
① 随着 $n$ 值变大，$5n^2+7n$ 和 $3n^2+2n$ ，执行曲线重合, 说明 这种情况下, $5$ 和 $3$ 可以忽略。
② 而 $n^3+5n$ 和 $6n^3+4n$ ，执行曲线分离，说明多少次方是关键

2.3. 时间复杂度

    一般情况下，算法中的基本操作语句的重复执行次数是问题规模 $n$ 的某个函数，用 $T(n)$表示，若有某个辅助函数 $f(n)$，使得当 $n$ 趋近于无穷大时，$\frac{T(n)}{f(n)}$ 的极限值为不等于零的常数，则称 $f(n)$是 $T(n)$的同数量级函数。记作 $T(n)=Ｏ(f(n))$，称$Ｏ(f(n))$ 为算法的渐进时间复杂度，简称时间复杂度。
    
    $T(n)$ 不同，但时间复杂度可能相同。 如：$T(n)=n^2+7n+6$ 与 $T(n)=3n^2+2n+2$ 它们的 $T(n)$ 不同，但时间复杂度相同，都为 $O(n^2)$。

计算时间复杂度的方法：
（以 $T(n)=n^2+7n+6$ 为例）
①用常数 $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)$

2.4. 常见的时间复杂度

1. 常数阶 $O(1)$
2. 对数阶 $O(lo{g}_{2}n)$（其中，$log$以2为底，也可以是以3、4、5……为底）
3. 线性阶 $O(n)$
4. 线性对数阶 $O(nlo{g}_{2}n)$（其中，$log$以2为底，也可以是以3、4、5……为底）
5. 平方阶 $O(n^2)$
6. 立方阶 $O(n^3)$
7. k 次方阶 $O(n^k)$
8. 指数阶 $O(2^n)$

常见的时间复杂度对应的图：

说明：

1. 常见的算法时间复杂度由小到大依次为：$O(1)$＜$O(lo{g}_{2}n)$＜$O(n)$＜$O(nlo{g}_{2}n$)＜$O(n^2)$＜$O(n^3)$＜$O(n^k)$ ＜$O(2^n)$ ，随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
2. 从图中可见，我们应该尽可能避免使用指数阶的算法。

① 常数阶 $O(1)$

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

int i = 1;
int j =2;
++i;
j++;
int m = i + j;

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

② 对数阶 $O(lo{g}_{2}n)$

int i =1;
while(i < n){
   
	i= i * 2;
}

说明：
    在while循环里面，每次都将 $i$ 乘以 $2$，乘完之后，$i$ 距离 $n$ 就越来越近了。假设循环 $x$ 次之后，$i$ 就大于 $n$ 了，此时这个循环就退出了，也就是说 $2$ 的 $x$ 次方等于 $n$，那么 $x=lo{g}_{2}n$也就是说当循环 $lo{g}_{2}n$ 次以后，这个代码就结束了。因此这个代码的时间复杂度为：$O(lo{g}_{2}n)$ 。
    $O(lo{g}_{2}n)$ 中的2是根据代码变化的，若 $i=i\ast 3$ ，则是 $O(lo{g}_{3}n)$。

    如果 $N=a^x(a>0,a\ne 1)$，即 $a$ 的 $x$ 次方等于 $N(a>0,a\ne 1)$，那么数 $x$ 叫做以 $a$ 为底 $N$ 的对数$(logarithm)$，记作 $x=lo{g}_{a}N$ 。其中，$a$ 叫做对数的底数，$N$ 叫做真数，$x$ 叫做 “以 $a$ 为底 $N$ 的对数” 。

③ 线性阶 $O(n)$

for(i = 1; i <= n; ++i){
   
	j = i;
	j++;
}

说明：
    这段代码，for循环 里面的代码会执行 $n$ 遍，因此它消耗的时间是随着 $n$ 的变化而变化的，因此这类代码都可以用 $O(n)$ 来表示它的时间复杂度。$T(n)=n+1$ --> $O(n)$

④ 线性对数阶 $O(nlo{g}_{2}n)$

for(m = 1; m < n; m++){
   
	i = 1;
	while(i < n){
   
		i = i * 2;
	}
}

说明：
    线性对数阶 $O(nlo{g}_{2}N)$ 其实非常容易理解，将时间复杂度为 $O(lo{g}_{2}n)$ 的代码循环 $N$ 遍的话，那么它的时间复杂度就是 $n\ast O(lo{g}_{2}N)$，也就是了$O(nlo{g}_{2}N)$

⑤ 平方阶 $O(n^2)$

for(x = 1; x <= n; x++){
   
	for(i = 1; i <= n; i++){
   
		j = i;
		j++;
	}
}

说明：
    平方阶$O(n^2)$ 就更容易理解了，如果把 $O(n)$ 的代码再嵌套循环一遍，它的时间复杂度就是 $O(n^2)$，这段代码其实就是嵌套了2层 $n$ 循环，它的时间复杂度就是 $O(n\ast n)$，即 $O(n^2)$ 如果将其中一层循环的 $n$ 改成$m$ ，那它的时间复杂度就变成了 $O(m\ast n)$

⑥ 立方阶 $O(n^3)$ 和 ⑦ k 次方阶 $O(n^k)$

说明： 参考上面的 $O(n^2)$ 去理解就好了，$O(n^3)$ 相当于3层 $n$ 循环，其它的类似。

2.5. 平均时间复杂度和最坏时间复杂度

    平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
    最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

平均时间复杂度和最坏时间复杂度是否一致，和算法有关(如下图所示)。

3. 算法的空间复杂度

    类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模 $n$ 的函数。
    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模 $n$ 有关，它随着 $n$ 的增大而增大，当 $n$ 较大时，将占用较多的存储单元，例如快速排序、归并排序、 基数排序就属于这种情况。

    在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间。