排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源，今天我们一起来了解下几种排序算法的时间空间复杂度。

1、冒泡排序不管序列是怎样，都是要比较n(n-1)/2次的，最好、最坏、平均时间复杂度都为O(n²)，需要一个临时变量用来交换数组内数据位置，所以空间复杂度为O(1)。有很多人说冒泡排序的最优的时间复杂度为O(n),其实这是在代码中使用一个标志位来判断是否已经排序好的,是冒泡排序的优化版，如果元素已经排序好，那么循环一次就直接退出。

2、选择排序是冒泡排序的改进，同样选择排序无论序列是怎样的都是要比较n(n-1)/2次的，最好、最坏、平均时间复杂度也都为O(n²)，需要一个临时变量用来交换数组内数据位置，所以空间复杂度为O(1)。

3、插入排序不同，如果序列是完全有序的，插入排序只要比较n次，无需移动时间复杂度为O(n)，如果序列是逆序的，插入排序要比较O(n²)和移动O(n²)，所以平均复杂度为O(n²)，最好为O(n)，最坏为O(n²)，排序过程中只要一个辅助空间，所以空间复杂度O(1)。

4、快速排序的时间复杂度最好是O(nlogn),平均也是O(nlogn),最坏情况是序列本来就是有序的，此时时间复杂度为O(n²)，快速排序的空间复杂度可以理解为递归的深度，而递归的实现依靠栈，平均需要递归logn次，所以平均空间复杂度为O(logn)。

5、归并排序需要一个临时temp[]来储存归并的结果，空间复杂度为O(n)，时间复杂度为O(nlogn)，可以将空间复杂度由O(n)降低至O(1)，然而相对的时间复杂度则由O(nlogn)升至O(n²)。

6、希尔排序的时间复杂度分析及其复杂，有的增量序列的复杂度至今还没人能够证明出来，只需要记住结论就行，{1,2,4,8,...}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n²)，Hibbard提出了另一个增量序列{1,3,7，...,2^k-1}，这种序列的时间复杂度(最坏情形)为O(n^1.5)，Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3）,其中最好的一个序列是{1,5,19,41,109,...}，需要一个临时变量用来交换数组内数据位置，所以空间复杂度为O(1)。

7、堆排序的时间复杂度，主要在初始化堆过程和每次选取最大数后重新建堆的过程，初始化建堆时的时间复杂度为O(n)，更改堆元素后重建堆的时间复杂度为O(nlogn)，所以堆排序的平均、最好、最坏时间复杂度都为O(nlogn)，堆排序是就地排序，空间复杂度为常数O(1)。

8、基数排序对于n个记录，执行一次分配和收集的时间为O(n+r)，如果关键字有d位，则要执行d遍，所以总的时间复杂度为O(d(n+r))。该算法的空间复杂度就是在分配元素时，使用的桶空间，空间复杂度为O(r+n)=O(n)