关于各种排序方法的比较.doc

《关于各种排序方法的比较.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、各种排序方法的总结一．直接插入排序1．时间复杂度移动次数和比较次数受初始排列的影响。最好情况o(n)最坏情况o(n2)平均情况o(n2)2．空间复杂度：o(1)3．算法特点稳定排序；算法简便，且容易实现适用于顺序和链式两种存储结构，链式存储时不需要移动记录，只修改指针；适合于初始记录基本有序的情况；当记录无序，且n较大时，不宜采用。二．折半插入排序1．时间复杂度移动次数受初始排列的影响。最好情况o(nlog2n)最坏情况o(n2)平均情况o(n2)2．空间复杂度o(1)3．算法特点稳定排序；算法简便，且容易实现只适用于顺序存储结构，不能用于链式存储结构；适合记录无序、n

2、较大的情况；三．希尔排序1．时间复杂度2．空间复杂度o(1)3．算法特点不稳定排序，记录跳跃式的移动；只适用于顺序存储结构，不能用于链式存储结构；增量序列可以有多种取法，最后一个增量值必须是1；适合记录无序、n较大的情况；四．冒泡排序1．时间复杂度移动次数和比较次数受初始排列的影响。最好情况o(n)最坏情况o(n2)平均情况o(n2)2．空间复杂度o(1)3．算法特点稳定排序；适用于顺序存储结构和链式存储结构；适合记录无序、n较大时不宜采用；五．快速排序1．时间复杂度移动次数和比较次数受初始排列的影响。最好情况o(nlog2n)最坏情况o(n2)平均情况o(nlog2n

3、)1．空间复杂度：o(log2n)递归算法2．算法特点不稳定排序；算法简便，且容易实现适用于顺序存储结构；适合记录无序，且n较大情况。一．直接选择排序1．时间复杂度比较次数不受初始排列的影响，移动次数受影响。最好情况o(n2)最坏情况o(n2)平均情况o(n2)2．空间复杂度o(1)3．算法特点不稳定排序；适用于顺序存储结构和链式存储结构；移动记录的次数较多，适合记录占用空间较多时，采用此方法；二．堆排序1．时间复杂度移动次数和比较次数受初始排列的影响。最好情况o(nlog2n)最坏情况o(nlog2n)平均情况o(nlog2n)2．空间复杂度：o(1)3．算法特点不稳

4、定排序；适用于顺序存储结构；n较小时不宜采用。三．归并排序1．时间复杂度移动次数和比较次数受初始排列的影响。最好情况o(nlog2n)最坏情况o(nlog2n)平均情况o(nlog2n)2．空间复杂度：o(n)3．算法特点稳定排序；适用于顺序和链式两种存储结构；四．基数排序1．时间复杂度唯一一个不通过比较和移动记录实现排序的方法。最好情况o(d(n+REDIX))最坏情况o(d(n+REDIX))平均情况o(d(n+REDIX))其中，d表示关键字的位数；n表示关键字的个数；REDIX表示基，即位上关键字的取值范围4．空间复杂度：o(n+REDIX)5．算法特点稳定排序

5、；适用于顺序和链式两种存储结构；使用条件较多，需要知道各级关键字的主次关系和各级关系字的取值范围。