首页 > 编程语言 > 详细

数据结构(七)排序---排序知识点总结

时间:2018-09-23 00:34:20      阅读:59      评论:0      收藏:0      [点我收藏+]

标签:至少   pla   有序   rdquo   稳定   href   比较   cli   tar   

回顾:排序分类

(一)插入类

直接插入排序

折半插入排序

希尔排序

本质还是插入排序

(二)交换类

冒泡排序

快速排序

(三)选择类

简单选择排序

堆排序

(四)归并类

归并排序

一:复杂度总结

(一).时间复杂度

1.平均情况下:快些排队(快希排堆)

在平均情况下,快速排序,希尔排序,归并排序,堆排序的时间复杂度都是O(nlog2n),其他都是O(n2)

2.最坏情况下

快速排序的时间复杂度为O(n2),其他的和平均情况下相同

(二).空间复杂度

快速排序是O(log2n),归并排序是O(n),基数排序是O(rd),其他都是O(1)

(三).其他:容易插,起的好

直接插入排序和冒泡排序对于所谓的:直接插和起的好(指的是初始化序列已经有序)。其复杂度变为O(n)

二:稳定性总结

技术分享图片
就是说在我们未排序之前,数据中可能已经有部分数据是相同的,若是我们排序后,这些相同的数据的先后顺序没有改变,那么就是稳定的,若是我们在排序中,将相同的数据的顺序进行了修改(虽然没啥影响,但是做了多余的操作,而且说明我们的操作对数据的影响较大,不稳定),那么就是不稳定的
稳定性定义

(一)快些选队:不稳定

快速排序,希尔排序,简单选择排序,堆排序都是不稳定排序,其他都是稳定排序

三:其他细节:排序原理相关

(一)经过一趟排序,能够保证一个关键字达到最终位置,这样的排序是交换类(冒泡,快速)选择类(简单排序,堆)

(二)排序算法关键字比较次数原始序列无关---简单选择排序折半插入排序

(三)排序算法的排序趟数和原始序列有关---交换类的排序

四:其他结论

(一)借助于“比较”进行排序的算法,在最坏情况下的时间复杂度至少为O(nlog2n)

 

数据结构(七)排序---排序知识点总结

标签:至少   pla   有序   rdquo   稳定   href   比较   cli   tar   

原文:https://www.cnblogs.com/ssyfj/p/9691665.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号