C语言常见排序法总结：稳定性、时间复杂度、辅助空间比较

排序法总结 **排序法稳定性比较** 在排序法中，稳定性是指在排序前后，相等的元素保持原有的相对次序。根据稳定性，可以将排序法分为稳定排序和非稳定排序。稳定排序法包括插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序，而选择排序、希尔排序、快速排序、堆排序等则是非稳定的。 **时间复杂性比较** 排序法的时间复杂度是指排序算法的执行时间成本。根据时间复杂度，可以将排序法分为三类：O(n^2)的插入排序、冒泡排序、选择排序，O(nlog2n)的非线形排序，和O(n)的线形排序。 **辅助空间的比较** 排序法的辅助空间是指排序算法在执行过程中所需的额外存储空间。根据辅助空间，可以将排序法分为两类：O(n)的线形排序、二路归并排序，和O(1)的其他排序法。 **其他比较** 在实际应用中，需要根据具体情况选择合适的排序法。例如，在序列局部或整体有序时，插入排序和冒泡排序可以达到较快的速度；在n较小时，对稳定性不作要求时，选择排序是一个不错的选择；在待排序的记录的关键字在一个明显有限范围内时，桶排序是一个不错的选择；在n较大时，快速排序是一个不错的选择；在n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，归并排序是一个不错的选择。 **排序法分类** 根据排序法的稳定性、时间复杂度、辅助空间等特性，可以将排序法分为多种类型： * 稳定排序法：插入排序、冒泡排序、二叉树排序、二路归并排序等 * 非稳定排序法：选择排序、希尔排序、快速排序、堆排序等 * 内排序法：插入排序、冒泡排序、选择排序等 * 外排序法：归并排序、堆排序等 * 时间复杂度为O(n^2)的排序法：插入排序、冒泡排序、选择排序等 * 时间复杂度为O(nlog2n)的排序法：非线形排序等 * 时间复杂度为O(n)的排序法：线形排序等 * 辅助空间为O(n)的排序法：线形排序、二路归并排序等 * 辅助空间为O(1)的排序法：其他排序法等 **结论** 排序法是计算机科学中一个非常重要的概念，它有很多种类型，每种排序法都有其特点和适用场景。了解排序法的稳定性、时间复杂度、辅助空间等特性是非常重要的，以便选择合适的排序法来解决实际问题。