常用12大排序算法汇总–插入排序-交换排序-选择排序-基数排序-归并排序等

2017-04-20 21:49 阅读 2,610 次 评论 0 条

1.排序相关的的基本概念

(1)排序概念:将一组杂乱无章的数据按一定的规律顺次排列起来。

数据表( data list): 它是待排序数据对象的有限集合。

排序码(key):通常数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码,要视具体的应用需要而定。

(2)排序分类
内排序:指在排序期间数据对象全部存放在内存的排序;

外排序:指在排序期间全部对象个数太多,不能同时存放在内存,必须根据排序过程的要求,不断在内、外存之间移动的排序。

排序算法分类总结

 

 2.排序算法的稳定性

如果在对象序列中有两个对象r[i]和r[j] ,它们的排序码k[i]==k[j] 。如果排序前后,对象r[i]和r[j] 的相对位置不变,则称排序算法是稳定的;否则排序算法是不稳定的。

 

3.排序算法的评价

(1)时间开销

算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的,需要按最好情况和最坏情况进行估算。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。

(2)空间开销

算法执行时所需的附加存储。

(3)复杂度

排序算法复杂度总结

 

4.十二大排序算法

(1)插入排序(Insert Sorting)

(2)二分(折半)插入排序

(3)希尔(Shell)插入排序

(4)交换排序之冒泡排序

(5)交换排序之快速排序

(6)选择排序之直接选择排序

(7)选择排序之堆排序

(8)归并排序

(9)基数排序

(10)桶排序

(11)计数排序

(12)鸡尾酒排序

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用12大排序算法汇总–插入排序-交换排序-选择排序-基数排序-归并排序等 | 算法君

发表评论


表情