排序算法复杂度 #

1. 排序算法复杂度介绍
2. 排序算法的时间复杂度
3. 排序算法的空间复杂度

收获 #

学完本节内容，可以初步对排序算法的复杂度概念有一个大致的了解。

排序算法复杂度介绍 #

排序算法，是一种能将一串数据按照特定的排序方式进行排列的一种算法，一个排序算法的好坏，主要从时间复杂度，空间复杂度和稳定性来衡量。
评价排序算法优劣的标准主要是两条：一是算法的运算量，这主要是通过记录的比较次数和移动次数来反应，主要通过时间复杂度来评估；
另一个是执行算法所需要的附加存储单元的的多少，主要通过空间复杂度来进行评估。

排序算法的时间复杂度 #

时间复杂度是一个函数，语句总的执行次数与问题规模n的函数表达式，它描述了该算法的运行时间，考察的是当输入值大小趋近无穷时的情况。数学和计算机科学中使用这个大 O 符号用来标记不同”阶“的无穷大。
这里的无穷被认为是一个超越边界而增加的概念，而不是一个数。常见的时间复杂度 O(1)，O(log n)，O(n)，O(n log n)，O(n^2)等 ，计算时间复杂度的过程，常常需要分析一个算法运行过程中需要的基本操作，计量所有操作的数量。
时间是累积的，但是空间不是累积的，可重复使用。冒泡、选择、插入、归并、希尔、堆排序都是基于比较的排序，平均时间复杂度最低O(nlogn)；

排序算法的空间复杂度 #

和时间复杂度一样，常见的空间复杂度有 O(1)，O(log n)，O(n)，O(n log n)，O(n^2)等。实际写代码的过程中完全可以用空间来换取时间。
比如判断2017年之前的某一年是不是闰年，通常可以通过一个算法来解决。但还有另外一种做法就是将2017年之前的闰年保存到一个数组中。如果某一年存在这个数组中就是闰年，反之就不是。
一般来说时间复杂度和空间复杂度是矛盾的。到底优先考虑时间复杂度还是空间复杂度，取决于实际的应用场景。

小结 #

理解排序算法复杂度的定义
理解排序算法的时间复杂度和空间复杂度

习题 #

1. 习题1：说出几个评价排序算法好坏的指标
2. 习题2：简要描述排序算法的时间复杂度和空间复杂度的区别