排序算法分类和比较

https://www.cnblogs.com/beli/p/6297741.html

https://www.cnblogs.com/liyongshuai/p/7197962.html

[图片上传失败...(image-1ec62d-1550542124892)]

image.png

稳定性：

• 稳定的排序方法有：直接插入排序、冒泡排序、归并排序

• 不稳定的排序方法有：希尔排序、快速排序、简单选择排序、堆排序

选择排序方法的原则：

1. 若排序元素的数目n较小（如小于等于50）时，可采用直接插入排序或者简单选择排序。由于直接插入排序所需的元素移动操作较简单选择排序多，因而当元素本身信息量较大时，用简单选择排序比较好。

2. 若元素的初始状态已经按关键码基本有序，可采用直接插入排序或冒泡排序。

3. 若排序元素的数目n较大，则可采用快速排序、堆排序或归并排序等。

       （1）快速排序目前被认为是最快的一种方法，而在待排序元素个数比较多的情况下，归并排序较堆排序更快。
   
       （2）堆排序的时间复杂度不会发生变化，且所需的辅助空间少于快速排序。快排的时间复杂度会有变化。
   
       （3）快速排序和堆排序都是不稳定的排序方法，若需要稳定的排序方法，则可采用归并排序。