排序总结

O(n^2) 小结

通过对三种时间复杂度为 O(n^2)排序算法进行分析，我们不难看出：

• 选择排序是这三种排序算法中最差的，排序即不稳定，而且时间复杂度始终为 O(n^2)。
• 冒泡排序和插入排序在空间复杂度、稳定性、时间复杂度上的数据是完全相同的，两种算法无论怎么优化，元素交换的次数也是一个固定值（逆序数）。
• 冒泡排序和插入排序在元素交换时，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。在数量级较大的情况下，插入排序的性能可能表现的更优。

O(nlogn) 小结

时间复杂度为 O(nlogn)的排序有快速排序、归并排序和堆排序三种，它们的空间复杂度和稳定性如图所示：

在归并排序的性能分析中可以了解到，归并排序虽然稳定，但是空间复杂度高，在处理较小的排序序列可以使用，体积较大则不推荐使用。

当处理体积较大的排序时，由于堆排序交换存在一些缺点，我们可以选择快速排序。在使用快速排序时，可以使用"三数取中法"等方法对快速排序进行优化，使快速排序分区更均匀。

O(n) 小结

桶排序主要适用的是范围不大的数据，可以将数据划分成不同的桶，然后对每个桶进行快速排序，最终合并到一起完成排序。

基数排序要求数据可以按位划分，每一位的数据范围较小，且如果高位数据较大则地位不需要比较了，高位相同的再比较低位。