各种排序算法的稳定性，时间复杂度和空间复杂度总结：
我们比较时间复杂度函数的情况：
时间复杂度函数O(n)的增长情况：
所以对于n较大的排序记，一般的选择都是时间复杂度为O(nlog2n)的排序 。
时间复杂度来说：
1.平方阶O(n2)排序
各类简单排序：直接插入排序，直接选择排序和冒泡排序；
2.线性对数阶O(nlog2n)排序
快速排序、堆排序和归并排序；
3.O(n1+§)排序，§是介于0和1之间的整数。
希尔排序；
4.线性阶O(n)排序
基数排序，此外还有桶、箱排序。
5.说明
当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O(n);
而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O(n2);
表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
稳定性来说：
1.排序算法的稳定性：若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，而称该算法是不稳定的。
2.稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，之一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以便面多余的比较；
3.稳定的排序算法：冒泡排序，直接插入排序，归并排序和基数排序；
4.不稳定的排序算法：选择排序，快速排序，希尔排序，堆排序；
选择排序算法的准则和依据：
1.准则：每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种 结合起来使用。
2.依据：影响排序算法的因素有很多，平均时间复杂度低的算法并不一定就是更优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需考虑的因素有以下4点：
1.待排序的记录数目n的大小；
2.记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
3.关键字的结构及其分布情况；
4.对排序稳定性的要求。
设待排序元素的个数为n。
1.当n较大，则因采用时间复杂度为O(nlog2n)的排序 ：快速排序、堆排序或归并排序；
快速排序：是目前基于比较的内部排序中被认为是更好的 ，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序：如果内存空间允许切要求稳定性的；
归并排序：它有一定数量的数据移动，所以我们可以与插入排序结合，先获得一定长度的序列，然后再合并，在效率上有所提高。
2.当n较小，可采用直接插入或直接选择排序。
直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。
直接选择排序：元素分布有序，如果不要求稳定性，选直接选择排序。
3.一般不使用或不直接使用传统的冒泡排序。
4.基数排序：它是一种稳定的排序算法，但有一定的局限性：
关键字可分解
记录的关键字位数较少，如果密集更好
如果是数字时，更好是无符号的，否则将增加相关的映射复杂度，可先将其正负分开排序。
