精华内容
下载资源
问答
  • 数据结构与算法】如何高效学习数据结构与算法

    千次阅读 多人点赞 2020-05-23 23:30:44
    如果想成为一个高级开发工程师或者进入大厂,不论岗位是前端、后端还是AI,算法都是重中之重。也无论我们需要进入的公司的岗位是否最后是做算法工程师,前提面试就需要考算法。所以`小时不学算法,长大掉头发`。

    前言

    本文是个人基于覃超老师的《算法训练营》的学习笔记,此笔记的内容都是学习后的个人记录、个人总结、理解和思想。仅供参考学习。

    很多同学在大学的时候会觉得数据结构与算法很枯燥,很多小伙伴都不愿意听这门课程。甚至以前还觉得能开发一个项目就能成为一个合格的程序员。但是学会算法,或者接触过数据结构与算法后,发现懂这门知识的程序员编写出来的代码相对有更高的质量。代码的性能、写法、底层逻辑和解决问题的能力都会高于不懂数据结构与算法的程序员。

    到了如今,如果想成为一个高级开发工程师或者进入大厂,不论岗位是前端、后端还是AI,算法都是重中之重。也无论我们需要进入的公司的岗位是否最后是做算法工程师,前提面试就需要考算法。所以小时不学算法,长大掉头发

    这系列的《算法学习笔记》,与大家一起重温或者学习数据结构与算法。

    这里也赠送大家一句话:

    好记性不如烂笔头,好记性更不如好笔记

    愿大家在技术银河中终身漂泊学习时,习惯编写自己的笔记,以后这些笔记必定成为我们最珍贵的宝藏!✨

    如何系统化学习算法

    深入到精通一门知识的我们都需要一个系统化的学习方法,如果这门知识越是有难度,前期就越是枯燥无味,或者甚至觉得很困难。所以学习算法也是一样的:

    • 枯燥无味
      • 所以需要系统化学习;
      • 小步快跑的方式进行学习;
      • 不懂就找答案不要埋头苦学;
    • 不牢固
      • 越是庞大的知识,越学就会越觉得之前学到的知识忘的差不多了;
      • 其实就是缺乏知识的稳固性;
    • 预习
      • 学习任何一门知识,都要先了解和预习这门知识;
      • 同理,在学习一门新的开发语言时,我们都会先来一个hello world
    • 坚持leetcode刷题
      • 要学会算法,并且稳固这一门知识,不断的刻意练习是重中之重;

    系统化的效果

    系统化学习和拿起一本书最终的效果是不一样的。很多时候我们开始学习一门知识,我们都会看:《xxx深入浅出》、《xxx指南》和《从0到1学会xxx》,其实里面的知识是很庞大的。只靠知识是无法支撑我们的实战和经验的,所以我们需要系统化的学习方法最终达到的目标也是不一样的,例如:

    • 提升到职业顶尖水平
    • 通过一线互联网大厂的面试
    • 要有Leetcode 300+ 刷题量

    推荐阅读《Outliner》这本书中的学习方法

    精通一个领域

    前面说到,任何一个领域的知识都是很庞大的。而且只靠看书,看文章学习都是不够的。所以一套好的学习方法,可以为我们打开一扇大门。而且在打开这扇大门的同时不会因为艰苦、困难、煎熬或者是枯燥而最后放弃。

    • 切碎知识点 Chunk it up
      • 庖丁解牛
      • 脉络相连 - 从根部开始学习,到分支,再到树叶。让每一个知识点都有关联关系
    • 刻意练习 Deliberate Practicing
    • 反馈 Feedback

    数据结构有什么?

    • 一维:
      • 基础: 数组 array (string),链表 linked list
      • 高级:栈 stack,队列 queue, 双端队列 duque,集合 set,映射 map (hash or map),等等
    • 二维:
      • 基础:树 tree, 图 graph
      • 高级:二叉搜索树 binary search tree(红黑树 red-black tree, AVL),堆 heap,并查集 disjoint set,字典树 Trie
    • 特殊:
      • 位运算 Bitwise,步隆过滤器 BloomFilter
      • LRU Cache (缓存)

    参考:覃超老师的《数据库脑图》

    算法有什么?

    任何的高级算法与数据结构都会转换成If Else,for循环,其实也是最朴素的计算机的知识,没有什么AI,人工智能的知识。高级算法重点是找到重复单元

    • 跳转语句 (Branch) :If-else,switch
    • 循环 (Iteration) :for, which,while loop
    • 递归 (Recursion) : Divide & Conquer, Backtrace
    • 搜索 (Search) :深度优先搜索 Depth first search,广度优先搜索 Breadth first search,启发式搜索 A*
    • 动态规划 (Dynamic Programming)
    • 二分查找 (Binary Search)
    • 贪心 (Greedy)
    • 数学 (Math),几何 (Geometry)

    参考:覃超老师的《算法脑图》

    刻意练习 - Deliberate practice

    无论是科学家、国家运动员、技术专家还是游戏职业选手,他们的优秀的背后都有一个共同点:刻意练习

    什么是刻意练习?

    • 刻意练习 - 过遍数,持续多边形的练习,用数遍达到质变!(五毒神掌);
    • 练习不擅长的地方;
    • 如果感到不舒服、不爽、枯燥的话,那证明我们正在爬坡,正在提升!

    反馈 - Feedback

    很多时候在学习中,特别是在自学的过程,我们永远不知道自己的学习的成果是怎么样的。或者我们有时候会遇到难点但是无法突破,甚至有时候我们以为自己很努力,或者已经很强了。但是其实还只是坐井观天而已。所以我们在学习的时候需要反馈。所谓的反馈有几种:

    • 即时反馈
      • 学会使用一门语言;
      • 能写出能执行的代码;
      • 能写出一个项目;
      • 能实现一个功能;
    • 主动型反馈
      • 高手代码(Github、LeetCode);
      • 第一视角止步(看视频,看高手写的代码,学习思路);
    • 被动式反馈(高手指点)
      • 代码审查 code review;
      • 例如:教练看你打,给你反馈;

    切题四件套

    我个人认为也可以叫解题四大法则

    • 理解题目(Clarification)
      • 在LeetCode看题后,先思考,认真确认和理解题目;
      • 避免忽略了一些条件或者是误解题目;
      • 面试的时候更加应该跟面试官确认清楚题目、条件、场景等;
    • 多种解题方案(Possible solutions)
      • 对比时间和空间复杂度 compare (time/spaace)
      • 最优解 optimal (加强)
    • 多编写(Coding)
      • 代码反复练习和编写;
      • 每一种解法都反复练习和编写;
    • 多测试案例(Test cases)
      • 在LeetCode上可以改变测试案例;
      • 多测试几种案例,确保自己的代码可以适应各种特殊情况;

    刷题方式(五毒神掌)

    第一遍

    • 5分钟:读题 + 思考;
    • 5分钟过后,没有思路就直接看解法;
    • 记录多个解题方法,比较解题方法的优弊;
    • 尝试默写代码,训练刻意手写代码;

    第二遍

    • 自己编写,这时候就不要再看题解了;
    • LeetCode提交代码,确保能通过;
    • 有Bug没有关系,重复debug到通过为止;
    • 编写出多种解题方法;
    • 持续优化 - 重点是 执行时间 (可参考LeetCode中打败了多少的人,也可以点击比较优秀的人,学习更好的写法);

    第三遍

    • 过了一天后,再重复做题;
    • 根据自己不熟悉的题目与程度做专项练习;
    • 专项练习就是针对自己不熟悉的种类的题,从而刻意练习哪一种题;

    第四篇

    • 过了一周后,再反复练习;

    第五遍

    • 面试前,提前2-3周开始重复练习;

    总结

    这篇笔记中,我们记录了一下关键知识重点点:

    • 如何深入学习一门知识
      • 通过系统化学习一门知识;
      • 最高效和持续的学习算法就是通过系统化的学习;
      • 这里推荐大家,真的想学好一个技术,最好的方法就是找对老师,找对课程,找对人;
    • 如何攻破庞大的知识体系变成编程职业高手
      • 切碎知识点与建立脉络
      • 刻意练习
      • 反馈
    • 数据结构中有什么? - 看脑图
    • 算法中有什么?- 看脑图
    • 算法练习方法
      • 切题四件套
      • 五毒神掌

    我是三钻,一个在技术银河中和你们一起来终身漂泊学习。
    点赞是力量,关注是认可,评论是关爱!下期再见 👋!

    公众号《技术银河》回复"算法资料"可以获得PDF版和脑图资料!

    推荐阅读

    • 📖《分析时间与空间复杂度《三钻数据结构与算法笔记》》 — 算法的核心时间和空间复杂度,《数据结构与算法》都是围绕着这个核心开展的。它的存在也是为了解决我们在编程的过程中性能问题,同时也让我们有更高级的思维和思路,写出更优质的程序。

    • 📖《28关学会HTML与HTML5基础》 — 一个系列的文章和大家一起闯关进攻前端全方位知识点。没有闯过这些关卡的童鞋,无论前端能力如何,这个可以锻炼我们自己,也可以深入知道我们自己的前端水平和差距。想学习前端的童鞋可以从零开始学习,一起排除困难共同打开前端大门!

    • 📖《44关深入浅出CSS基础之第一篇》 — 这周我们一起闯过了22关,下一期我们会一起把剩余的22关完成。学习是一种像爬山一样的过程,要经历过漫长的上坡路,一步一个脚印。“路漫漫其修远兮,吾将上下而求索。”, 在追寻知识的道路上,前方的道路还很漫长,但我们将百折不挠,不遗余力地,上天下地的去追求和探索。让我们继续坚持学习,终身学习成长。在大前端的时代爬到技术的巅峰,做一个有深度的技术人员。

    • 🔥《前端必看的8个HTML+CSS技巧》 — CSS是一个很独特的语言。看起来非常简单,但是某种特殊效果看似简单,实现起来就颇有难度。这篇文章主要是给在学习前端的童鞋分享一些新的CSS技巧,一些在前端教程和培训课堂中不会讲到的知识。第二就是让还在前端开发这条道路上的童鞋们,重新燃起对前端排版和特效的热爱和热情!🔥

    展开全文
  • 数据结构与算法必知基础知识

    千次阅读 多人点赞 2021-01-06 22:58:12
    数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这个等式存在。各个中间件开发者,架构师他们都在努力的优化中间件、项目结构以及算法提高运行效率和降低...

    原创公众号:bigsai
    文章已收录在 全网都在关注的数据结构与算法学习仓库 欢迎star

    前言

    数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这个等式存在。各个中间件开发者,架构师他们都在努力的优化中间件、项目结构以及算法提高运行效率和降低内存占用,在这里数据结构起到相当重要的作用。此外数据结构也蕴含一些面向对象的思想,故学好掌握数据结构对逻辑思维处理抽象能力有很大提升。

    为什么学习数据结构与算法?如果你还是学生,那么这门课程是必修的,考研基本也是必考科目。工作在内卷严重的大厂中找工作数据结构与算法也是面试、笔试必备的非常重要的考察点。如果工作了数据结构和算法也是内功提升一个非常重要的体现,对于程序员来说,想要得到满意的结果,数据结构与算法是必备功力!

    数据结构

    image-20201108002732048

    概念

    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。

    简言之,数据结构是一系列的存储结构按照一定执行规则、配合一定执行算法所形成的高效的存储结构。在我们所熟知的关系数据库、非关系数据库、搜索引擎存储、消息队列等都是比较牛的大型数据结构良好的运用。当然这些应用中间件不单单要考虑单纯的结构问题。还考虑实际os、网络等其他因素。

    而对于数据结构与算法这个专栏。我们程序员更改掌握的首先是在内存中运行的抽象的数据结构。是一个相对比较单一的数据结构类型,比如线性结构等等.

    相关术语

    在数据结构与算法中,数据、数据对象、数据元素、数据项很多人搞不清其中的关系。通过画一张图来捋一捋,然后下面举个例子给大家分享一下。

    image-20201230101757854

    用户信息表users

    id name sex
    001 bigsai man
    002 smallsai man
    003 菜虚鲲 woman

    users的pojo对象

    class users
    { 
         //略
         int id;
         String name;
         String sex;
    }
    //list和woman是数据
    List<users>list;//数据对象list
    List<users>woman;//数据对象woman
    list.add(new users(001,"bigsai","man"));//添加数据元素 一个users由(001,bigsai,man)三个数据项组成 
    list.add(new users(002,"smallsai","man"));//数据元素
    list.add(new users(003,"菜虚鲲","woman"));//数据元素
    woman.add(list.get(2));//003,"菜虚鲲","woman"三个数据项构成的一个数据元素
    

    数据:对客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的集合总称。上述表中的三条用户信息的记录就是数据(也可能多表多集合这里只有一个)。这些数据一般都是用户输入或者是自定义构造完成。当然,还有一些图像、声音也是数据。

    数据元素:数据元素是数据的基本单位。一个数据元素由若干数据项构成!可认为是一个pojo对象、或者是数据库的一条记录。比如菜虚鲲那条记录就是一个数据元素。

    数据项: 而构成用户字段/属性的有idnamesex等,这些就是数据项.数据项是构成数据元素的最小不可分割字段。可以看作一个pojo对象或者一张表(people)的一个属性/字段的值。

    数据对象:是相同性质数据元素的集合。是数据的一个子集。比如上面的users表、list集合、woman集合都是数据对象。单独一张表,一个集合都可以是一个数据对象。

    总的捋一捋,数据范围最广,所有数据即数据,而数据对象仅仅是有相同性质的一个集合,这个集合是数据的子集,但并不是数据的基本单位,而数据元素才是数据的基本单位。举个例子表cat和表dog都是数据,然后表cat是个数据对象(因为都描述cat这种对象),但是数据的基本单位并不是猫和狗,而是他们的具体的每一条,比如小猫咪1号,大猫咪二号,哈士奇1号,藏獒2号这些每一条才是数据的基本单位。

    还有数据类型,抽象数据类型也在下面讲一讲。

    数据类型

    原子类型:其值不可再分的类型。比如int,char,double,float等。

    结构类型:其值可以再分为若干成分的数据类型。比如结构体构造的各种结构等。

    抽象数据类型(ADT):抽象数据类型(ADT)是一个实现包括储存数据元素的存储结构以及实现基本操作的算法。使得只研究和使用它的结构而不用考虑它的实现细节成为可能。比如我们使用List、Map、Set等等只需要了解它的api和性质功能即可。而具体的实现可能是不同的方案,比如List的实现有数组和链表不同选择。

    三要素

    逻辑结构:数据元素之间的逻辑关系。逻辑结构分为线性结构非线性结构。线性结构就是顺序表、链表之类。而非线性就是集合、树、图这些结构。

    存储结构:数据结构在计算机中的表示(又称映像,也称物理结构),存储结构主要分为顺序存储链式存储索引存储散列(哈希)存储,这几种存储通过下面这张图简单了解一下(仅仅为理解不考虑更多):

    image-20201230110548234

    数据的运算:施加在数据上的运算包括运算的定义实现,运算的定义基于逻辑结构,运算的实现基于存储结构。

    在这里容易混淆的是逻辑结构与存储结构的概念。对于逻辑结构,不难看得出逻辑二字,逻辑关系也就是两者存在数据上的关系而不考虑物理地址的关系,比如线性结构和非线性结构,它描述的是一组数据中联系的方式和形式,他针对的是数据。看中的是数据结构的功能,比如线性表就是前后有序的,我需要一个有序的集合就可以使用线性表。

    存储结构就是跟物理地址挂钩的。因为同样逻辑结构采用不同存储结构实现适用场景和性能可能不同。比如同样是线性表,可能有多种存储结构的实现方式。比如顺序表链表(Arraylist,Linkedlist)它们的存储结构就不同,一个是顺序存储(数组)实现,一个是链式存储(链表)实现。它关注的是计算机运行物理地址的关系。但通常同一类存储结构实现的一些数据结构有一些类似的共同点和缺点(线性易查难插、链式易插难查等等)。

    算法分析

    上面讲了数据结构相关概念,下面对算法分析的一些概念进行描述。

    在这里插入图片描述

    算法的五个重要特征:有穷性、确定性、可行性、输入、输出。这些从字面意思即可理解,其中有穷性强调算法要有结束的时候不能无限循环;而确定性是每条指令有它意义,相同的输入得到相同的输出;可行性是指算法每个步骤经过若干次执行可以实现;输入是0个或多个输入(可0);输出是1个或多个输出(一定要有输出)。

    而一个好的算法,通常更要着重考虑的是效率和空间资源占用(时间复杂度和空间复杂度),通常复杂度更多描述的是一个量级程度而很少用具体数字描述。

    空间复杂度

    概念:是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))

    空间复杂度其实在算法的衡量占比是比较低的(我们经常使用牺牲空间换时间的数据结构和算法),但是不能忽视空间复杂度中重要性。无论在刷题还是实际项目生产内存都是一个极大额指标。对于Java而言更是如此。本身内存就大,如果采用的存储逻辑不太好会占用更多的系统资源,对服务造成压力。

    而算法很多情况都是牺牲空间换取时间(效率)。就比如我们熟知的字符串匹配String.contains()方法,我们都知道他是暴力破解,时间复杂度为O(n^2),不需要借助额外内存。而KMP算法在效率和速度上都原生暴力方法,但是KMP要借助其他数组(next[])进行标记储存运算。就用到了空间开销。再比如归并排序也会借助新数组在递归分冶的适合进行逐级计算,提高效率,但增加点影响不大的内存开销。

    当然,算法的空间花销最大不能超过jvm设置的最大值,一般为2G.(2147483645)如果开二维数组多种多维数据不要开的太大,可能会导致heap OutOfMemoryError

    时间复杂度

    概念:计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。

    时间复杂度的排序:O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) <O(n!) < O(n^n)

    常见时间复杂度:对于时间复杂度,很多人的概念是比较模糊的。下面举例子说明一些时间复杂度。

    O(1): 常数函数

    • a=15

    O(logn): 对数函数

    • for(int i=1;i<n;i*=2)
      分析:假设执行t次使得i=n;有2^t=n; t=log2~n,为log级别时间复杂度为O(logn)。
    • 还有典型的二分查找,拓展欧几里得,快速幂等算法均为O(logn)。属于高效率算法。

    O(n): 线性函数

    • for (int i=0;i<n;i++)
    • 比较常见,能够良好解决大部分问题。

    O(nlogn):

    • for (int i=1;i<n;i++)
      for (int j=1;j<i;j*=2)
    • 常见的排序算法很多正常情况都是nlogn,比如快排、归并排序。这种算法效率大部分也还不错。

    O(n^2)

    • for(int i=0;i<n;i++)
      for(int j=0;j<i;j++)
    • 其实O(n2)的效率就不敢恭维了。对于大的数据O(n2)甚至更高次方的执行效果会很差。

    当然如果同样是n=10000.那么不同时间复杂度额算法执行次数、时间也不同。

    具体 n 执行次数
    O(1) 10000 1
    O(log2n) 10000 14
    O( n^1/2) 10000 100
    O(n) 10000 10000
    O(nlog2 n) 10000 140000
    O(n^2) 10000 100000000
    O(n^3) 10000 1000000000000

    降低算法复杂度有些会靠数据结构的特性和优势,比如二叉排序树的查找,线段树的动态排序等等,这些数据结构解决某些问题有些非常良好的性能。还有的是靠算法策略解决,比如同样是排序,冒泡排序这种笨而简单的方法就是O(n2),但快排、归并等聪明方法就能O(nlogn)。要想变得更快,那就得掌握更高级的数据结构和更精巧的算法。

    时间复杂度计算
    时间复杂度计算一般步骤:1、找到执行次数最多的语句; 2、计算语句执行的数量级 ; 3、用O表示结果。并且有两个规则:

    加法规则: 同一程序下如果多个并列关系的执行语句那么取最大的那个,eg:

    T(n)=O(m)+O(n)=max(O(m),O(n)); 
    T(n)=O(n)+O(nlogn)=max(O(n),O(nlogn))=O(nlogn);
    

    乘法规则:循环结构,时间复杂度按乘法进行计算,eg:

    T(n)=O(m)*O(n)=O(mn)
    T(n)=O(m)*O(m)=O(m^2)(两层for循环)
    

    当然很多算法的时间复杂度还跟输入的数据有关,分为还会有最优时间复杂度(可能执行次数最少时),最坏时间复杂度(执行次数最少时),平均时间复杂度,这在排序算法中已经具体分析,但我们通常使用平均时间复杂度来衡量一个算法的好坏。

    数据结构与算法学习

    捋过数据结构与算法基本概念的介绍,在学习数据结构与算法方面,个人把经典的数据结构与算法学习过程步骤写在下面,希望能给大家一个参考:

    数据结构

    • 单链表(带头结点、不带头结点)设计与实现(增删改查),双链表设计与实现

    • 栈设计与实现(数组和链表),队列设计与实现(数组和链表)

    • 二叉树概念学习,二叉树前序、中序、后序遍历递归、非递归实现 ,层序遍历

    • 二叉排序树设计与实现(插入删除)

    • 堆(优先队列、堆排序)

    • AVL(平衡)树设计与实现(四种自旋方式理解实现)

    • 伸展树、红黑树原理概念理解

    • B、B+原理概念理解

    • 哈夫曼树原理概念理解(贪心策略)

    • 哈希(散列表)原理概念理解(几种解决哈希冲突方式)

    • 并查集/不相交集合(优化和路径压缩)

    • 图论拓扑排序

    • 图论dfs深度优先遍历、bfs广度优先遍历

    • 最短路径Dijkstra算法、Floyd算法、spfa算法

    • 最小生成树prim算法、kruskal算法

    • 其他数据结构线段树、后缀数组等等

    经典算法

    • 递归算法(求阶乘、斐波那契、汉诺塔问题)
    • 二分查找
    • 分治算法(快排、归并排序、求最近点对等问题)
    • 贪心算法(使用较多,区间选点问题,区间覆盖问题)
    • 常见动态规划(LCS(最长公共子序列) LIS(最长上升子序列)背包问题等等)
    • 回溯算法(经典八皇后问题、全排列问题)
    • 位运算常见问题(参考剑指offer和LeetCode问题)
    • 快速幂算法(快速求幂乘、矩阵快速幂)
    • kmp等字符串匹配算法
    • 一切其他数论算法(欧几里得、拓展欧几里得、中国剩余定理等等)

    相信看完这篇文章,你应该对数据结构与算法有个不错的认知。数据结构与算法有着非常密切的关联,数据结构是为了实现某种算法,算法是核心目的。学习数据结构与算法之前,可以先参考书本或者博客先了解其功能,再研究其运行原理,再动手实战(编写数据结构或者相关题目)这样层次渐进,想要深入的学习数据结构与算法光理解是不行的,需要有大量代码实战才可。并且这条路是没有止境的,活到老,学到老,刷到老。

    愿大家2021一起加油,2021我会把专栏数据结构与算法系列文章进行优化输出!这是第一篇,敬请期待!

    原创不易,bigsai请csdn的朋友们帮两件事帮忙一下:

    1. 点赞、在看、分享支持一下, 您的肯定是我创作的源源动力。

    2. 微信搜索「bigsai」,2021我需要你的支持!

    咱们下次再见!

    image-20201114211553660

    展开全文
  • 数据结构与算法之美

    千次阅读 2019-08-31 17:14:58
    数据结构是为算法服务的,算法要作用在特定的数据结构之上。 因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构。比如,因为数组具有随机访问的特点,常用的二分查找算法需要用数组来存储数据。但...

    1.介绍

    数据结构和算法解决的是如何更省、更快地存储和处理数据的问题.

    数据结构和算法是相辅相成的。数据结构是为算法服务的,算法要作用在特定的数据结构之上。 因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构。比如,因为数组具有随机访问的特点,常用的二分查找算法需要用数组来存储数据。但如果我们选择链表这种数据结构,二分查找算法就无法工作了,因为链表并不支持随机访问。数据结构是静态的,它只是组织数据的一种方式。如果不在它的基础上操作、构建算法,孤立存在的数据结构就是没用的

     

    知识结构

    2.应用背景

    主要应用于各个方面,特别是大数据量处理方面. 

    3.学习

    参考与输出

    https://github.com/ningxiaofa/data_structure_and_algorithm  // [个人]代码实现汇总

    https://blog.csdn.net/william_n/article/details/109038448 // 算法 - Leetcode - 练习题目 - 记录 - 20201012

    同时参考:

    https://github.com/pushaowei/arithmetic-php // 🐳 用 PHP 的方式实现的各类算法合集 🐳   ---20210308 公司

    https://github.com/wangzheng0822/algo. // 专栏 - 数据结构与算法之美 - 作者 - code实现

    https://github.com/gl-lei/algorithm // 基于专栏 - 数据结构与算法之美 - 优化

     

     

    课程目录
    已完结 73  讲

    专栏实现code: https://github.com/ningxiaofa/algorithm

    自我实现code: https://github.com/ningxiaofa/beauty_of_data_structures_and_algorithms

    开篇词 (1讲)
    开篇词 | 开篇词 | 从今天起,跨过“数据结构与算法”这道坎?

    入门篇 (4讲)

    01 | 为什么要学习数据结构和算法?

    02 | 如何抓住重点,系统高效地学习数据结构与算法?

    03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?

    04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度

     

     

    基础篇 (38讲)

    05 | 数组:为什么很多编程语言中数组都从0开始编号?

    https://blog.csdn.net/william_n/article/details/103142069

    06 | 链表(上):如何实现LRU缓存淘汰算法?

    https://blog.csdn.net/william_n/article/details/103147275

    07 | 链表(下):如何轻松写出正确的链表代码?

    https://blog.csdn.net/william_n/article/details/102573956

    08 | 栈:如何实现浏览器的前进和后退功能?

    https://blog.csdn.net/william_n/article/details/102573766

    09 | 队列:队列在线程池等有限资源池中的应用

    10 | 递归:如何用三行代码找到“最终推荐人”?

    11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?

    12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?

    13 | 线性排序:如何根据年龄给100万用户数据排序?

    14 | 排序优化:如何实现一个通用的、高性能的排序函数?

    15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?

    16 | 二分查找(下):如何快速定位IP对应的省份地址?

    17 | 跳表:为什么Redis一定要用跳表来实现有序集合?

    18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?

    19 | 散列表(中):如何打造一个工业级水平的散列表?

    20 | 散列表(下):为什么散列表和链表经常会一起使用?

    21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?

    22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?

    23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?

    24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?

    25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?

    26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树

    https://blog.csdn.net/william_n/article/details/115871105

    27 | 递归树:如何借助树来求解递归算法的时间复杂度?

    28 | 堆和堆排序:为什么说堆排序没有快速排序快?

    29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?

    30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?

    31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?

    32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?

    33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?

    34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?

    35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?

    36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?

    37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?

    38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想

    39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想

    40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?

    41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

    42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?

     

    高级篇 (9讲)

    43 | 拓扑排序:如何确定代码源文件的编译依赖关系?

    44 | 最短路径:地图软件是如何计算出最优出行路径的?

    45 | 位图:如何实现网页爬虫中的URL去重功能?

    46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?

    47 | 向量空间:如何实现一个简单的音乐推荐系统?

    48 | B+树:MySQL数据库索引是如何实现的?

    49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?

    50 | 索引:如何在海量数据中快速查找某个数据?

    51 | 并行算法:如何利用并行处理提高算法的执行效率?

     

    实战篇 (5讲)

    52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构

    53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法

    54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法

    55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法

    56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?

     

    加餐:不定期福利 (6讲)

    不定期福利第一期 | 数据结构与算法学习书单

    不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫

    不定期福利第三期 | 测一测你的算法阶段学习成果

    不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?

    总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?

    《数据结构与算法之美》学习指导手册

     

    加餐:春节7天练 (7讲)

    春节7天练 | Day 1:数组和链表

    春节7天练 | Day 2:栈、队列和递归

    春节7天练 | Day 3:排序和二分查找

    春节7天练 | Day 4:散列表和字符串

    春节7天练 | Day 5:二叉树和堆

    春节7天练 | Day 6:图

    春节7天练 | Day 7:贪心、分治、回溯和动态规划

     

    加餐:用户学习故事 (2讲)

    用户故事 | Jerry银银:这一年我的脑海里只有算法

    用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”

     

    结束语 (1讲)

    结束语 | 送君千里,终须一别

    4.推荐书籍

    从易至难总结一下数据结构书籍:
    1. 入门级:《大话数据结构》、《算法图解》
    2.面试:《剑指offer》、《编程珠玑》、《编程之美》
    3.不同语言:《数据结构与算法分析:c++描述》、《数据结构与算法分析:c语言描述》、《数据结构与算法分析:java语言描述》
    4.经典大部头:《算法导论》、《算法》
    5.殿堂级:《计算机程序设计艺术》
    6.闲暇时间阅读:《算法帝国》、《数学之美》、《算法之美》

    5.学习体会

    TBD

    6.参考

    极客时间专栏:数据结构与算法之美 --王争 以及不记名网友的评论见解

    https://blog.csdn.net/william_n/article/details/103092795。// 数据结构与算法之美-问题收集

    https://github.com/ningxiaofa/data_structure_and_algorithm  // [个人]代码实现汇总

    https://blog.csdn.net/william_n/article/details/109038448 // 算法 - Leetcode - 练习题目 - 记录 - 20201012

    https://github.com/pushaowei/arithmetic-php // 🐳 用 PHP 的方式实现的各类算法合集 🐳   ---20210308 公司

    https://github.com/wangzheng0822/algo. // 专栏 - 数据结构与算法之美 - 作者 - code实现

    https://github.com/gl-lei/algorithm // 基于专栏 - 数据结构与算法之美 - 优化

    后续补充... 

    展开全文
  • Java数据结构与算法入门

    万次阅读 多人点赞 2018-04-29 11:53:50
    第一部分:Java数据结构要理解Java数据结构,必须能清楚何为数据结构数据结构:Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。而各数据元素之间的相互关系,又...

    第一部分:Java数据结构

    要理解Java数据结构,必须能清楚何为数据结构?

    数据结构:

    1. Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。
    2. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构。
    3. 而一个数据结构的设计过程分成抽象层、数据结构层和实现层。

    数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构。

    一、Java数据结构之:线性数据结构

    线性数据结构:常见的有一维数组,线性表,栈,队列,双队列,串。

    1:一维数组

    在Java里面常用的util有:String [],int [],ArrayList,Vector,CopyOnWriteArrayList等。及可以同过一维数组[]自己实现不同逻辑结构的Util类。而ArrayList封装了一些[]的基本操作方法。ArrayList和Vector的区别是:Vector是线程安全的,方法同步。CopyOnWriteArrayList也是线程安全的但效率要比Vector高很多。(PS:如果不懂出门右拐看另一篇chat)。

    数组这种数据结构典型的操作方法,是根据下标进行操作的,所以insert的的时候可以根据下标插入到具体的某个位置,但是这个时候它后面的元素都得往后面移动一位。所以插入效率比较低,更新,删除效率也比较低,而查询效率非常高,查询效率时间复杂度是1。

    2: 线性表

    线性表是有序的储存结构、链式的储存结构。链表的物理储存空间是不连续的,链表的每一个节点都知道上一个节点、或者下一个节点是谁,通常用Node表示。常见的有顺序链表(LinkedList、Linked***),单项链表(里面只有Node类),双向链表(两个Node类),循环链表(多个Node类)等。

    操作方法:插入效率比较高,插入的时候只需要改变节点的前后节点的连接即可。而查询效率就比较低了,如果实现的不好,需要整个链路找下去才能找到应该找的元素。所以常见的方法有:add(index,element),addFirst(element),addLast(element)。getFirst(),getLast(),get(element)等。

    常见的Uitil有:LinkedList,LinkedMap等,而这两个JDK底层也做了N多优化,可以有效避免查询效率低的问题。当自己实现的时候需要注意。其实树形结构可以说是非线性的链式储存结构。

    3: 栈Stack

    栈,最主要的是要实现先进后出,后进先出的逻辑结构。来实现一些场景对逻辑顺序的要求。所以常用的方法有push(element)压栈,pop()出栈。

    java.util.Stack。就实现了这用逻辑。而Java的Jvm里面也用的到了此种数据结构,就是线程栈,来保证当前线程的执行顺序。

    4:队列

    队列,队列是一种特殊的线性数据结构,队列只能允许在队头,队尾进行添加和查询等相关操作。队列又有单项有序队列,双向队列,阻塞队列等。

    Queue这种数据结构注定了基本操作方法有:add(E e)加入队列,remove(),poll()等方法。

    队列在Java语言环境中是使用频率相当高的数据结构,所有其实现的类也很多来满足不同场景。


    使用场景也非常多,如线程池,mq,连接池等。

    5:串

    串:也称字符串,是由N个字符组成的优先序列。在Java里面就是指String,而String里面是由chat[]来进行储存。

    KMP算法: 这个算法一定要牢记,Java数据结构这本书里面针对字符串的查找匹配算法也只介绍了一种。关键点就是:在字符串比对的时候,主串的比较位置不需要回退的问题。

    二、Java数据结构之:非线性数据结构

    非线性数据结构:常见的有:多维数组,集合,树,图,散列表(hash).

    1:多维数组

    一维数组前面咱也提到了,多维数组无非就是String [][],int[][]等。Java里面很少提供这样的工具类,而java里面tree和图底层的native方法用了多维数组来储存。

    2:集合

    由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。

    Collection

    3:树

    树形结构,作者觉得它是一种特殊的链形数据结构。最少有一个根节点组成,可以有多个子节点。树,显然是由递归算法组成。

    树的特点:

    1. 在一个树结构中,有且仅有一个结点没有直接父节点,它就是根节点。
    2. 除了根节点,其他结点有且只有一个直接父节点
    3. 每个结点可以有任意多个直接子节点。

    树的数据结构又分如下几种:

    • 1) 自由树/普通树:对子节点没有任何约束。

      自由树

    • 2) 二叉树:每个节点最多含有两个子节点的树称为二叉树。

      2.1) 一般二叉树:每个子节点的父亲节点不一定有两个子节点的二叉树成为一般二叉树。

      2.2) 完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;

      2.3) 满二叉树:所有的节点都是二叉的二叉树成为满二叉树。

      二叉树

    • 3) 二叉搜索树/BST:binary search tree,又称二叉排序树、二叉查找树。是有序的。要点:如果不为空,那么其左子树节点的值都小于根节点的值;右子树节点的值都大于根节点的值。

      二叉搜索树

      3.1) 二叉平衡树:二叉搜索树,是有序的排序树,但左右两边包括子节点不一定平衡,而二叉平衡树是排序树的一种,并且加点条件,就是任意一个节点的两个叉的深度差不多(比如差值的绝对值小于某个常数,或者一个不能比另一个深出去一倍之类的)。这样的树可以保证二分搜索任意元素都是O(log n)的,一般还附带带有插入或者删除某个元素也是O(log n)的的性质。

      为了实现,二叉平衡树又延伸出来了一些算法,业界常见的有AVL、和红黑算法,所以又有以下两种树:

      3.1.1) AVL树:最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。

      3.1.2) 红黑树:通过制定了一些红黑标记和左右旋转规则来保证二叉树平衡。

      红黑树的5条性质:

      1. 每个结点要么是红的,要么是黑的。
      2. 根结点是黑的。
      3. 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。
      4. 如果一个结点是红的,那么它的俩个儿子都是黑的。
      5. 对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

      红黑树

    • 4) B-tree:又称B树、B-树。又叫平衡(balance)多路查找树。树中每个结点最多含有m个孩子(m>=2)。它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。

      B-tree

    • 4) B+tree:又称B+。是B-树的变体,也是一种多路搜索树。

      B+tree

    树总结:
    树在Java里面应用的也比较多。非排序树,主要用来做数据储存和展示。而排序树,主要用来做算法和运算,HashMap里面的TreeNode就用到了红黑树算法。而B+树在数据库的索引原理里面有典型的应用。

    4:Hash

    Hash概念:

    • Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),变换成固定长度的输出,该输出就是散列值。一般通过Hash算法实现。

    • 所谓的Hash算法都是散列算法,把任意长度的输入,变换成固定长度的输出,该输出就是散列值.(如:MD5,SHA1,加解密算法等)

    • 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

    Java中的hashCode:

    • 我们都知道所有的class都是Object的子类,既所有的class都会有默认Object.java里面的hashCode的方法,如果自己没有重写,默认情况就是native方法通过对象的内存的+对象的值然后通过hash散列算法计算出来个int的数字。

    • 最大的特性是:不同的对象,不同的值有可能计算出来的hashCode可能是一样的。

    Hash表:

    • Java中数据存储方式最底层的两种结构,一种是数组,另一种就是链表。而Hash表就是综合了这两种数据结构。

    • 如:HashTable,HashMap。这个时候就得提一下HashMap的原理了,默认16个数组储存,通过Hash值取模放到不同的桶里面去。(注意:JDK1.8此处算法又做了改进,数组里面的值会演变成树形结构。)

    • 哈希表具有较快(常量级)的查询速度,及相对较快的增删速度,所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”,我们可以理解为“链表的数组”。

      哈希表

    一致性Hash:

    • 我们查看一下HashMap的原理,其实发现Hash很好的解决了单体应用情况下的数据查找和插入的速度问题。但是毕竟单体应用的储存空间是有限的,所有在分布式环境下,应运而生了一致性Hash算法。

    • 用意和hashCode的用意一样,只不过它是取模放在不同的IP机器上而已。具体算法可以找一下相关资料。

    • 而一致性Hash需要注意的就是默认分配的桶比较多些,而当其中一台机器挂了,影响的面比较小一些。

    • 需要注意的是,相同的内容算出来的hash一定是一样的。既:幂等性。

    • 一致性Hash

    第二部分:Java基本算法

    理解了Java数据结构,还必须要掌握一些常见的基本算法。 理解算法之前必须要先理解的几个算法的概念:

    空间复杂度:一句来理解就是,此算法在规模为n的情况下额外消耗的储存空间。

    时间复杂度:一句来理解就是,此算法在规模为n的情况下,一个算法中的语句执行次数称为语句频度或时间频度。

    稳定性:主要是来描述算法,每次执行完,得到的结果都是一样的,但是可以不同的顺序输入,可能消耗的时间复杂度和空间复杂度不一样。

    一、二分查找算法

    二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。这个是基础,最简单的查找算法了。

        public static void main(String[] args) {
            int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
            System.out.println(binSearch(srcArray, 28));
        }
        /**
         * 二分查找普通循环实现
         *
         * @param srcArray 有序数组
         * @param key 查找元素
         * @return
         */
        public static int binSearch(int srcArray[], int key) {
            int mid = srcArray.length / 2;
    //        System.out.println("=:"+mid);
            if (key == srcArray[mid]) {
                return mid;
            }
    
    //二分核心逻辑
            int start = 0;
            int end = srcArray.length - 1;
            while (start <= end) {
    //            System.out.println(start+"="+end);
                mid = (end - start) / 2 + start;
                if (key < srcArray[mid]) {
                    end = mid - 1;
                } else if (key > srcArray[mid]) {
                    start = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
    

    二分查找算法如果没有用到递归方法的话,只会影响CPU。对内存模型来说影响不大。时间复杂度log2n,2的开方。空间复杂度是2。一定要牢记这个算法。应用的地方也是非常广泛,平衡树里面大量采用。

    二、递归算法

    递归简单理解就是方法自身调用自身。

        public static void main(String[] args) {
            int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
            System.out.println(binSearch(srcArray, 0,15,28));
        }
        /**
         * 二分查找递归实现
         *
         * @param srcArray  有序数组
         * @param start 数组低地址下标
         * @param end   数组高地址下标
         * @param key  查找元素
         * @return 查找元素不存在返回-1
         */
        public static int binSearch(int srcArray[], int start, int end, int key) {
            int mid = (end - start) / 2 + start;
            if (srcArray[mid] == key) {
                return mid;
            }
            if (start >= end) {
                return -1;
            } else if (key > srcArray[mid]) {
                return binSearch(srcArray, mid + 1, end, key);
            } else if (key < srcArray[mid]) {
                return binSearch(srcArray, start, mid - 1, key);
            }
            return -1;
        }
    

    递归几乎会经常用到,需要注意的一点是:递归不光影响的CPU。JVM里面的线程栈空间也会变大。所以当递归的调用链长的时候需要-Xss设置线程栈的大小。

    三、八大排序算法

    • 一、直接插入排序(Insertion Sort)
    • 二、希尔排序(Shell Sort)
    • 三、选择排序(Selection Sort)
    • 四、堆排序(Heap Sort)
    • 五、冒泡排序(Bubble Sort)
    • 六、快速排序(Quick Sort)
    • 七、归并排序(Merging Sort)
    • 八、基数排序(Radix Sort)

    八大算法,网上的资料就比较多了。

    吐血推荐参考资料:git hub 八大排序算法详解。此大神比作者讲解的还详细,作者就不在这里,描述重复的东西了,作者带领大家把重点的两个强调一下,此两个是必须要掌握的。

    1:冒泡排序

    基本思想:

    冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    冒泡排序

    以下是冒泡排序算法复杂度:

    平均时间复杂度最好情况最坏情况空间复杂度
    O(n²)O(n)O(n²)O(1)

    冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).

    Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.

    /**
     * 冒泡排序
     *
     * ①. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
     * ②. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
     * ③. 针对所有的元素重复以上的步骤,除了最后一个。
     * ④. 持续每次对越来越少的元素重复上面的步骤①~③,直到没有任何一对数字需要比较。
     * @param arr  待排序数组
     */
    public static void bubbleSort(int[] arr){
        for (int i = arr.length; i > 0; i--) {      //外层循环移动游标
            for(int j = 0; j < i && (j+1) < i; j++){    //内层循环遍历游标及之后(或之前)的元素
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    System.out.println("Sorting: " + Arrays.toString(arr));
                }
            }
        }
    }
    

    2:快速排序

    快速排序

    快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:

    ①. 从数列中挑出一个元素,称为”基准”(pivot)。

    ②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

    ③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

    代码实现:

    用伪代码描述如下:

    ①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。

    ②.j--,由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

    ③.i++,由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

    ④.再重复执行②,③二步,直到i==j,将基准数填入a[i]中。

    快速排序采用“分而治之、各个击破”的观念,此为原地(In-place)分区版本。

    快速排序 In-place

    /**
     * 快速排序(递归)
     *
     * ①. 从数列中挑出一个元素,称为"基准"(pivot)。
     * ②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
     * ③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
     * @param arr   待排序数组
     * @param low   左边界
     * @param high  右边界
     */
    public static void quickSort(int[] arr, int low, int high){
        if(arr.length <= 0) return;
        if(low >= high) return;
        int left = low;
        int right = high;
        int temp = arr[left];   //挖坑1:保存基准的值
        while (left < right){
            while(left < right && arr[right] >= temp){  //坑2:从后向前找到比基准小的元素,插入到基准位置坑1中
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= temp){   //坑3:从前往后找到比基准大的元素,放到刚才挖的坑2中
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;   //基准值填补到坑3中,准备分治递归快排
        System.out.println("Sorting: " + Arrays.toString(arr));
        quickSort(arr, low, left-1);
        quickSort(arr, left+1, high);
    }
    

    以下是快速排序算法复杂度:

    平均时间复杂度最好情况最坏情况空间复杂度
    O(nlog₂n)O(nlog₂n)O(n²)O(1)(原地分区递归版)

    快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高.


    最后,作者希望让大家对《Java数据结构》整体有个全面的了解,知道什么是数据结构,离我们工作中有多远,而不是一个深不可测的神秘物件。里面的细节,篇幅有限可能不能描述完,但是只要同学们的方向没有搞错,那只要针对每个点再详细的看看即可。

    面试和工作,这些都是离不开的,当同学们有个完整的认识之后,一定要在工作中留心,留意每个用到的地方。

    更多精彩教程,请关注公众号:Java开发教程视频      


    展开全文
  • 数据结构教科上开篇就是“什么是数据结构?”,这里我也就不多说了,没意思。 我总是把“数据结构”和“算法”这两个词语看做是一样的(个人而言哈),我们倒不如说说算法能干什么,学习数据结构能干什么? 不知道...
  • 数据结构算法经典书籍

    千次阅读 2016-03-04 18:53:50
    在职软件工程师建议学习Sahni(萨尼)的《数据结构算法与应用 C++语言描述》,算法部分可以参考Horowitz(霍罗威茨)的《计算机算法(C++版)》。 本书没那么多公式,实际应用结合紧密,作者给出了所有的代码,...
  • 用Python解决数据结构与算法问题(一):Python基础

    万次阅读 多人点赞 2019-09-29 09:51:44
    python学习之路 - 从入门到精通到大师 文章目录[python学习之路 - 从入门...回顾Python基础1.8.数据入门1.8.1.内置的原子数据类型1.8.2.内置的集合数据类型 1.7.回顾Python基础 在本节中,我们将回顾 Python 编程语...
  • 常见数据结构与算法整理总结

    千次阅读 多人点赞 2018-01-10 14:03:30
    下面是自己整理的常用数据结构与算法相关内容,如有错误,欢迎指出。 为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是...
  • 学习数据结构与算法一个很重要的前提,就是至少熟练掌握一门编程语言。至于是那种语言就无关紧要了,C 语言、C++、Java、Python 等语言都可以。因为无论是数据结构还是算法,它教会我们的是解决问题的思想,并不挂靠...
  • 如何学习数据结构与算法

    千次阅读 2018-04-30 22:51:35
    我觉得入门学习算法与数据结构时应包含三个部分: 选择一本合适的。 编程实现和应用。 反复学习。 1、选择一本合适的  我是用的是算法第四版,因为我是学java出身,而这本书中使用Java代码进行实现,学习...
  • 有关数据结构与算法方面的经典书籍推荐

    万次阅读 多人点赞 2018-08-17 14:41:05
    下面列出一份数据结构算法书目,先从最著名的说起 A 原书名:The Art of Computer Programming 中文名:计算机程序设计艺术 作者:Donald E.Knuth 难度:***** 个人评价:******* 推荐程度:**** .....
  • 数据结构与算法 -- 栈 ADT

    千次阅读 2017-02-14 10:08:09
    这两天翻了下数据结构与算法分析和严蔚敏的数据结构这两本,受益很多。不过大多的示例不够完整,需要自己动手编写程序。又看了遍培训时的笔记,虽然很糙但是精华的部分还是可以借鉴的。还有看到了不错的博文,参看...
  • c/c++ 数据结构与算法

    千次阅读 多人点赞 2019-02-14 11:13:44
    参考;... 程序设计 = 数据结构 + 算法 1.数据结构 数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。... 因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构数据结构...
  • 数据结构与算法(Java笔记15天)

    千次阅读 多人点赞 2020-06-07 09:17:54
    文章目录Java数据结构与算法前言目录结束 Java数据结构与算法 前言 源码:https://github.com/name365/Java-Data-structure 目录 名称 地址 第一章 稀疏数组 ...htt
  • 数据结构算法常见面试考题

    万次阅读 多人点赞 2018-11-08 09:29:44
    数据结构上几种树集中的讨论一下: 1.AVLtree 定义:最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)...
  • 数据结构与算法书籍推荐

    千次阅读 2010-02-23 10:50:00
    Niklaus Wirth说:算法+数据结构=程序,不说废话了,下面列出一份数据结构算法书目,先从最著名的说起A原书名:The Art of Computer Programming中文名:计算机程序设计艺术作者:Donald E.Knuth难度:
  • 前言都说数据结构与算法分析是程序员的内功,想要理解计算机世界就不能不懂点数据结构与算法,然而这也备受争议,因为大多数的业务需求都用不上数据结构与算法,又或者说已经有封装好的库可以直接调用,例如Java中的...
  • 数据结构与算法 相关经典书籍推荐

    千次阅读 2012-09-02 11:27:39
    Niklaus Wirth说:算法+数据结构=程序,不说废话了,下面列出一份数据结构算法书目,先从最著名的说起 A 原书名:The Art of Computer Programming 中文名:计算机程序设计艺术 作者:Don
  • python学习之路 - 从入门到精通到大师 文章目录[python学习之路 - 从入门到...目标3.2.什么是线性数据结构3.3.什么是栈3.4.栈的抽象数据类型3.5.Python实现栈3.6.简单括号匹配3.7.符号匹配3.8.十进制转换成二进制...
  • 学习数据结构与算法参考书是《数据结构与算法分析c++描述》一书。  首先看的是最基本的ADT(抽象数据结构)表、栈、队列。  1、表:是一种有限且有序的序列。实现的方式有两种:数组(所有操作都可以用数组来实现...
  • 目录 一、蓝桥杯题库 1.1VIP试题提交平台步骤 1.2入门训练 1.3基础练习 1.4 蓝桥杯真题 二、Python数据结构与算法 2.1各类算法的一些简单题目(每个博客都带有原题目链接和python解法) 2.2深度优先搜索DFS和广度...
  • 买了不少数据结构书 不知道哪些适合我 目前准大二 即将开数据结构数据结构与算法分析 c语言描述 数据结构与算法分析 java语言描述 算法四 就红色那本书 算法导论 大话数据结构 感觉有点贪多了 目前...
  • 我回答他算法,而他说我对语言学的太心急,太快,不像是喜欢算法的,并和我说算法玩玩就好,不要陷得太深,并建议我走一般开发的路子。虽然学长学的挺好,但就比我大一岁,我还是不太相信他说的。后来在学校acm实验...
  • 数据结构与算法分析—C语言描述 高清版

    千次下载 热门讨论 2008-04-05 21:01:56
    本书是国外数据结构与算法分析方面的标准教材,介绍了数据结构(大量数据的组织方法)以及算法分析(算法运行时间的估算)。本书的编写目标是同时讲授好的程序设计和算法分析技巧,使读者可以开发出具有最高效率的...
  • 数据结构与算法】之跳表(Java实现)---第九篇

    万次阅读 多人点赞 2018-10-30 17:35:10
    说明:跳表是一种不太常用的数据结构,很多书籍上甚至都没有提及过,我也是学习极客时间中的《数据结构与算法之美》专栏的时候才知道这种数据结构,但是感觉这种数据结构真的有很多优点,看了一些博客讲的都很片面,...
  • Java数据结构与算法解析(一)——表

    万次阅读 多人点赞 2017-08-27 13:27:07
    本节我们讨论常见常用的数据结构——表。 如果要通俗简单的说什么是表,那我们可以这样说:按顺序排好的元素集合就是表。表的概述抽象数据类型是带有一组操作的一些对象的结合1、定义: 线性表是一个线性结构,它...
  • 数据结构与算法分析—C语言描述 pdf

    千次阅读 2018-11-14 18:41:25
    数据结构与算法分析—C语言描述 pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 109,999
精华内容 43,999
关键字:

数据结构与算法参考书

数据结构 订阅