正文

数据结构：第8章学习小结

000827lmk  000827lmk  2022-12-04  592

关键词：

一、排序

概念：排序(Sorting)是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。

排序方式：

1.插入排序：①直接插入排序：是一种最简单的排序方法,其基本操作是将一条记录插入到已排好序的有序表中,从而得到一个新的、记录数量增1的有序表。【一一对比】

特点: (I)稳定排序。

(2)算法简便，且容易实现。

(3)也适用千链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针。

(4) 更适合于初始记录基本有序（正序）的情况，当初始记录无序， n较大时，此算法时间复杂度较高，不宜采用。

②折半插入排序：在折半查找的前提下进行的排序操作【在已经排好的序列中插入】

特点：(l)稳定排序。

(2)因为要进行折半查找，所以只能用于顺序结构，不能用于链式结构。

(3) 适合初始记录无序、n较大时的情况。

③希尔排序：直接插入排序，当待排序的记录个数较少且待排序序列的关键字基本有序时，效率较高。希尔排序基于以上两点，从 “减少记录个数” 和 “序列基本有序” 两个方面对直接插入排序进行了改进。

特点：(1)记录跳跃式地移动导致排序方法是不稳定的。

(2)只能用千顺序结构，不能用于链式结构。

(3) 增量序列可以有各种取法，但应该使增量序列中的值没有除 l 之外的公因子，并且最后一个增量值必须等于1。

(4) 记录总的比较次数和移动次数都比直接插入排序要少，n越大时，效果越明显。所以适合初始记录无序、n较大时的情况。

2.交换排序

①冒泡排序：是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录如气泡一般逐渐往上＂漂浮（左移），或者使关键字大的记录如石块一样逐渐向下＂坠落” （右移）。

特点：(1) 稳定排序。

(2) 可用于链式存储结构。

