排序可以分为两类:内部排序和外部排序。在排序过程中,所有记录都存储在内存中,这称为内部排序。如果在排序过程中需要外部存储,则称为外部排序。
一、内排序有可以分为以下几类
(1),插入排序:直接插入排序,二分法插入排序,希尔排序。(2)选择排序:简单的选择排序和堆排序。(3)交换排序:冒泡排序和快速排序。(4),归并排序(5),基数排序
二、时间复杂度分析
二进制插入排序类似于直接插入排序。忽略系数,最坏的情况下也是O (n 2)。
三、排序算法的选择
1.数据规模较小
(1)在要排序的列的基本顺序的情况下,可以选择直接插入排序;
(2)如果对稳定性没有要求,宜采用简单选择排序;如果对稳定性有要求,以插入或冒泡为宜。
2.数据规模不是很大
(1)可以完全利用内存空间,顺序无序,对稳定性没有要求,可以快速排序。这时候你要付出log(N)的额外空间。
(2)序列本身可能是有序的,这就要求稳定性。如果空间允许,最好合并排序。
3.数据规模很大
(1)如果想要稳定,可以考虑合并排序。
(2)对稳定性没有要求,首选堆排序。
4.序列初始基本有序(正序)
应该是直接插入,冒泡。
评论(0)