数据结构—排序

内部排序:指待排序记录全部存放在内存中排序的过程。
外部排序:指待排序记录的数量很大,以至于内存不能容纳全部记录,在排序过程中尚需对外存进行访问的过程。

插入排序

1.直接插入排序
先将序列中的第一个记录看成一个有序列,然后从第二个记录开始,逐个进行插入,直至整个序列有序,排序过程为n-1躺插入。

  • 时间效率:因为在最坏情况下,所有元素的比较次数总和为(0+1+...+n-1)—>O(n的平方),时间复杂度O(n的平方)。
  • 空间效率:仅占用1个缓冲单元—O(1)
  • 算法的稳定性:稳定
    2、希尔排序


示意图
选择排序

每一次从待排序的数据元素中选出最小的一个元素,存放在已排序列的后面,直到全部待排序的数据元素排完。

  • 优点:实现简单
  • 缺点:每趟只能确定一个元素,表长为n时需要n-1趟
  • 前提:顺序存储结构

1、直接选择排序
在所有记录中选出最小的记录,把它与第一个记录交换,然后在剩余的记录内选出最小的记录与第二个记录交换...依次类推。


示意图

2、堆排序


示意图

堆排序的最坏时间复杂度为O(n倍的log以2为底的n次方),堆排序平均性能接近最坏性能。
堆排序的辅助空间为O(1)。

交换排序

1、冒泡排序

  • 时间效率:O(n的平方)
  • 空间效率:O(1)
  • 稳定性:稳定

2、快速排序

  • 优点:因为每趟可以确定不止一个元素的位置,而且呈指数增加,所以特别
    示意图

快速排序最坏时间复杂度O(n的平方),最好时间复杂度为O(n倍的log以2为底的n次方)

归并排序

可以把一个长度为n的无序序列看成是n个长度为1的有序子序列,首先做两两归并,得到n/2个长度为2的有序子序列;再做两两归并,如此重复,直到最后得到一个长度为n的有序序列。

示意图

时间效率:O(nLog以2为底的n次方)
空间效率:O(n)
稳定性:稳定

算法复杂性比较

排序算法时间复杂度表
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 一、 单项选择题(共71题) 对n个元素的序列进行冒泡排序时,最少的比较次数是( )。A. n ...
    貝影阅读 9,502评论 0赞 10
  • 1.数据结构 数据结构:专门研究应用程序中数据之间逻辑关系、存储方式及其操作的学问 集合:数据元素之间只有“同属于...
    怪蜀黍Zzzzlw阅读 1,315评论 0赞 21
  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 6,729评论 0赞 13
  • 冒泡排序---Bubble Sort 冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如...
    LittlePy阅读 292评论 0赞 0
  • 所有内部排序算法的一个总结表格 简单选择排序 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后...
    fredal阅读 3,405评论 4赞 132

友情链接更多精彩内容