前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >第八章知识小结【数据结构】

第八章知识小结【数据结构】

作者头像
MIKE笔记
发布2023-03-22 16:24:25
1970
发布2023-03-22 16:24:25
举报

目录


前言

第八章知识小结


1. 直接插入排序

若出现各种可能排列的概率相同,则可取最好情况和最坏情况的平均情况。

平均情况比较次数和移动次数约为n2/4

时间复杂度为 o(n2),空间复杂度为 o(1)

是一种稳定的排序方法

适用于:基本有序,元素较少。

2. 折半插入排序

折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列。

减少了比较次数,但没有减少移动次数

平均性能优于直接插入排序

时间复杂度为 o(n2)

空间复杂度为 o(1)

是一种稳定的排序方法

3. 希尔排序

基本思路:将整个待排记录序列分割成若干组,分别进行直接插入排序。

分组技巧:分组不是简单地“逐段分割”,而是将相隔某个增量dk的记录组成一个组。让增量dk逐趟缩短,(例如依次取5,3,1),直到dk=1为止。

优点:

(1)小元素跳跃式前移

(2)最后一趟增量为1时,序列已基本有序

(3)平均性能优于直接插入排序

时间复杂度是n和d的函数:

O(n1.25)~O(1.6n1.25)—经验公式 空间复杂度为 o(1)

5、交换排序

基本思想:两两比较,如果发生逆序则交换位置,直到所有记录都排好序为止。

6、冒泡排序

冒泡排序:两两比较,若逆序则交换,小数如气泡一样上浮(左移),大数如石块一样下沉(右移)。

优点:每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素; 一旦下趟没有交换,还可提前结束排序 时间复杂度为 o(n2) 空间复杂度为 o(1) 是一种稳定的排序方法

8、快速排序

(1)可以证明,最好情况下的时间复杂度为O(nlog2n) ,最坏情况下为O(n),平均时间复杂度是O(nlog2n)。

(2)实验结果表明:就平均计算时间而言,快速排序是我们所讨论的所有内排序方法中最好的一个。

(3)快速排序是递归的,需要有一个栈存放每层递归调用时参数(新的low和high)。

(4)最大递归调用层次数与递归树的深度一致,因此,要求存储开销为 O(log2n) 。

(5)稳定性: 不稳定—可选任一元素为支点。

9、选择排序

简单选择排序

移动次数:最好情况:0。最坏情况:3(n-1) 时间复杂度:O(n²);空间复杂度:O(1)

稳定 堆排序 什么是堆? 如何建立堆?(此处不做总结,看书) 时间效率:O(nlog2n) 空间效率:O(1) 稳 定 性:不稳定 适用于n 较大的情况 基本思想:每一趟从待排序的记录中选出关键字最小的记录,按顺序放在已经排好序的记录序列的后面。

10、归并排序

归并:将两个或两个以上的有序表组合成一个新有序表 时间效率:O(nlog2n) 空间效率:O(n) 稳 定 性:稳定

在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-05-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 目录
  • 前言
    • 1. 直接插入排序
      • 2. 折半插入排序
        • 3. 希尔排序
          • 5、交换排序
            • 6、冒泡排序
              • 8、快速排序
                • 9、选择排序
                  • 简单选择排序
                • 10、归并排序
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档