seo网站排名后退,wordpress 经过天数,wordpress server酱,自己做的网站出现广告目录
数据结构与算法
为什么要学习数据结构和算法#xff1f;
常见的数据结构
常用算法
插入排序
一、概念及其介绍
二、适用说明
三、过程图示
希尔排序
一、概念及其介绍
二、适用说明
三、过程图示
归并排序
一、概念及其介绍
二、适用说明
三、过程图示
…目录
数据结构与算法
为什么要学习数据结构和算法
常见的数据结构
常用算法
插入排序
一、概念及其介绍
二、适用说明
三、过程图示
希尔排序
一、概念及其介绍
二、适用说明
三、过程图示
归并排序
一、概念及其介绍
二、适用说明
三、过程图示
随机化快速排序
一、概念及其介绍
二、适用说明
三、过程图示
双路快速排序
一、概念及其介绍
二、适用说明
三、过程图示
三路排序算法
一、概念及其介绍
二、适用说明
排序算法衍生问题
1归并排序和快速排序都使用了分治算法。
2逆序对的定义
3取数组中第 n 大的元素 Reference Source 数据结构与算法
数据结构英语data structure是计算机中存储、组织数据的方式。
数据结构是一种具有一定逻辑关系在计算机中应用某种存储结构并且封装了相应操作的数据元素集合。它包含三方面的内容逻辑关系、存储关系及操作。
不同种类的数据结构适合于不同种类的应用而部分甚至专门用于特定的作业任务。例如计算机网络依赖于路由表运作B 树高度适用于数据库的封装。
为什么要学习数据结构和算法
随着应用程序变得越来越复杂和数据越来越丰富几百万、几十亿甚至几百亿的数据就会出现而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢数据结构就是用来解决这些问题的。
常见的数据结构
栈Stack栈是一种特殊的线性表它只能在一个表的一个固定端进行数据结点的插入和删除操作。队列Queue队列和栈类似也是一种特殊的线性表。和栈不同的是队列只允许在表的一端进行插入操作而在另一端进行删除操作。数组Array数组是一种聚合数据类型它是将具有相同类型的若干变量有序地组织在一起的集合。链表Linked List链表是一种数据元素按照链式存储结构进行存储的数据结构这种存储结构具有在物理上存在非连续的特点。树Tree树是典型的非线性结构它是包括2 个结点的有穷集合 K。图Graph图是另一种非线性数据结构。在图结构中数据结点一般称为顶点而边是顶点的有序偶对。堆Heap堆是一种特殊的树形数据结构一般讨论的堆都是二叉堆。散列表Hash table散列表源自于散列函数(Hash function)其思想是如果在结构中存在关键字和T相等的记录那么必定在F(T)的存储位置可以找到该记录这样就可以不用进行比较操作而直接取得所查记录。
常用算法
数据结构研究的内容就是如何按一定的逻辑结构把数据组织起来并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据提高数据运算效率。数据的运算是定义在数据的逻辑结构上但运算的具体实现要在存储结构上进行。一般有以下几种常用运算
检索检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值找具有该字段值的节点。插入往数据结构中增加新的节点。删除把指定的结点从数据结构中去掉。更新改变指定节点的一个或多个字段的值。排序把节点按某种指定的顺序重新排列。例如递增或递减。
插入排序
一、概念及其介绍
插入排序(InsertionSort)一般也被称为直接插入排序。
对于少量元素的排序它是一个有效的算法。插入排序是一种最简单的排序方法它的基本思想是将一个记录插入到已经排好序的有序表中从而一个新的、记录数增 1 的有序表
。在其实现过程使用双层循环外层循环对除了第一个元素之外的所有元素内层循环对当前元素前面有序表进行待插入位置查找并进行移动。
二、适用说明
插入排序的平均时间复杂度也是 O(n^2)空间复杂度为常数阶 O(1)具体时间复杂度和数组的有序性也是有关联的。
插入排序中当待排序数组是有序时是最优的情况只需当前数跟前一个数比较一下就可以了这时一共需要比较 N-1 次时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的此时需要比较次数最多最坏的情况是 O(n^2)。
三、过程图示
假设前面 n-1(其中 n2)个数已经是排好顺序的现将第 n 个数插到前面已经排好的序列中然后找到合适自己的位置使得插入第n个数的这个序列也是排好顺序的。
按照此法对所有元素进行插入直到整个序列排为有序的过程称为插入排序。
从小到大的插入排序整个过程如图示
第一轮从第二位置的 6 开始比较比前面 7 小交换位置。 第二轮第三位置的 9 比前一位置的 7 大无需交换位置。 第三轮第四位置的 3 比前一位置的 9 小交换位置依次往前比较。 第四轮第五位置的 1 比前一位置的 9 小交换位置再依次往前比较。 ......
就这样依次比较到最后一个元素。
希尔排序
一、概念及其介绍
希尔排序(Shell Sort)是插入排序的一种它是针对直接插入排序算法的改进。
希尔排序又称缩小增量排序因 DL.Shell 于 1959 年提出而得名。
它通过比较相距一定间隔的元素来进行各趟比较所用的距离随着算法的进行而减小直到只比较相邻元素的最后一趟排序为止。
二、适用说明
希尔排序时间复杂度是 O(n^(1.3-2))空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 因此对中等大小规模表现良好但对规模非常大的数据排序不是最优选择总之比一般 O(n^2 ) 复杂度的算法快得多。
三、过程图示
希尔排序目的为了加快速度改进了插入排序交换不相邻的元素对数组的局部进行排序并最终用插入排序将局部有序的数组排序。
在此我们选择增量 gaplength/2缩小增量以 gap gap/2 的方式用序列 {n/2,(n/2)/2...1} 来表示。
如图示例
1初始增量第一趟 gap length/2 4 2第二趟增量缩小为 2 3第三趟增量缩小为 1,得到最终排序结果 归并排序
一、概念及其介绍
归并排序Merge sort是建立在归并操作上的一种有效、稳定的排序算法该算法是采用分治法(Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。
二、适用说明
当有 n 个记录时需进行 logn 轮归并排序每一轮归并其比较次数不超过 n元素移动次数都是 n因此归并排序的时间复杂度为 O(nlogn)。归并排序时需要和待排序记录个数相等的存储空间所以空间复杂度为 O(n)。
归并排序适用于数据量大并且对稳定性有要求的场景。
三、过程图示
归并排序是递归算法的一个实例这个算法中基本的操作是合并两个已排序的数组取两个输入数组 A 和 B一个输出数组 C以及三个计数器 i、j、k它们初始位置置于对应数组的开始端。
A[i] 和 B[j] 中较小者拷贝到 C 中的下一个位置相关计数器向前推进一步。
当两个输入数组有一个用完时候则将另外一个数组中剩余部分拷贝到 C 中。 自顶向下的归并排序递归分组图示 对第三行两个一组的数据进行归并排序 对第二行四个一组的数据进行归并排序 整体进行归并排序 随机化快速排序
一、概念及其介绍
快速排序由 C. A. R. Hoare 在 1960 年提出。
随机化快速排序基本思想通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。
二、适用说明
快速排序是一种比较快速的排序算法它的平均运行时间是 O(nlogn)之所以特别快是由于非常精练和高度优化的内部循环最坏的情形性能为 O(n^2)。像归并一样快速排序也是一种分治的递归算法。从空间性能上看快速排序只需要一个元素的辅助空间但快速排序需要一个栈空间来实现递归空间复杂度也为O(logn)。
三、过程图示
在一个数组中选择一个基点比如第一个位置的 4然后把4挪到正确位置使得之前的子数组中数据小于 4之后的子数组中数据大于 4然后逐渐递归下去完成整个排序。 如何和把选定的基点数据挪到正确位置上这是快速排序的核心我们称为 Partition。
过程如下所示其中 i 为当前遍历比较的元素位置 如果是对近乎有序的数组进行快速排序每次分区后子数组大小极不平衡容易退化成 O(n^2) 的时间复杂度算法。我们需要对上述代码进行优化随机选择一个基点做为比较称为随机化快速排序算法。只需要在上述代码前加上下面一行随机选择数组中一数据和基点数据进行交换。
swap( arr, l , (int)(Math.random()*(r-l1))l );
双路快速排序
一、概念及其介绍
双路快速排序算法是随机化快速排序的改进版本partition 过程使用两个索引值i、j用来遍历数组将 v 的元素放在索引i所指向位置的左边而将 v 的元素放在索引j所指向位置的右边v 代表标定值。
二、适用说明
时间和空间复杂度同随机化快速排序。 对于有大量重复元素的数组如果使用上一节随机化快速排序效率是非常低的导致 partition 后大于基点或者小于基点数据的子数组长度会极度不平衡甚至会退化成 O(n*2) 时间复杂度的算法对这种情况可以使用双路快速排序算法。
三、过程图示
使用两个索引值i、j用来遍历我们的序列将 v 的元素放在索引 i 所指向位置的左边而将 v 的元素放在索引 j 所指向位置的右边平衡左右两边子数组。 三路排序算法
一、概念及其介绍
三路快速排序是双路快速排序的进一步改进版本三路排序算法把排序的数据分为三部分分别为小于 v等于 v大于 vv 为标定值这样三部分的数据中等于 v 的数据在下次递归中不再需要排序小于 v 和大于 v 的数据也不会出现某一个特别多的情况通过此方式三路快速排序算法的性能更优。
二、适用说明
时间和空间复杂度同随机化快速排序。
三路快速排序算法是使用三路划分策略对数组进行划分对处理大量重复元素的数组非常有效提高快速排序的过程。它添加处理等于划分元素值的逻辑将所有等于划分元素的值集中在一起。
三、过程图示 我们分三种情况进行讨论 partiton 过程i 表示遍历的当前索引位置
1当前处理的元素 eV元素 e 直接纳入蓝色区间同时i向后移一位。 2当前处理元素 eve 和等于 V 区间的第一个位置数值进行交换同时索引 lt 和 i 都向后移动一位 3当前处理元素 eve 和 gt-1 索引位置的数值进行交换同时 gt 索引向前移动一位。 最后当 igt 时结束遍历同时需要把 v 和索引 lt 指向的数值进行交换这样这个排序过程就完成了然后对 V 和 V 的数组部分用同样的方法再进行递归排序。
排序算法衍生问题
本小节对本教程的排序算法做一个总结。
1归并排序和快速排序都使用了分治算法。
顾名思义就是将原问题分割查能同等结构的子问题之后将子问题逐一解决后原问题也就得到了解决。
2逆序对的定义
如果存在正整数 i, j 使得 1 ≤ i j ≤ n 而且 A[i] A[j]则 A[i], A[j] 这个有序对称为 A 的一个逆序对。我们可以使用本教程的归并思想求逆序对的数量。
3取数组中第 n 大的元素
并不需要对整个数组进行排序使用快速排序的思路求数组中第 n 大元素算法复杂度为 O(n)。 Reference Source
数据结构与算法 | 菜鸟教程
