宿州网站建设,网页版浏览器怎么设置,西安官网seo技巧,html5和php做网站目录1、数据结构与算法1.1 定义1.2 常见数据结构1.3 常用算法2、插入排序3、希尔排序4、归并排序1、数据结构与算法
1.1 定义
数据结构#xff1a;是计算机中存储、组织数据的方式。具有一定逻辑关系#xff0c;应用某种存储结构#xff0c;并且封装了相应操作的数据元素集…
目录1、数据结构与算法1.1 定义1.2 常见数据结构1.3 常用算法2、插入排序3、希尔排序4、归并排序1、数据结构与算法
1.1 定义
数据结构是计算机中存储、组织数据的方式。具有一定逻辑关系应用某种存储结构并且封装了相应操作的数据元素集合。包含三方面的内容逻辑关系存储关系及操作
不同种类的数据结构适合于不同种类的应用而部分甚至专门用于特定的作业任务。例如计算机网络依赖于路由表运作B 树高度适用于数据库的封装。
为什么学数据结构 当数据过大时对数据进行搜索、插入或排序等操作就越慢这时候就需要数据结构 数据结构研究的内容就是如何按一定的逻辑结构把数据组织起来并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。 算法研究的目的是为了更有效的处理数据提高数据运算效率。
1.2 常见数据结构
栈Stack栈是一种特殊的线性表它只能在一个表的一个固定端进行数据结点的插入和删除操作。先进后出 队列Queue队列和栈类似也是一种特殊的线性表。和栈不同的是队列只允许在表的一端进行插入操作而在另一端进行删除操作。先进先出 数组Array数组是一种聚合数据类型它是将具有相同类型的若干变量有序地组织在一起的集合。 链表Linked List链表是一种数据元素按照链式存储结构进行存储的数据结构这种存储结构具有在物理上存在非连续的特点。 树Tree树是典型的非线性结构它是包括2 个结点的有穷集合 K。 图Graph图是另一种非线性数据结构。在图结构中数据结点一般称为顶点而边是顶点的有序偶对。 堆Heap堆是一种特殊的树形数据结构一般讨论的堆都是二叉堆。 散列表Hash table散列表源自于散列函数(Hash function)其思想是如果在结构中存在关键字和T相等的记录那么必定在F(T)的存储位置可以找到该记录这样就可以不用进行比较操作而直接取得所查记录。
1.3 常用算法
检索插入删除更新排序
检索检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值找具有该字段值的节点。 插入往数据结构中增加新的节点。 删除把指定的结点从数据结构中去掉。 更新改变指定节点的一个或多个字段的值。 排序把节点按某种指定的顺序重新排列。例如递增或递减。
2、插入排序
将一个记录插入到已经排好序的有序表中 插入排序的平均时间复杂度也是 O(n^2)空间复杂度为常数阶 O(1) 使用双层循环外层循环对除了第一个元素之外的所有元素内层循环对当前元素前面有序表进行待插入位置查找并进行移动 就这样依次比较到最后一个元素。
3、希尔排序
通过比较相距一定间隔的元素来进行各趟比较所用的距离随着算法的进行而减小直到只比较相邻元素的最后一趟排序为止。
希尔排序时间复杂度是 O(n ^ (1.3-2))空间复杂度为常数阶 O(1)。 希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 因此对中等大小规模表现良好但对规模非常大的数据排序不是最优选择总之比一般 O(n^2 ) 复杂度的算法快得多。
4、归并排序
采用分治法(Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
归并排序是递归算法的一个实例这个算法中基本的操作是合并两个已排序的数组取两个输入数组 A 和 B一个输出数组 C以及三个计数器 i、j、k它们初始位置置于对应数组的开始端。
A[i] 和 B[j] 中较小者拷贝到 C 中的下一个位置相关计数器向前推进一步。
当两个输入数组有一个用完时候则将另外一个数组中剩余部分拷贝到 C 中。
