Kotlin程序员必备的面试算法宝典

各种排序算法的比较如下表所示。

从该表中可以得到以下几个方面的结论：

1）简单地说，所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，就称这种排序方法是稳定的，反之就是非稳定的。例如，一组数排序前是a1，a2，a3，a4，a5，其中a2=a4，经过某种排序后为a1，a2，a4，a3，a5，则说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1，a4，a2，a3，a5就不是稳定的了。各种排序算法中稳定的排序算法有直接插入排序、冒泡排序和归并排序，而不稳定的排序算法有希尔排序、快速排序、简单选择排序和堆排序。

2）时间复杂度为O（n2）的排序算法有直接插入排序、冒泡排序、快速排序和简单选择排序，时间复杂性为O（nlogn）的排序算法有堆排序和归并排序。(www.xing528.com)

3）空间复杂度为O（1）的算法有简单选择排序、直接插入排序、冒泡排序、希尔排序和堆排序，空间复杂杂度为O（n）的算法是归并排序，空间复杂度为O（logn）的算法是快速排序。

4）虽然直接插入排序和冒泡排序的速度比较慢，但是当初始序列整体或局部有序时，这两种排序算法会有较好的效率。当初始序列整体或局部有序时，快速排序算法的效率会下降。当排序序列较小且不要求稳定性时，直接选择排序效率较好；要求稳定性时，冒泡排序效率较好。

除了以上这几种排序算法以外，还有位图排序、桶排序及基数排序等。每种排序算法都有其最佳适用场合。例如，当待排序数据规模巨大，而对内存大小又没有限制时，位图排序则是最高效的排序算法。所以，在选择使用排序算法的时候，一定要结合实际情况进行分析。