4种常见排序方式的时间,空间复杂度（冒泡排序，插入排序，选择排序，快速排序）

时间复杂度的定义：

如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数T(n)称为这一算法的“时间复杂性”。概念：

在进行时间复杂度的计算时：
1，算法完成工作最少需要多少基本操作，即最优时间复杂度
2，算法完成工作最多需要多少基本操作，即最坏时间复杂度
3，算法完成工作平均需要多少基本操作，即平均时间复杂度
1 对于最优时间复杂度，其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。
2 对于最优时间复杂度，其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。
3 对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能并不均匀而难以计算。
对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。

时间复杂度计算：

时间复杂度的几条基本计算规则：
基本操作，即只有常数项，认为其时间复杂度为O(1)
顺序结构，时间复杂度按加法进行计算
循环结构，时间复杂度按乘法进行计算
分支结构，时间复杂度取最大值
判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略
在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度（在这里我们只分析最坏的时间复杂度）。

空间复杂度的概念：

和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，也是使用大O表示法。

空间复杂度的计算：

和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，也是使用大O表示法。

1、常量空间
存储空间大小固定，和输入没有关系时，空间复杂度是O(1)

2、线性空间
算法中定义了一个线性集合，如一个列表，并且集合大小和输入规模n成正比，空间复杂度记为O(n)

3、二维空间
算法中定义了一个二维列表集合，并且集合的长和宽都和输入规模n成正比，空间复杂度记为O(nn)/O（nm)

4、递归空间
递归过程就是一个进栈和出栈的过程，当进入一个新函数时，进行入栈操作，把调用的函数和参数信息压入栈中；当函数返回时，执行出栈。
递归的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。

1，冒泡排序：

时间复杂度：
若初始文件是反序的，需要进行N趟排序。每趟排序要进行 C = N-1次关键字的比较(1≤i≤N-1)和总共(Mmax = (N*(N-1))/2)次的移动（移动次数由乱序对的个数决定，即多少对元素顺序不对，如 1 3 4 2 5 中共有(3,2)、(4,2)两个乱序对），在这种情况下，比较和移动次数均达到最大值（Cmax =N*(N-1) + Mmax=(N*(N-1))/2 = O(N^2)）。所以，冒泡排序的最坏时间复杂度为O(N ^2),也就是冒泡排序的总共执行次数；
空间复杂度:

空间复杂度就是在交换元素时那个临时变量所占的内存空间；
最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；
最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；
平均的空间复杂度为：O(1)；

2，插入排序：

时间复杂度：
最坏时间复杂度—Θ(n2)
如果数组是倒序的，每次插入就相当于在数组的第一个位置插入数据。比如将 0 插入到数组[2, 3, 5, 7, 11]中，因为数组中的元素都大于 0 ，所以
需要需要与数组中的所有元素进行比较并以此将元素向右移动，最终将0 插入到数组第一个位置。通常来讲，假设数组的length为n，将元素插入到数组的操作称为insert，被插入元素Key需要与数组元素进行比较的此时称为K。 那么在这种情况下，将某一个元素插入到数组时 k = n - 1。
综上所述，在插入排序的流程中，第一次进行insert时K = 1，第二次K = 2， 第三次K = 3…最后一次K = n - 1.因此插入排序所用的总的时间为：
1 + 2 + 3 + ⋯ (n−1) = (1+2+3+⋯+(n−1)) = n2 / 2 - n / 2 用big-Θ表示法表示就是 Θ(n2)
空间复杂度：
空间复杂度：直接插入排序中只使用了i,j这两个辅助元素，与问题规模无关，空间复杂度为O(1)；

3，选择排序：

时间复杂度:
最差的时候，也就初始化降序或者升序是，需要交换n-1次，基于最终的排序时间是比较与交换的次数总和，因此，总的时间复杂度依然为O(n²)
空间复杂度：
空间复杂度：最差的情况下（全部元素都要重新排序）复杂度为：O(n );

4，快速排序：

快速排序其实是在冒泡排序的基础上做出的一个改进.快速排序算法利用的是一趟快速排序,基本内容是选择一个数作为准基数,然后利用这个准基数将遗传数据分为两个部分,第一部分比这个准基数小,都放在准基数的左边,第二部分都比这个准基数大,放在准基数的右边.
时间复杂度：
在最坏的情况下，待排序的序列为正序或者逆序，快速排序的时间复杂度和冒泡排序的时间复杂度一致为O(n^2)

空间复杂度:
其实这个空间复杂度不太好计算，因为有的人使用的是非就地排序，那样就不好计算了（因为有的人用到了辅助数组，所以这就要计算到你的元素个数了）；我就分析下就地快速排序的空间复杂度吧；
首先就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；
最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况