(3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时，此算法不宜采用。

②快速排序：是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个（不相邻）记录的一次交换，消除多个逆序，则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。

特点：(I) 记录非顺次的移动导致排序方法是不稳定的。

(2)排序过程中需要定位表的下界和上界，所以适合用于顺序结构，很难用千链式结构。

(3) 当n较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以其适合初始记录无序、 n较大时的情况。

3.选择排序①简单选择排序也称作直接选择排序：以第一个数进行比较，然后找到里面最小的那一个数后，调换位置，紧接着第二个数开始

②树形选择排序：又称锦标赛排序(Tournament Sort), 是一种按照锦标赛的思想进行选择排序的方法。【从树的叶子到根，两两比较，换位】

③堆排序：是一种树形选择排序，在排序过程中，将待排序的记录 r[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大（或最小）的记录。【调整堆、建初堆】

4.归并排序：将两个或两个以上的有序表合并成一个有序表

特点：(1)是稳定排序。

(2)可用于链式结构，且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈。

5.基数排序：多关键字的排序、链式基数排序

内容掌握程度比较低，在课余时间去理解

数据结构第八章学习小结(代码片段)

数据结构第八章学习小结排序8.1基本概念和排序方法概述排序的基本概念1.排序：是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作2.排序的稳定性：当排序记录中的关键字Ki(i=1,2,…，n)都不相同时，则任何一... 查看详情

第5章学习小结

...的知识，以前一直很好奇，为什么电脑能存储像树一样的数据结构，学完才发现，ADT加数组或者ADT加链表真的可以衍生出多种多样的数据类型，以下做出本章小结：1.利用ASCII码实现不同类型的数据的转换，如：int=char-‘0&rsquo... 查看详情

数据结构：第1章学习小结

心得体会：这周开始接触了数据结构的概念，对数据结构有了初步的认识，学习了数据结构的逻辑结构、存储结构，以及数据类型和算法，明白了解决办法的效率跟数据的组织方式、空间的利用效率、算法的巧妙程度等有关本学... 查看详情

数据结构第8章小结

第八章给我们介绍了内部排序和外部排序。各种排序方法都有各自的优缺点，没有说哪一种是最好的。直接插入排序、折半插入排序、冒泡排序和简单选择排序的速度较慢，但是它们实现的过程比较简单，所以称他们为简单... 查看详情

数据结构第五章学习小结(代码片段)

本章学习内容：本章我们学习了一种新的数据结构，“树”结构是一类非线性数据结构。主要学习到二叉树的内容，二叉树有好几个重要的性质。刚开始学这种数据结构的时候，还是觉得比线性结构抽象很多。在后来上课... 查看详情

ml第11周学习小结

本周收获总结一下本周学习内容：1、学习了《深入浅出Pandas》的第10章：Pandas数据清洗10.1缺失值的认定~10.5Numpy格式转化🚗博客：Pandas:数据清洗2、《机器学习》第3章、第4章的一部分第3章3.1基本形式3.2线性回归3.3对数几率... 查看详情

第7章学习小结(代码片段)

查找分为线性表的查找、树表的查找、散列表的查找。一些定义：查找表：由同一类型的数据元素（或记录）构成的集合（在查找时对表做修改操作，如插入和删除，则称为动态查找表；否则称为静态查找表）关键... 查看详情

数据结构第五章学习小结(代码片段)

一、本章学习内容小结：本章学习了新的数据结构--树，与前面的学习不同的是，树是一种非线性结构，树只有一个根结点，其子树本身也是一棵树，所以其定义是递归定义。本章还学习了二叉树和哈夫曼树。二叉树：结点的度... 查看详情

数据结构：第八章学习小结(代码片段)

1概述2待排序记录的存储方法3排序算法的效率评价指标4时间效率5排序速度（比较次数与移动次数）6空间效率7占内存辅助空间的大小8稳定性9A和B的关键字相同，在排序之后先后顺序保持不变1011内部排序12插入排序13直接插入排... 查看详情

第7章学习小结(代码片段)

第7章学习小结上图为第七章的思维导图。在顺序查找中，设置监视哨的顺序查找比较重要。1intSearch_Seq(SSTableST,KeyTypekey)23ST.R[0].key=key;4for(i=ST.length;ST.R[i].key!=key;--i);5returni;6它的时间复杂度为O（n），空间复杂度为O（1）算法比... 查看详情

第1章学习小结

...形式，还是从程序设计基础再深挖的学习内容，都让我对数据结构产生了越来越深的学习兴趣。本学期的目标：即使在这段特殊的日子里，我也希望自己能像在学校里一样约束自己，来适应学习的新方式，掌握本学期的新知识，... 查看详情

数据结构第六章学习小结---图(代码片段)

...了有关图的一些知识，图是一种比线性表和树更为复杂的数据结构，她不像线性表一样，数据元素之间具有线性关系，每个元素对应一个前驱和一个后继，她也不像树一样，数据元素之间有明显的层次关系，简而言之，在图结构... 查看详情

数据结构第一章学习小结

第一章学习了一些基本概念以及它们之间的联系，对数据结构这门课程有了初步的了解。刚开始看书的时候，有很多地方不是很明白，对一些名词的解释也不懂，后来结合视频讲解才比较透彻。一开始不清楚ADT的作用，直到自己... 查看详情

数据结构：第1章学习小结

心得体会：　　初识数据结构，目前的理解是它能帮助我从内存的角度理解编程语言。受限于内存的大小，我们不得不思考问题解决的算法。与现实一致，实际问题的处理也总面临着时空和空间的约束。这个时候，高效的数据组... 查看详情

第2章监督学习python机器学习基础教程

第2章　监督学习2.1　分类与回归.212.2　泛化、过拟合与欠拟合.222.3　监督学习算法.242.3.1　一些样本数据集252.3.2k近邻.282.3.3　线性模型352.3.4　朴素贝叶斯分类器532.3.5　决策树542.3.6　决策树集成642.3.7　核支持向量机712.3.8　神经... 查看详情

第5章学习小结(代码片段)

本章我们学习了树与二叉树，树对于我来说是一种新的概念，虽然它本身的结构比较简单，但是在认清一些概念的时候还是要费上一点功夫，我们学习到的有树的基本术语：　　节点的度：节点的子树个数。　树的度：... 查看详情

数据结构第一章学习小结

...得体会：通过对第一章的学习，我初步了解了“程序=数据结构+算法”这个公式，数据结构又包括逻辑结构和存储结构，通过分析数据元素之间的逻辑关系来确定使用哪种结构，通过对问题的具体分析判定使用顺序存储结... 查看详情

第7章学习小结(代码片段)

一、线性表的查找 1、顺序查找：typedefKeyTypeint;//这个根据具体情况去定义；在这里定义为int；typedefstructKeyTypekey;InfoTypeotherinfo;//这个根据具体情况去改，这里只是抽象的说成还要添加这些类型。ElemType;typedefstruct... 查看详情