JasonsGong/JasonsGong.github.io
1
0
Fork 0
mirror of https://github.com/JasonsGong/JasonsGong.github.io.git synced 2024-11-24 11:49:36 +08:00
Code Issues Actions Packages Projects Releases Wiki Activity
main
JasonsGong.github.io/posts/40445.html

558 lines
527 KiB
HTML
Raw Permalink Normal View History

Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0,viewport-fit=cover"><title>数据结构与算法 | The Blog</title><meta name="author" content="Jason"><meta name="copyright" content="Jason"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="代码仓库的地址:https:&#x2F;&#x2F;gitee.com&#x2F;JasonsGong&#x2F;DataStructures 一.经典算法问题字符串匹配 KMP算法 汉诺塔问题 分治算法 八皇后问题 回溯算法 马踏棋盘问题 图的深度优化遍历算法(DFS)和 贪心算法优化 二.数据结构与算法的概述2.1 数据结构与算法的关系（1）数据(data)结构(structure)是一门研究组织数">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构与算法">
Site updated: 2024-05-10 10:21:29
2024-05-10 10:21:35 +08:00
<meta property="og:url" content="https://qingling.icu/posts/40445.html">
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
<meta property="og:site_name" content="The Blog">
<meta property="og:description" content="代码仓库的地址:https:&#x2F;&#x2F;gitee.com&#x2F;JasonsGong&#x2F;DataStructures 一.经典算法问题字符串匹配 KMP算法 汉诺塔问题 分治算法 八皇后问题 回溯算法 马踏棋盘问题 图的深度优化遍历算法(DFS)和 贪心算法优化 二.数据结构与算法的概述2.1 数据结构与算法的关系（1）数据(data)结构(structure)是一门研究组织数">
<meta property="og:locale" content="zh_CN">
Site updated: 2024-06-14 22:00:18
2024-06-14 22:00:25 +08:00
<meta property="og:image" content="https://qingling.icu/img/4.png">
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
<meta property="article:published_time" content="2023-03-13T03:31:58.000Z">
Site updated: 2024-04-02 11:00:40
2024-04-02 11:00:46 +08:00
<meta property="article:modified_time" content="2024-04-02T02:52:59.937Z">
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
<meta property="article:author" content="Jason">
<meta property="article:tag" content="数据结构与算法">
<meta name="twitter:card" content="summary">
Site updated: 2024-06-14 22:00:18
2024-06-14 22:00:25 +08:00
<meta name="twitter:image" content="https://qingling.icu/img/4.png"><link rel="shortcut icon" href="/img/%E5%9B%BE%E6%A0%87.png"><link rel="canonical" href="https://qingling.icu/posts/40445.html"><link rel="preconnect" href="//fastly.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="/cdn/icon/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="/cdn/css/snackbar.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="/cdn/css/fancybox.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
root: '/',
algolia: undefined,
localSearch: {"path":"/search.xml","preload":true,"top_n_per_article":1,"unescape":false,"languages":{"hits_empty":"找不到您查询的内容：${query}","hits_stats":"共找到 ${hits} 篇文章"}},
translate: undefined,
noticeOutdate: undefined,
highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":400},
copy: {
success: '复制成功',
error: '复制错误',
noSupport: '浏览器不支持'
},
relativeDate: {
homepage: true,
post: true
},
runtime: '天',
dateSuffix: {
just: '刚刚',
min: '分钟前',
hour: '小时前',
day: '天前',
month: '个月前'
},
copyright: undefined,
lightbox: 'mediumZoom',
Site updated: 2023-12-09 14:20:53
2023-12-09 14:21:01 +08:00
Snackbar: {"chs_to_cht":"你已切换为繁体","cht_to_chs":"你已切换为简体","day_to_night":"你已切换为深色模式","night_to_day":"你已切换为浅色模式","bgLight":"#006650","bgDark":"#006650","position":"top-center"},
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
source: {
justifiedGallery: {
Site updated: 2023-09-30 18:36:20
2023-09-30 18:36:25 +08:00
js: 'https://fastly.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.js',
css: 'https://fastly.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.css'
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
}
},
isPhotoFigcaption: false,
islazyload: false,
Site updated: 2023-12-10 21:56:51
2023-12-10 21:57:00 +08:00
isAnchor: true,
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
percent: {
toc: true,
rightside: false,
},
Site updated: 2023-12-09 19:59:27
2023-12-09 19:59:36 +08:00
autoDarkmode: true
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
title: '数据结构与算法',
isPost: true,
isHome: false,
isHighlightShrink: false,
isToc: true,
Site updated: 2024-04-02 11:00:40
2024-04-02 11:00:46 +08:00
postUpdate: '2024-04-02 10:52:59'
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
}</script><noscript><style type="text/css">
#nav {
opacity: 1
}
.justified-gallery img {
opacity: 1
}
#recent-posts time,
#post-meta time {
display: inline !important
}
</style></noscript><script>(win=>{
win.saveToLocal = {
set: function setWithExpiry(key, value, ttl) {
if (ttl === 0) return
const now = new Date()
const expiryDay = ttl * 86400000
const item = {
value: value,
expiry: now.getTime() + expiryDay,
}
localStorage.setItem(key, JSON.stringify(item))
},
get: function getWithExpiry(key) {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = new Date()
if (now.getTime() > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = url => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
document.head.appendChild(script)
})
win.getCSS = (url,id = false) => new Promise((resolve, reject) => {
const link = document.createElement('link')
link.rel = 'stylesheet'
link.href = url
if (id) link.id = id
link.onerror = reject
link.onload = link.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
link.onload = link.onreadystatechange = null
resolve()
}
document.head.appendChild(link)
})
win.activateDarkMode = function () {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = function () {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
const t = saveToLocal.get('theme')
Site updated: 2023-12-09 19:59:27
2023-12-09 19:59:36 +08:00
const isDarkMode = window.matchMedia('(prefers-color-scheme: dark)').matches
const isLightMode = window.matchMedia('(prefers-color-scheme: light)').matches
const isNotSpecified = window.matchMedia('(prefers-color-scheme: no-preference)').matches
const hasNoSupport = !isDarkMode && !isLightMode && !isNotSpecified
if (t === undefined) {
if (isLightMode) activateLightMode()
else if (isDarkMode) activateDarkMode()
else if (isNotSpecified || hasNoSupport) {
const now = new Date()
const hour = now.getHours()
const isNight = hour <= 8 || hour >= 22
isNight ? activateDarkMode() : activateLightMode()
}
window.matchMedia('(prefers-color-scheme: dark)').addListener(function (e) {
if (saveToLocal.get('theme') === undefined) {
e.matches ? activateDarkMode() : activateLightMode()
}
})
} else if (t === 'light') activateLightMode()
else activateDarkMode()
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
const detectApple = () => {
if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
document.documentElement.classList.add('apple')
}
}
detectApple()
Site updated: 2024-06-14 22:00:18
2024-06-14 22:00:25 +08:00
})(window)</script><script src="https://apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script><script type="text/javascript" src ="/js/welcome.js" ></script><script src="/js/sweetalert.js"></script><link rel="stylesheet" href="/css/sweetalert.css"><!-- hexo injector head_end start --><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiperstyle.css" media="print" onload="this.media='all'"><!-- hexo injector head_end end --><meta name="generator" content="Hexo 6.3.0"></head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="/img/avatar.jpg" onerror="onerror=null;src='/img/loading.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">60</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">39</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">10</div></a></div><br/><div class="menus_items"><div class="menus_item"><a class="site-page" target="_blank" rel="noopener" href="https://www.tutorialspoint.com/compile_java8_online.php"><i class="fa-fw fas fa-code"></i><span> 代码</span></a></div><div class="menus_item"><a class="site-page" href="/notice/"><i class="fa-fw fas fa-stream"></i><span> 公告</span></a></div><div class="menus_item"><a class="site-page" href="/website/"><i class="fa-fw fas fa-list"></i><span> 网址</span></a></div><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="not-top-img" id="page-header"><nav id="nav"><span id="blog-info"><a href="/" title="The Blog"><img class="site-icon" src="/img/logo.png"/><span class="site-name">The Blog</span></a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search" href="javascript:void(0);"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" target="_blank" rel="noopener" href="https://www.tutorialspoint.com/compile_java8_online.php"><i class="fa-fw fas fa-code"></i><span> 代码</span></a></div><div class="menus_item"><a class="site-page" href="/notice/"><i class="fa-fw fas fa-stream"></i><span> 公告</span></a></div><div class="menus_item"><a class="site-page" href="/website/"><i class="fa-fw fas fa-list"></i><span> 网址</span></a></div><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);"><i class="fas fa-bars fa-fw"></i></a></div></div></nav></header><main class="layout" id="content-inner"><div id="post"><div id="post-info"><h1 class="post-title">数据结构与算法</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2023-03-13T03:31:58.000Z" title="发表于 2023-03-13 11:31:58">2023-03-13</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2024-04-02T02:52:59.937Z" title="更新于 2024-04-02 10:52:59">2024-04-02</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E5%90%8E%E7%AB%AF/">后端</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-cou
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
<h2 id="一-经典算法问题"><a href="#一-经典算法问题" class="headerlink" title="一.经典算法问题"></a>一.经典算法问题</h2><p>字符串匹配 KMP算法 </p>
<p>汉诺塔问题 分治算法</p>
<p>八皇后问题 回溯算法 </p>
<p>马踏棋盘问题 图的深度优化遍历算法(DFS)和 贪心算法优化</p>
<h2 id="二-数据结构与算法的概述"><a href="#二-数据结构与算法的概述" class="headerlink" title="二.数据结构与算法的概述"></a>二.数据结构与算法的概述</h2><h3 id="2-1-数据结构与算法的关系"><a href="#2-1-数据结构与算法的关系" class="headerlink" title="2.1 数据结构与算法的关系"></a>2.1 数据结构与算法的关系</h3><p>（1）数据(data)结构(structure)是一门研究组织数据方式的学科，有了编程语言也就有了数据结构，学好了数据结构可以编写出更加漂亮，更加有效率的代码。</p>
<p>（2）程序&#x3D;数据结构+算法</p>
<p>（3）数据结构是算法的基础</p>
<h3 id="2-2解决实际的问题"><a href="#2-2解决实际的问题" class="headerlink" title="2.2解决实际的问题"></a>2.2解决实际的问题</h3><p>五子棋程序 稀疏数组（压缩存档） 二维数组-&gt;转化成稀疏数组-&gt;存档 读档反之</p>
<p>约瑟夫问题(丢手帕问题) 单向环形列表</p>
<p>修路问题 求最小生成树 + 普利姆算法</p>
<p>最短路径问题 图+弗洛伊德算法</p>
<h3 id="2-3-数据结构"><a href="#2-3-数据结构" class="headerlink" title="2.3 数据结构"></a>2.3 数据结构</h3><p>线性结构:</p>
<p>​ 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系</p>
<p>​ 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的</p>
<p>​ 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息</p>
<p>​ 线性结构常见的有：数组、队列、链表和栈</p>
<p>非线性结构:</p>
<p>​ 二维数组，多维数组，广义表，树结构，图结构</p>
<h2 id="三-稀疏数组和队列"><a href="#三-稀疏数组和队列" class="headerlink" title="三.稀疏数组和队列"></a>三.稀疏数组和队列</h2><h3 id="3-1稀疏数组"><a href="#3-1稀疏数组" class="headerlink" title="3.1稀疏数组"></a>3.1稀疏数组</h3><h4 id="3-1-1-基本的介绍"><a href="#3-1-1-基本的介绍" class="headerlink" title="3.1.1 基本的介绍"></a>3.1.1 基本的介绍</h4><p>​ 当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。</p>
<p>稀疏数组的处理方法是:</p>
<p>​ 1)记录数组一共有几行几列，有多少个不同的值</p>
<p>​ 2)把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模</p>
<h4 id="3-1-2使用的场景"><a href="#3-1-2使用的场景" class="headerlink" title="3.1.2使用的场景"></a>3.1.2使用的场景</h4><p>​ 五子棋程序的存档和退出功能的实现</p>
<h4 id="3-1-3图解"><a href="#3-1-3图解" class="headerlink" title="3.1.3图解"></a>3.1.3图解</h4><p>第一行记录的是原始的数组有几行几列有几个非零的值 例如下面的数组是一个6行7列有8个非零值的数组</p>
<p><img src="/pictures/image-20230313124552408.png" alt="image-20230313124552408"></p>
<h4 id="3-1-5实现的思路"><a href="#3-1-5实现的思路" class="headerlink" title="3.1.5实现的思路"></a>3.1.5实现的思路</h4><p><img src="/pictures/image-20230318100138197.png" alt="image-20230318100138197"></p>
<h4 id="3-1-5代码实现"><a href="#3-1-5代码实现" class="headerlink" title="3.1.5代码实现"></a>3.1.5代码实现</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.sparsearray;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/3/18</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 稀疏数组的代码实现 稀疏数组和二维数组之间的互转</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">SparseArray</span> &#123;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">
<h3 id="3-2队列"><a href="#3-2队列" class="headerlink" title="3.2队列"></a>3.2队列</h3><h4 id="3-2-1基本的介绍"><a href="#3-2-1基本的介绍" class="headerlink" title="3.2.1基本的介绍"></a>3.2.1基本的介绍</h4><p>先进先出</p>
<p> 队列是一个有序列表，可以通过数组或者链表实现。</p>
<p> 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入队列的数据要后取出。</p>
<h4 id="3-2-2代码实现"><a href="#3-2-2代码实现" class="headerlink" title="3.2.2代码实现"></a>3.2.2代码实现</h4><p> 使用数组模拟队列 </p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class=
<h4 id="3-2-3-数组模拟环形队列"><a href="#3-2-3-数组模拟环形队列" class="headerlink" title="3.2.3 数组模拟环形队列"></a>3.2.3 数组模拟环形队列</h4><p>环形队列的思路分析</p>
<ul>
<li>环形队列满的条件:(rear + 1) % maxSize &#x3D;&#x3D; front</li>
<li>环形队列空的条件:rear &#x3D;&#x3D; front</li>
<li>环形队列中有效数据的个数: (rear + maxSize - front) % maxSize</li>
</ul>
<p><img src="/pictures/image-20230428124659873.png" alt="image-20230428124659873"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class=
<h2 id="四-链表"><a href="#四-链表" class="headerlink" title="四.链表"></a>四.链表</h2><h3 id="4-1-链表-Linked-List-介绍"><a href="#4-1-链表-Linked-List-介绍" class="headerlink" title="4.1 链表(Linked List)介绍"></a>4.1 链表(Linked List)介绍</h3><p>在内存中不是连续存储的</p>
<h3 id=""><a href="#" class="headerlink" title=""></a><img src="/pictures/image-20230428134234636.png"></h3><p>链表的逻辑结构</p>
<p><img src="/pictures/image-20230428135032883.png" alt="image-20230428135032883"></p>
<h3 id="4-2单链表的应用实例-CRUD"><a href="#4-2单链表的应用实例-CRUD" class="headerlink" title="4.2单链表的应用实例(CRUD)"></a>4.2单链表的应用实例(CRUD)</h3><p>使用带head头的单向链表实现 –水浒英雄排行榜管理 完成对英雄人物的增删改查操作</p>
<h4 id="4-2-1向单链表中添加数据"><a href="#4-2-1向单链表中添加数据" class="headerlink" title="4.2.1向单链表中添加数据"></a>4.2.1向单链表中添加数据</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.linkedlist;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/4/28</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 单链表的实现</span></span><br><span class="line"><span class="comment"> * 使用带head头的单向链表实现 –水浒英雄排行榜管理</span></span><br><span class="line"><span class="comment"> * 完成对英雄人物的增删改查操作</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">SingleLinkedListDemo</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span cl
<h4 id="4-2-2修改单链表中节点的方法"><a href="#4-2-2修改单链表中节点的方法" class="headerlink" title="4.2.2修改单链表中节点的方法"></a>4.2.2修改单链表中节点的方法</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 修改节点的信息</span></span><br><span class="line"><span class="comment"> * 根据新的节点的编号进行修改</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">update</span><span class="params">(HeroNode newHeroNode)</span> &#123;</span><br><span class="line"> <span class="comment">//判断链表是否为空</span></span><br><span class="line"> <span class="keyword">if</span> (head.next == <span class="literal">null</span>) &#123;</span><br><span class="line"> System.out.println(<span class="string">&quot;链表为空,无法修改该节点!&quot;</span>);</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="comment">//找到需要修改的节点</span></span><br><span class="line"> <span class="comment">//首先找到头节点的位置</span></span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">temp</span> <span class="operator">=</span> head.next;</span><br><span class="line"> <span class="type">boolean</span> <span class="variable">idFind</span> <span class="operator">=</span> <span class="literal">false</span>; <span class="comment">//是否找到节点的信息</span></span><br><span class="line"> <span class="keyword">while</span> (<span class="literal">true</span>) &#123;</span><br><span class="line"> <span class="keyword">if</span> (temp == <span class="literal">null</span>) &#123;</span><br><span class="line"> <span class="keyword">break</span>;<span class="comment">//已经到了链表的结尾,就退出循环</span></span><br><span class="line"> &#125;</span><br><span class="line"> <span class="keyword">if</span> (temp.no == newHeroNode.no) &#123;<span class="comment">//找到修改的节点</span></span><br><span class="line"> temp.name = newHeroNode.name;</span><br><span class="line"> temp.nickname = newHeroNode.nickname;</span><br><span class="line"> idFind = <span class="literal">true</span>; <span class="comment">//找到了节点并且修改了节点的信息</span></span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> temp = temp.next;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="comment">//做出判断,返回结果</span></span><br><span class="line"> System.out.println(idFind ? <span class="string">&quot;修
<h4 id="4-2-3删除单链表中节点的方法"><a href="#4-2-3删除单链表中节点的方法" class="headerlink" title="4.2.3删除单链表中节点的方法"></a>4.2.3删除单链表中节点的方法</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 删除链表中的节点</span></span><br><span class="line"><span class="comment"> * 根据节点的编号删除节点的信息</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">delete</span><span class="params">(<span class="type">int</span> no)</span> &#123;</span><br><span class="line"> <span class="comment">//判断链表是否为空</span></span><br><span class="line"> <span class="keyword">if</span> (head.next == <span class="literal">null</span>) &#123;</span><br><span class="line"> System.out.println(<span class="string">&quot;链表为空,无法删除!&quot;</span>);</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="comment">//找到要删除的节点的信息</span></span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">temp</span> <span class="operator">=</span> head;</span><br><span class="line"> <span class="type">boolean</span> <span class="variable">isDelete</span> <span class="operator">=</span> <span class="literal">false</span>;<span class="comment">//是否删除</span></span><br><span class="line"> <span class="keyword">while</span> (<span class="literal">true</span>) &#123;</span><br><span class="line"> <span class="keyword">if</span> (temp.next == <span class="literal">null</span>) &#123;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="comment">//这里的temp指的是要删除节点的上一个节点 temp.next.next指的是要删除节点的下一个节点</span></span><br><span class="line"> <span class="keyword">if</span> (temp.next.no == no) &#123;</span><br><span class="line"> <span class="comment">//将要删除的节点的上一个节点指向要删除节点的下一个节点 实现删除的操作</span></span><br><span class="line"> <span class="comment">//这样要删除的节点没有引用指向,会被垃圾回收机制回收</span></span><br><span class="line"> temp.next = temp.next.next; </span><br><span class="line"> isDelete = <span class="literal">true</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> temp = temp.next;</span><br><span class="line"> &#125;</span>
<h4 id="4-2-4完整代码"><a href="#4-2-4完整代码" class="headerlink" title="4.2.4完整代码"></a>4.2.4完整代码</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line
<h4 id="4-2-5-单链表的面试题（新浪，百度，腾讯）"><a href="#4-2-5-单链表的面试题（新浪，百度，腾讯）" class="headerlink" title="4.2.5 单链表的面试题（新浪，百度，腾讯）"></a>4.2.5 单链表的面试题（新浪，百度，腾讯）</h4><h5 id="1-求单链表中有效节点的个数"><a href="#1-求单链表中有效节点的个数" class="headerlink" title="1.求单链表中有效节点的个数"></a>1.求单链表中有效节点的个数</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 获取有效节点的个数（如果是带头节点的链表，需求不统计头节点）</span></span><br><span class="line"><span class="comment"> * 注意:这里是有头节点的情况下统计节点的个数 （这里我们去除了头节点）</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> heroNode 头节点</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> 有效节点的个数</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">getLength</span><span class="params">(HeroNode heroNode)</span>&#123;</span><br><span class="line"> <span class="comment">//先判断节点是否为空</span></span><br><span class="line"> <span class="keyword">if</span>(heroNode.next == <span class="literal">null</span>)&#123;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="comment">//遍历节点进行统计</span></span><br><span class="line"> <span class="type">int</span> <span class="variable">length</span> <span class="operator">=</span> <span class="number">0</span>;<span class="comment">//有效节点的个数</span></span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">temp</span> <span class="operator">=</span> heroNode.next;<span class="comment">//这里没有统计头节点</span></span><br><span class="line"> <span class="keyword">while</span> (temp != <span class="literal">null</span>)&#123;<span class="comment">//遍历 统计个数</span></span><br><span class="line"> length++;</span><br><span class="line"> temp = temp.next;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="keyword">return</span> length;</span><br><span class="line"> &#125;</span><br></pre></td></tr></table></figure>
<h5 id="2-查找单链表中的倒数第K个节点-新浪面试题"><a href="#2-查找单链表中的倒数第K个节点-新浪面试题" class="headerlink" title="2.查找单链表中的倒数第K个节点(新浪面试题)"></a>2.查找单链表中的倒数第K个节点(新浪面试题)</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 查找单链表中的倒数第K个节点</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> index 倒数第几</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> heroNode 头节点</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> 倒数第K个节点的信息</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> HeroNode <span class="title function_">getHeroNodeByLastIndex</span><span class="params">(<span class="type">int</span> index, HeroNode heroNode)</span> &#123;</span><br><span class="line"> <span class="comment">//先判断节点是否为空</span></span><br><span class="line"> <span class="keyword">if</span> (heroNode.next == <span class="literal">null</span>) &#123;</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="comment">//首先获取有效节点的个数</span></span><br><span class="line"> <span class="type">int</span> <span class="variable">length</span> <span class="operator">=</span> <span class="built_in">this</span>.getLength(heroNode);<span class="comment">//使用求节点有效个数的方法</span></span><br><span class="line"> <span class="comment">//求倒数第k个节点就是在求正数第（length - index + 1）节点</span></span><br><span class="line"> index = length - index; <span class="comment">//求出正向的索引位置</span></span><br><span class="line"> <span class="keyword">if</span> (index &lt; <span class="number">0</span> || index &gt; length) &#123;</span><br><span class="line"> System.out.println(<span class="string">&quot;所求的在链表中不存在&quot;</span>);</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="type">int</span> <span class="variable">count</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">temp</span> <span class="operator">=</span> heroNode.next;</span><br><span class="line"> <span class="keyword">while</span> (<span class="literal">true</span>) &
<h5 id="3-单链表的反转-腾讯面试题"><a href="#3-单链表的反转-腾讯面试题" class="headerlink" title="3.单链表的反转(腾讯面试题)"></a>3.单链表的反转(腾讯面试题)</h5><p><img src="/pictures/image-20230506105453269.png" alt="image-20230506105453269"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 单链表的反转</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> heroNode 需要反转单链表的头节点</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">reverseHeroNode</span><span class="params">(HeroNode heroNode)</span> &#123;</span><br><span class="line"> <span class="comment">//先判断当前的链表是否为空 或者当前的链表只有一个节点</span></span><br><span class="line"> <span class="keyword">if</span>(head.next == <span class="literal">null</span> || head.next.next == <span class="literal">null</span>)&#123;</span><br><span class="line"> System.out.println(<span class="string">&quot;当前链表为空或者只有一个节点,无需反转&quot;</span>);</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="comment">//定义一个辅助的变量 帮助我们遍历原来的链表</span></span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">cur</span> <span class="operator">=</span> head.next;</span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">next</span> <span class="operator">=</span> <span class="literal">null</span>;<span class="comment">//指向当前节点的下一个节点 我们要在挪动当前节点之前帮当前指针 下移</span></span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">reverseHeroNode</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">HeroNode</span>(<span class="number">0</span>, <span class="string">&quot;&quot;</span>, <span class="string">&quot;&quot;</span>);<span class="comment">//新链表的头节点</span></span><br><span class="line"> <span class="comment">//遍历原先的列表 确定每一个链表的指向关系</span></span><br><span class="line"> <span class="keyword">while</span> (cur != <span class="literal">null</span>)&#123;</span><br><span class="line"> next = cur.next;<span class="comment">//保存当前节点的下一个节点</span></span><br><span class="line"> <span class="comment">//reverseHeroNode.next表示头节点的下一个节点 我们让cur的下一个节点（cur.next）指向头节点的下一个节点 //（reverseHeroNode.next） 就把当前的节点（cur）穿插进去了</span></span><br><span class="line"> <span class="comment">//下一句将头节点和当前节点建立关系reverseHeroNode.next = cur 整个节点就连接起来了</span></span><br><span class="line"> cur.next = reverseHeroNode.next;<span class="comment">//将cur的下一个节点指向新的链表的最前端 相当于在头节点和头节点的下一个节点 //之
<h5 id="4-从尾到头打印单链表（百度面试题）"><a href="#4-从尾到头打印单链表（百度面试题）" class="headerlink" title="4.从尾到头打印单链表（百度面试题）"></a>4.从尾到头打印单链表（百度面试题）</h5><p>不改变链表本身的结构(不是通过链表的反转之后再打印的)</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * （通过栈的方式实现单链表的逆序打印）</span></span><br><span class="line"><span class="comment"> * 栈的特点是先入后出 正好可以满足逆序打印</span></span><br><span class="line"><span class="comment"> * 单链表的逆序打印</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">reversePrint</span><span class="params">(HeroNode heroNode)</span> &#123;</span><br><span class="line"> <span class="comment">//先判断当前的链表是否为空 或者当前的链表只有一个节点</span></span><br><span class="line"> <span class="keyword">if</span> (head.next == <span class="literal">null</span>) &#123;</span><br><span class="line"> System.out.println(<span class="string">&quot;当前链表为空,无法逆序打印!&quot;</span>);</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="comment">//创建一个栈，将各个节点压入栈中</span></span><br><span class="line"> <span class="comment">//先创建一个栈</span></span><br><span class="line"> Stack&lt;HeroNode&gt; stack = <span class="keyword">new</span> <span class="title class_">Stack</span>&lt;&gt;();</span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">cur</span> <span class="operator">=</span> heroNode.next;</span><br><span class="line"> <span class="comment">//循环将每一个节点添加进栈中</span></span><br><span class="line"> <span class="keyword">while</span> (cur != <span class="literal">null</span>) &#123;</span><br><span class="line"> stack.push(cur);<span class="comment">//将节点压入栈中</span></span><br><span class="line"> cur = cur.next;<span class="comment">//cur后移 压入下一个节点</span></span><br><span class="line"> &#125;</span><br><span class="line"> <span class="comment">//将栈中节点打印</span></span><br><span class="line"> <span class="keyword">while</span> (stack.size() &gt; <span class="number">0</span>) &#123;</span><br><span class="line"> System.out.println(stack.pop());</span><br><span class="line"> &#125;</span><br><span class="line"> &#125;</span><br></pre></td></tr></table></figure>
<h5 id="5-合并两个有序的单链表，合并之后的链表依然有序"><a href="#5-合并两个有序的单链表，合并之后的链表依然有序" class="headerlink" title="5.合并两个有序的单链表，合并之后的链表依然有序"></a>5.合并两个有序的单链表，合并之后的链表依然有序</h5><p>以下代码有一些bug 后期修改</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 合并两个有序的单链表，合并之后的链表依然有序</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">mergeHeroNode</span><span class="params">(HeroNode oneHead, HeroNode twoHead ,HeroNode head)</span> &#123;</span><br><span class="line"> <span class="comment">//先判断两个链表是否为空</span></span><br><span class="line"> <span class="keyword">if</span> (oneHead.next == <span class="literal">null</span> || twoHead.next == <span class="literal">null</span>) &#123;</span><br><span class="line"> System.out.println(<span class="string">&quot;其中有一个（两个）链表为空,无法合并&quot;</span>);</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> <span class="comment">//合并</span></span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">oneCur</span> <span class="operator">=</span> oneHead.next;</span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">twoCur</span> <span class="operator">=</span> twoHead.next;</span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">oneNext</span> <span class="operator">=</span> <span class="literal">null</span>;</span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">twoNext</span> <span class="operator">=</span> <span class="literal">null</span>;</span><br><span class="line"> <span class="type">HeroNode</span> <span class="variable">finalHeroHead</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">HeroNode</span>(<span class="number">0</span>, <span class="string">&quot;&quot;</span>, <span class="string">&quot;&quot;</span>);</span><br><span class="line"> <span class="keyword">while</span> (oneCur != <span class="literal">null</span> &amp;&amp; twoCur != <span class="literal">null</span>) &#123;</span><br><span class="line"> oneNext = oneCur.next;</span><br><span class="line"> twoNext = twoCur.next;</span><br><span class="line"> <span class="keyword">if</span>(oneCur.no &lt;= twoCur.no) &#123;</span><br><span class="line"> oneCur.next = finalHeroHead.next;</span><br><span class="line"> finalHeroHead.next = oneCur;</span><br><span class="line"> oneCur = oneNext;</span><br><span class="line"> &#125;<span class="keyword">else</span> &#123;</span><br><span class="line"> twoCur.next = finalHeroHead.next;</span><br><span class="line"> finalHeroHead.next = twoCur;</span><br><span class="line">
<h5 id="全部代码"><a href="#全部代码" class="headerlink" title="全部代码"></a>全部代码</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><spa
<h3 id="4-3-双向链表"><a href="#4-3-双向链表" class="headerlink" title="4.3 双向链表"></a>4.3 双向链表</h3><p>双向的链表的CRUD操作于单向链表的CRUD操作类似</p>
<p><img src="/pictures/image-20230507100730848.png" alt="image-20230507100730848"></p>
<p>完整的增删改查代码</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class=
<h3 id="4-4-单向环形链表的应用场景-Josephu问题"><a href="#4-4-单向环形链表的应用场景-Josephu问题" class="headerlink" title="4.4 单向环形链表的应用场景(Josephu问题)"></a>4.4 单向环形链表的应用场景(Josephu问题)</h3><p>​ Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1&lt;&#x3D;k&lt;&#x3D;n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。</p>
<p>​ 解决的方案:用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。</p>
<p><img src="/pictures/image-20230508104207815.png" alt="image-20230508104207815"></p>
<p><img src="/pictures/image-20230508121934697.png" alt="image-20230508121934697"></p>
<p>完整的代码</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class=
<h2 id="五-栈"><a href="#五-栈" class="headerlink" title="五.栈"></a>五.栈</h2><h3 id="1-介绍"><a href="#1-介绍" class="headerlink" title="1.介绍"></a>1.介绍</h3><p>1)栈的英文为(stack)</p>
<p>2)栈是一个<strong>先入后出</strong>(FILO-First In Last Out)的有序列表。</p>
<p>3)栈(stack)是限制线性表中元素的插入和删除<strong>只能在线性表的同一端</strong>进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为<strong>栈顶</strong>(Top)，另一端为固定的一端，称为<strong>栈底</strong>(Bottom)。</p>
<p>4)根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除</p>
<h3 id="2-应用场景"><a href="#2-应用场景" class="headerlink" title="2.应用场景"></a>2.应用场景</h3><p>1)子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。 </p>
<p>2)处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。</p>
<p>3)表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。</p>
<p>4)二叉树的遍历。</p>
<p>5)图形的深度优先(depth一first)搜索法。</p>
<h3 id="3-图解"><a href="#3-图解" class="headerlink" title="3.图解"></a>3.图解</h3><p><img src="/pictures/image-20230510101713914.png" alt="image-20230510101713914"></p>
<p><img src="/pictures/image-20230510101722707.png" alt="image-20230510101722707"></p>
<h3 id="4-使用数组模拟栈"><a href="#4-使用数组模拟栈" class="headerlink" title="4.使用数组模拟栈"></a>4.使用数组模拟栈</h3><p><img src="/pictures/image-20230510101916230.png" alt="image-20230510101916230"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.stack;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/10</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 使用数组模拟栈</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">ArrayStackDemo</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">
<h3 id="5-栈实现综合计算器"><a href="#5-栈实现综合计算器" class="headerlink" title="5.栈实现综合计算器"></a>5.栈实现综合计算器</h3><p>中缀表达式</p>
<p><img src="/pictures/image-20230510105251076.png" alt="image-20230510105251076"></p>
<p><img src="/pictures/image-20230510110403055.png" alt="image-20230510110403055"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class=
<h3 id="6-逆波兰计算器的设计与实现"><a href="#6-逆波兰计算器的设计与实现" class="headerlink" title="6.逆波兰计算器的设计与实现"></a>6.逆波兰计算器的设计与实现</h3><p><strong>逆波兰表达式(后缀表达式)</strong></p>
<p>1)<strong>输入一个逆波兰表达式(后缀表达式)，使用栈(Stack),计算其结果</strong></p>
<p>2)<strong>支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.stack;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.ArrayList;</span><br><span class="line"><span class="keyword">import</span> java.util.List;</span><br><span class="line"><span class="keyword">import</span> java.util.Stack;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/11</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 逆波兰计算器的设计与实现</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">PolandNotation</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="comment">//先定义一个逆波兰表达式</span></span><br><span class=
<p><strong>将中缀表达式转化为后缀表达式（逆波兰表达式）</strong></p>
<p>解题的步骤:</p>
<p>1)初始化两个栈：运算符栈s1和储存中间结果的栈s2；</p>
<p>2)从左至右扫描中缀表达式；</p>
<p>3)遇到操作数时，将其压s2；</p>
<p>4)遇到运算符时，比较其与s1栈顶运算符的优先级：</p>
<p>​ (1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；</p>
<p>​ (2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；</p>
<p>​ (3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较</p>
<p>5)遇到括号时：<br> (1) 如果是左括号“(”，则直接压入s1<br> (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃</p>
<p>6)重复步骤2至5，直到表达式的最右边</p>
<p>7)将s1中剩余的运算符依次弹出并压入s2</p>
<p>8)依次弹出s2中的元素并输出，<strong>结果的逆序即为中缀表达式对应的后缀表达式</strong></p>
<p><img src="/pictures/image-20230511094011546.png" alt="image-20230511094011546"></p>
<p>先将中缀表达式转化成list集合</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 将中缀表达式转化成对应的list</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> expression 中缀表达式</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> 中缀表达式转化成的一个list集合</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> List&lt;String&gt; <span class="title function_">toInfixExpressionList</span><span class="params">(String expression)</span> &#123;</span><br><span class="line"> <span class="comment">//定义一个集合，存储中缀表达式对应的list集合</span></span><br><span class="line"> List&lt;String&gt; list = <span class="keyword">new</span> <span class="title class_">ArrayList</span>&lt;&gt;();</span><br><span class="line"> <span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>;<span class="comment">//这个是一个指针 用于遍历中缀表达式的字符串</span></span><br><span class="line"> String str;<span class="comment">//做多位数的拼接工作 ,因为我们要考虑多位数的情况</span></span><br><span class="line"> <span class="type">char</span> c;<span class="comment">//每遍历一个字符就放入到c中</span></span><br><span class="line"> <span class="keyword">do</span> &#123;</span><br><span class="line"> <span class="keyword">if</span> ((c = expression.charAt(i)) &lt; <span class="number">48</span> || (c = expression.charAt(i)) &gt; <span class="number">57</span>) &#123; <span class="comment">//如果c是一个非数字的字符需要加入到ls中</span></span><br><span class="line"> list.add(c + <span class="string">&quot;&quot;</span>); <span class="comment">//直接将这个字符添加到list集合中</span></span><br><span class="line"> i++;</span><br><span class="line"> &#125; <span class="keyword">else</span> &#123;<span class="comment">//如果是一个数 要考虑多位数的问题</span></span><br><span class="line"> str = <span class="string">&quot;&quot;</span>;<span class="comment">//先将str置空</span></span><br><span class="line"> <span class="keyword">while</span> (i &lt; expression.length() &amp;&amp; (c = expression.charAt(i)) &gt;= <span class="number">48</span> &amp;&amp; (c = expression.charAt(i)) &lt;= <span class="number">57</span>) &#123;</span><br><span class="line"> str += c;</span><br><span class="line"> i++;</span><br><span class="line"> &#125;</span><br><span class="line"> list.add(str);</span><br><span class="line"> &#125;</span><br><span class="line"> &#125; <span class="keyword">while</span> (i &lt; expression.length());</span><br><span class="line"> <span class="keyword">return</span> list;</span><br><
<p>将中缀表达式的集合转化成逆波兰表达式（后缀表达式）的集合</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 将中缀表达式对应的List转化成后缀表达式对应的list</span></span><br><span class="line"><span class="comment"> * tips:</span></span><br><span class="line"><span class="comment"> * 1)初始化两个栈：运算符栈s1和储存中间结果的栈s2；</span></span><br><span class="line"><span class="comment"> * 2)从左至右扫描中缀表达式；</span></span><br><span class="line"><span class="comment"> * 3)遇到操作数时，将其压s2；</span></span><br><span class="line"><span class="comment"> * 4)遇到运算符时，比较其与s1栈顶运算符的优先级：</span></span><br><span class="line"><span class="comment"> * (1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；</span></span><br><span class="line"><span class="comment"> * (2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；</span></span><br><span class="line"><span class="comment"> * (3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较</span></span><br><span class="line"><span class="comment"> * 5)遇到括号时：</span></span><br><span class="line"><span class="comment"> * (1) 如果是左括号“(”，则直接压入s1</span></span><br><span class="line"><span class="comment"> * (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃</span></span><br><span class="line"><span class="comment"> * 6)重复步骤2至5，直到表达式的最右边</span></span><br><span class="line"><span class="comment"> * 7)将s1中剩余的运算符依次弹出并压入s2</span></span><br><span class="line"><span class="comment"> * 8)依次弹出s2中的元素并输出，**结果的逆序即为中缀表达式对应的后缀表达式**</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> ls 中缀表达式对应的list</span></span><br><span class="line"><span class="comment"> * <span class
<p>通过逆波兰表达式（后缀表达式）的集合得到最终的计算结果</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 通过一个后缀表达式的list集合得到表达式最终的计算结果</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> list 后缀表达式的list集合</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> 根据后缀表达式的集合计算出的表达式的结果信息</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">calculate</span><span class="params">(List&lt;String&gt; list)</span> &#123;</span><br><span class="line"> <span class="comment">//创建一个栈</span></span><br><span class="line"> Stack&lt;String&gt; stack = <span class="keyword">new</span> <span class="title class_">Stack</span>&lt;&gt;();</span><br><span class="line"> <span class="comment">//遍历list</span></span><br><span class="line"> <span class="keyword">for</span> (String item : list) &#123;</span><br><span class="line"> <span class="comment">//使用正则表达式取出数字</span></span><br><span class="line"> <span class="keyword">if</span> (item.matches(<span class="string">&quot;\\d+&quot;</span>)) &#123; <span class="comment">//匹配的是多位数</span></span><br><span class="line"> <span class="comment">//入栈</span></span><br><span class="line"> stack.push(item);</span><br><span class="line"> &#125; <span class="keyword">else</span> &#123;</span><br><span class="line"> <span class="comment">//弹出两个数 并运算 再入栈</span></span><br><span class="line"> <span class="type">int</span> <span class="variable">num2</span> <span class="operator">=</span> Integer.parseInt(stack.pop());</span><br><span class="line"> <span class="type">int</span> <span class="variable">num1</span> <span class="operator">=</span> Integer.parseInt(stack.pop());</span><br><span class="line"> <span class="comment">//运算</span></span><br><span class="line"> <span class="type">int</span> <span class="variable">res</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">if</span> (item.equals(<span class="string">&quot;+&quot;</span>)) &#123;</span><br><span class="line"> res = num1 + num2;</span><br><span class="line"> &#125; <span class="keyword">else</span> <span class="keyword">if</span>
<p><strong>完整的代码</strong></p>
<p>(不支持小数)</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class=
<p><strong>完整的逆波兰计算器，含小数点的计算</strong></p>
<p>(老师的代码)</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class=
<h2 id="六-递归"><a href="#六-递归" class="headerlink" title="六.递归"></a>六.递归</h2><h3 id="1-简单介绍"><a href="#1-简单介绍" class="headerlink" title="1.简单介绍"></a>1.简单介绍</h3><p>递归就是方法自己调用自己,每次调用时传入不同的变量，<strong>递归有助于编程者解决复杂的问题</strong>,同时可以让代码变得简洁</p>
<p><img src="/pictures/image-20230511123527496.png" alt="image-20230511123527496"></p>
<h3 id="2-入门案例"><a href="#2-入门案例" class="headerlink" title="2.入门案例"></a>2.入门案例</h3><p><img src="/pictures/image-20230511123245408.png" alt="image-20230511123245408"></p>
<h3 id="3-递归解决的问题"><a href="#3-递归解决的问题" class="headerlink" title="3.递归解决的问题"></a>3.递归解决的问题</h3><p>1)各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)</p>
<p>2)各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.</p>
<p>3)将用栈解决的问题–&gt;第归代码比较简洁</p>
<h3 id="4-递归遵循的规则"><a href="#4-递归遵循的规则" class="headerlink" title="4.递归遵循的规则"></a>4.递归遵循的规则</h3><p>1)执行一个方法时，就创建一个新的受保护的独立空间(栈空间)</p>
<p>2)方法的局部变量是独立的，不会相互影响, 比如n变量</p>
<p>3)如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.</p>
<p>4)递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了:)</p>
<p>5)当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。</p>
<h3 id="5-递归的实际应用"><a href="#5-递归的实际应用" class="headerlink" title="5.递归的实际应用"></a>5.递归的实际应用</h3><h4 id="5-1递归解决迷宫问题"><a href="#5-1递归解决迷宫问题" class="headerlink" title="5.1递归解决迷宫问题"></a>5.1递归解决迷宫问题</h4><p><img src="/pictures/image-20230512092144712.png" alt="image-20230512092144712"></p>
<p><strong>代码实现</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.recursion;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/12</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 递归解决迷宫问题</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">MiGong</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(
<h4 id="5-2-递归解决八皇后问题"><a href="#5-2-递归解决八皇后问题" class="headerlink" title="5.2 递归解决八皇后问题"></a>5.2 递归解决八皇后问题</h4><p>使用回溯算法解决 类似于穷举法 后期使用别的算法优化</p>
<p><strong>问题介绍</strong></p>
<p><img src="/pictures/image-20230512112050729.png" alt="image-20230512112050729"></p>
<p><strong>思路分析</strong></p>
<p><img src="/pictures/image-20230512112456731.png" alt="image-20230512112456731"></p>
<p><strong>代码实现</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.recursion;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/13</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 八皇后问题的解题思路及代码实现</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Queue8</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="type">Queue8</span> <span class="variable">queue8</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Queue8</span>();</span><br><span class="line"> queue8.check(<span class="number">0</span>);</span><br><span class="line"> &#125;</span><br><span class="line"
<h2 id="七-排序算法"><a href="#七-排序算法" class="headerlink" title="七.排序算法"></a>七.排序算法</h2><p><strong>十大经典的排序算法：</strong><a target="_blank" rel="noopener" href="https://www.runoob.com/w3cnote/ten-sorting-algorithm.html">菜鸟教程排序算法</a></p>
<h3 id="1-介绍-1"><a href="#1-介绍-1" class="headerlink" title="1.介绍"></a>1.介绍</h3><p><img src="/pictures/image-20230513115319799.png" alt="image-20230513115319799"></p>
<h3 id="2-时间复杂度"><a href="#2-时间复杂度" class="headerlink" title="2.时间复杂度"></a>2.时间复杂度</h3><p><strong>度量时间复杂度的两种方法</strong></p>
<p>事后统计法的不足：</p>
<ul>
<li>需要实际的运行程序 比较耗时</li>
<li>受计算机硬件和软件的影响</li>
</ul>
<p><img src="/pictures/image-20230513115606521.png" alt="image-20230513115606521"></p>
<p><strong>时间频度</strong></p>
<p>​ 基本的介绍:一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。<strong>一个算法中的语句执行次数称为语句频度或时间频度</strong>。记为T(n)</p>
<p><strong>时间复杂度介绍</strong></p>
<p><img src="/pictures/image-20230515093520587.png" alt="image-20230515093520587"></p>
<p><strong>常见的时间复杂度</strong></p>
<p><img src="/pictures/image-20230515093753893.png" alt="image-20230515093753893"></p>
<h3 id="3-空间复杂度"><a href="#3-空间复杂度" class="headerlink" title="3.空间复杂度"></a>3.空间复杂度</h3><p><img src="/pictures/image-20230515095247319.png" alt="image-20230515095247319"></p>
<p><strong>排序算法的时间和空间复杂度</strong></p>
<p><img src="/pictures/image-20230516083738747.png" alt="image-20230516083738747"></p>
<h3 id="4-冒泡排序"><a href="#4-冒泡排序" class="headerlink" title="4.冒泡排序"></a>4.冒泡排序</h3><p>冒泡排序的时间复杂度:o(n^2)</p>
<p>同一台电脑 8万个数据 十几秒左右</p>
<h4 id="4-1-基本介绍"><a href="#4-1-基本介绍" class="headerlink" title="4.1 基本介绍"></a>4.1 基本介绍</h4><p><img src="/pictures/image-20230515100345339.png" alt="image-20230515100345339"></p>
<h4 id="4-2-图解"><a href="#4-2-图解" class="headerlink" title="4.2 图解"></a>4.2 图解</h4><p><img src="/pictures/image-20230515100754827.png" alt="image-20230515100754827"></p>
<h4 id="4-3-代码实现"><a href="#4-3-代码实现" class="headerlink" title="4.3 代码实现"></a>4.3 代码实现</h4><p>优化之前的代码 </p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.sort;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/15</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 冒泡排序</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">BubbleSort</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="type">int</span> arr[] = &#123;<span class="number">3</span>, <span class="number">9</span>, -<span class="number">1</span>, <span class="number">10</span>, -<span class="number">2</span>&#125;;</span><br><span class="line"> BubbleSort.sort(arr);</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">sort</span><span class="params">(<span class="type">int</span>[] arr)</span> &#123;</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length - <span class="number">1</span>; i++) &#123;</span><br><span class="line"> <span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span> <span class="number">0</span>; <span class="comment">//临时变量</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; arr.length - <span class="number">1</span> - i; j++) &#123;</span><br><span class="line"> <span class="comment">//如果前面的数字大于后面的数字就交换</span></span><br><span class="line"> <span class="keyword">if</span> (arr[j] &gt; arr[j + <span class="number">1</span>]) &#123;</span><br><span class="line"> temp = arr[j];</span><br><span class="line"> arr[j] = arr[j + <span class="number">1</span>];</span><br><span class="line">
<p>优化之后的代码（如果排序的过程中代码有序就不在排序）</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.sort;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/15</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 冒泡排序</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">BubbleSort</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="type">int</span> arr[] = &#123;<span class="number">3</span>, <span class="number">9</span>, -<span class="number">1</span>, <span class="number">10</span>, -<span class="number">2</span>&#125;;</span><br><span class="line"> BubbleSort.sort(arr);</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line"> <span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 冒泡排序</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> arr 需要排序的数组</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">sort</span><span class="params">(<span class="type">int</span>[] arr)</span> &#123;</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length - <span class="number">1</span>; i++) &#123;</span><br><span class="line"> <span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span> <span class="number">0</span>; <span class="comment">//临时变量</span></span><br><span class="line"> <span class="type">boolean
<p><img src="/pictures/image-20230516091218716.png" alt="image-20230516091218716"></p>
<h3 id="5-选择排序"><a href="#5-选择排序" class="headerlink" title="5.选择排序"></a>5.选择排序</h3><h4 id="5-1-基本介绍"><a href="#5-1-基本介绍" class="headerlink" title="5.1 基本介绍"></a>5.1 基本介绍</h4><p>同一台电脑 8万个数据 两秒左右</p>
<p>选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的</p>
<p><img src="/pictures/image-20230515105359552.png" alt="image-20230515105359552"></p>
<h4 id="5-2图解"><a href="#5-2图解" class="headerlink" title="5.2图解"></a>5.2图解</h4><p><img src="/pictures/selectionSort.gif" alt="img"></p>
<p><img src="/pictures/image-20230516083148055.png" alt="image-20230516083148055"></p>
<h4 id="5-3代码实现"><a href="#5-3代码实现" class="headerlink" title="5.3代码实现"></a>5.3代码实现</h4><p>两种方法 一个是自己的 一个是老师的</p>
<p>使用老师的代码 老师的代码验证过</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.sort;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/16</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 选择排序</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">SelectSort</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="type">int</span>[] arr = &#123;<span class="number">101</span>,<span class="number">34</span>,<span class="number">119</span>,<span class="number">1</span>&#125;;</span><br><span class="line"> <span class="type">int</span>[] arr1 = &#123;<span class="number">3</span>, <span class="number">9</span>, -<span class="number">1</span>, <span class="number">10</span>, -<span class="number">2</span>&#125;;</span><br><span class="line"> <span class="type">int</span>[] arr2 = &#123;<span class="number">3</span>, <span class="number">9</span>, -<span class="number">1</span>, <span class="number">10</span>, -<span class="number">2</span>&#125;;</span><br><span class="line"> System.out.println(<span class="string">&quot;自己的代码&quot;</span>);</span><br><span class="line"> SelectS
<p><img src="/pictures/image-20230516093143656.png" alt="image-20230516093143656"></p>
<h3 id="6-插入排序"><a href="#6-插入排序" class="headerlink" title="6.插入排序"></a>6.插入排序</h3><h4 id="6-1-基本介绍"><a href="#6-1-基本介绍" class="headerlink" title="6.1 基本介绍"></a>6.1 基本介绍</h4><p>同一台电脑 8万个数据 五秒左右</p>
<p>插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。</p>
<p><img src="/pictures/image-20230516100256880.png" alt="image-20230516100256880"></p>
<h4 id="6-2-图解"><a href="#6-2-图解" class="headerlink" title="6.2 图解"></a>6.2 图解</h4><img src="/pictures/insertionSort.gif" alt="img" style="zoom:150%;" />
<h4 id="6-3-代码实现"><a href="#6-3-代码实现" class="headerlink" title="6.3 代码实现"></a>6.3 代码实现</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.sort;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/16</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 插入排序</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">InsertSort</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="type">int</span>[] arr = &#123;<span class="number">101</span>, <span class="number">34</span>, <span class="number">119</span>, <span class="number">1</span>,-<span class="number">1</span>,<span class="number">89</span>&#125;;</span><br><span class="line"> System.out.println(<span class="string">&quot;插入前的数组:&quot;</span>+Arrays.toString(arr));</span><br><span class="line"> InsertSort.insertSort(arr);</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line"> <span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 插入排序</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">insertSort</span><span class="params">(<span class="type">int</span>[] arr)</span> &#123;</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">1</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line"> <span class="comment">//定义待插入的数</span></span><br><span class="line"> <span class="type">int</span> <span class="variable">insertVal</span> <span class="operator">=</span> arr[i];</span><br><span
<p><img src="/pictures/image-20230516105517026.png" alt="image-20230516105517026"></p>
<h3 id="7-希尔排序"><a href="#7-希尔排序" class="headerlink" title="7.希尔排序"></a>7.希尔排序</h3><h4 id="7-1基本介绍"><a href="#7-1基本介绍" class="headerlink" title="7.1基本介绍"></a>7.1基本介绍</h4><p>同一台电脑 8万个数据 十七秒左右（交换法）</p>
<p>同一台电脑 8万个数据 一秒左右(移动法)</p>
<p><img src="/pictures/image-20230517091741355.png" alt="image-20230517091741355"></p>
<p><img src="/pictures/image-20230517091841366.png" alt="image-20230517091841366"></p>
<h4 id="7-2-图解"><a href="#7-2-图解" class="headerlink" title="7.2.图解"></a>7.2.图解</h4><p><img src="/pictures/Sorting_shellsort_anim.gif" alt="img"></p>
<img src="/pictures/image-20230517102649272.png" alt="image-20230517102649272" style="zoom:150%;" />
<h4 id="7-3-代码实现"><a href="#7-3-代码实现" class="headerlink" title="7.3 代码实现"></a>7.3 代码实现</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.sort;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/17</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 希尔排序</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">ShellSort</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="type">int</span>[] arr = &#123;<span class="number">8</span>, <span class="number">9</span>, <span class="number">1</span>, <span class="number">7</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">5</span>, <span class="number">4</span>, <span class="number">6</span>, <span class="number">0</span>&#125;;</span><br><span class="line"> <span class="comment">//shellSort(arr);</span></span><br><span class="line"> shellSort2(arr);</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line"> <span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 希尔排序
<h3 id="8-快速排序"><a href="#8-快速排序" class="headerlink" title="8.快速排序"></a>8.快速排序</h3><h4 id="8-1-基本介绍"><a href="#8-1-基本介绍" class="headerlink" title="8.1 基本介绍"></a>8.1 基本介绍</h4><p>同一台电脑 8万个数据 不到一秒 800万个数据两秒钟</p>
<p>​ <strong>快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列</strong></p>
<h4 id="8-2-图解"><a href="#8-2-图解" class="headerlink" title="8.2 图解"></a>8.2 图解</h4><img src="/pictures/quickSort.gif" alt="img" style="zoom:150%;" />
<img src="/pictures/image-20230517103139900.png" alt="image-20230517103139900" style="zoom:150%;" />
<h4 id="8-3-代码实现"><a href="#8-3-代码实现" class="headerlink" title="8.3 代码实现"></a>8.3 代码实现</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.sort;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/17</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 快速排序</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">QuickSort</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="type">int</span>[] arr = &#123;-<span class="number">9</span>, <span class="number">78</span>, <span class="number">0</span>, <span class="number">23</span>, -<span class="number">567</span>, <span class="number">70</span>&#125;;</span><br><span class="line"> quickSort(arr, <span class="number">0</span>, arr.length - <span class="number">1</span>);</span><br><sp
<h3 id="9-归并排序"><a href="#9-归并排序" class="headerlink" title="9. 归并排序"></a>9. 归并排序</h3><h4 id="9-1基本介绍"><a href="#9-1基本介绍" class="headerlink" title="9.1基本介绍"></a>9.1基本介绍</h4><p>同一台电脑 8万个数据 大约一秒钟 800万个数据三秒</p>
<p><img src="/pictures/image-20230518111233009.png" alt="image-20230518111233009"></p>
<h4 id="9-2-图解"><a href="#9-2-图解" class="headerlink" title="9.2 图解"></a>9.2 图解</h4><img src="/pictures/mergeSort.gif" alt="img" style="zoom:150%;" />
<p><img src="/pictures/image-20230518111454775.png" alt="image-20230518111454775"></p>
<p><img src="/pictures/image-20230518111536026.png" alt="image-20230518111536026"></p>
<h4 id="9-3代码实现"><a href="#9-3代码实现" class="headerlink" title="9.3代码实现"></a>9.3代码实现</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.sort;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/18</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 归并排序</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">MergeSort</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String
<h3 id="10-基数排序"><a href="#10-基数排序" class="headerlink" title="10.基数排序"></a>10.基数排序</h3><p>同一台电脑8万个数据 一秒左右 8千万个数据会报内存不足</p>
<h4 id="10-1-基本介绍"><a href="#10-1-基本介绍" class="headerlink" title="10.1 基本介绍"></a>10.1 基本介绍</h4><p><img src="/pictures/image-20230525195008102.png" alt="image-20230525195008102"></p>
<p><img src="/pictures/image-20230526094945578.png" alt="image-20230526094945578"></p>
<p><img src="/pictures/image-20230526113739081.png" alt="image-20230526113739081"></p>
<h4 id="10-2-图解"><a href="#10-2-图解" class="headerlink" title="10.2 图解"></a>10.2 图解</h4><p><img src="/pictures/radixSort.gif" alt="img"></p>
<h4 id="10-3-代码实现"><a href="#10-3-代码实现" class="headerlink" title="10.3 代码实现"></a>10.3 代码实现</h4><p><strong>推导代码</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.sort;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/26</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 基数排序</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">RadixSort</span> &#123;</span><br><span class="line"> <span
<p><strong>最终代码</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.sort;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/26</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 基数排序</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">RadixSort</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="comment">//定义一个待排序的数组</span></span><br><span class="line"> <span class="type">int</span> arr[] = &#123;<span class="number">53</span>, <span class="number">3</span>, <span class="number">542</span>, <span class="number">748</span>, <span class="number">14</span>, <span class="number">214</span>&#125;;</span><br><span class="line"> RadixSort.radixSort(arr);</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line"> <span class="comment">//基数排序</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">radixSort</span><span class="params">(<span class="type">int</span>[] arr)</span> &#123;</span><br><span class="line"> <span class="comment">//得到数组中最大数的位数</span></span><br><span class="line"> <span class="type">int</span> <span c
<h3 id="11-常用排序算法总结和对比"><a href="#11-常用排序算法总结和对比" class="headerlink" title="11.常用排序算法总结和对比"></a>11.常用排序算法总结和对比</h3><p><img src="/pictures/image-20230526114127402.png" alt="image-20230526114127402"></p>
<h2 id="八-查找算法"><a href="#八-查找算法" class="headerlink" title="八.查找算法"></a>八.查找算法</h2><h3 id="1-简单介绍-1"><a href="#1-简单介绍-1" class="headerlink" title="1.简单介绍"></a>1.简单介绍</h3><img src="/pictures/image-20230526115027518.png" alt="image-20230526115027518" style="zoom:200%;" />
<h3 id="2-线性查找算法"><a href="#2-线性查找算法" class="headerlink" title="2.线性查找算法"></a>2.线性查找算法</h3><h4 id="2-1代码实现"><a href="#2-1代码实现" class="headerlink" title="2.1代码实现"></a>2.1代码实现</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.search;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/29</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 线性查找</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">SeqSearch</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="type">int</span>[] arr = &#123;<span class="number">1</span>,<span class="number">9</span>,<span class="number">11</span>,-<span class="number">1</span>,<span class="number">34</span>,<span class="number">89</span>&#125;;<span class="comment">//没有顺序的数组</span></span><br><span class="line"> System.out.println(<span class="string">&quot;目标值的下标:&quot;</span>+seqSearch(arr, <span class="number">11</span>));</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line"> <span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 找到一个满足条件的值就返回</span></span><br><span class="line"><span class="comment"> * 线性查找是逐一比对，发现有相同的值时就返回这个值的下标</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> arr 需要在这里面找目标值的数组</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> value 目标值</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> 目标值的下标</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">seqSearch</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> value)</span>&#123;</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</sp
<h3 id="3-二分查找算法"><a href="#3-二分查找算法" class="headerlink" title="3.二分查找算法"></a>3.二分查找算法</h3><h4 id="3-1-图解"><a href="#3-1-图解" class="headerlink" title="3.1 图解"></a>3.1 图解</h4><img src="/pictures/image-20230529104112317.png" alt="image-20230529104112317" style="zoom:150%;" />
<h4 id="3-2-代码实现"><a href="#3-2-代码实现" class="headerlink" title="3.2 代码实现"></a>3.2 代码实现</h4><p><em><strong>递归的方式解决</strong></em></p>
<p><strong>基本的写法</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.search;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/29</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 二分查找</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">BinarySearch</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="type">int</span>[] arr = &#123;<span class="number">1</span>, <span class="number">8</span>, <span class="number">10</span>, <span class="number">89</span>, <span class="number">1000</span>, <span class="number">1234</span>&#125;;</span><br><span class="line"> System.out.println(<span class="string">&quot;目标值的下标:&quot;</span> + binarySearch(arr, <span class="number">0</span>, arr.length - <span class="number">1</span>, <span class="number">3</span>));</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line"> <span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 二分查找</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> arr 需要在这里面查找目标值的数组</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> left 左边的索引</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> right 右边的索引</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> findVal 要查找的值</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> 目标值在数组中的下标，找到就返回下标，没有就返回-1</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <s
<p><strong>完整的代码</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.search;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.ArrayList;</span><br><span class="line"><span class="keyword">import</span> java.util.List;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/29</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 二分查找</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">BinarySearch</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span cla
<h3 id="4-插值查找算法"><a href="#4-插值查找算法" class="headerlink" title="4.插值查找算法"></a>4.插值查找算法</h3><h4 id="4-1-图解"><a href="#4-1-图解" class="headerlink" title="4.1 图解"></a>4.1 图解</h4><p><img src="/pictures/image-20230530101020552.png"></p>
<img src="/pictures/image-20230530101803392.png" alt="image-20230530101803392" style="zoom:200%;" />
<h4 id="4-2-代码实现"><a href="#4-2-代码实现" class="headerlink" title="4.2 代码实现"></a>4.2 代码实现</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.atguigu.search;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> GongChangjiang</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@version</span> 1.0</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Date</span> 2023/5/30</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 插值查找算法</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">InsertValueSearch</span> &#123;</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"> <span class="comment">//创建一个数组 用于模拟需要查找数据的数组</span></span><br><span class="line"> <span class="type">int</span>[] arr = <span class="keyword">new</span> <span class="title class_">int</span>[<span class="number">100</span>];</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; <span class="number">100</span>; i++) &#123;</span><br><span class="line"> arr[i] = i + <span class="number">1</span>;</span><br><span class="line"> &#125;</span><br><span class="line"> System.out.println(Arrays.toString(arr));</span><br><span class="line"> System.out.println(<span class="string">&quot;查找的数的下标为:&quot;</span> + insertValueSearch(arr, <span class="number">0</span>, arr.length - <span class="number">1</span>, <span class="number">30</span>));</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line"> <span class="comment">/**</span></span><br><span cl
<h4 id="4-3-注意事项"><a href="#4-3-注意事项" class="headerlink" title="4.3 注意事项"></a>4.3 注意事项</h4><p><img src="/pictures/image-20230530105652529.png" alt="image-20230530105652529"></p>
<h3 id="5-斐波那契（黄金分割法）查找算法"><a href="#5-斐波那契（黄金分割法）查找算法" class="headerlink" title="5.斐波那契（黄金分割法）查找算法"></a>5.斐波那契（黄金分割法）查找算法</h3><h4 id="5-1-基本介绍-1"><a href="#5-1-基本介绍-1" class="headerlink" title="5.1 基本介绍"></a>5.1 基本介绍</h4><img src="/pictures/image-20230530110145048.png" alt="image-20230530110145048" style="zoom:150%;" />
<h4 id="5-2-原理介绍"><a href="#5-2-原理介绍" class="headerlink" title="5.2 原理介绍"></a>5.2 原理介绍</h4><p><img src="/pictures/image-20230530110511769.png" alt="image-20230530110511769"></p>
<hr>
<h2 id="PDF笔记"><a href="#PDF笔记" class="headerlink" title="PDF笔记"></a>PDF笔记</h2>
<div class="row">
<embed src="/pdf/尚硅谷图解Java数据结构和算法.pdf" width="100%" height="550" type="application/pdf">
</div>
Site updated: 2024-06-14 22:00:18
2024-06-14 22:00:25 +08:00
</article><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/">数据结构与算法</a></div><div class="post_share"><div class="social-share" data-image="/img/4.png" data-sites="wechat,weibo,qq"></div><link rel="stylesheet" href="/cdn/css/share.min.css" media="print" onload="this.media='all'"><script src="/cdn/js/social-share.min.js" defer></script></div></div><div class="post-reward"><div class="reward-button"><i class="fas fa-qrcode"></i> 打赏</div><div class="reward-main"><ul class="reward-all"><li class="reward-item"><a href="/img/wechat.jpg" target="_blank"><img class="post-qr-code-img" src="/img/wechat.jpg" alt="微信"/></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="/img/alipay.jpg" target="_blank"><img class="post-qr-code-img" src="/img/alipay.jpg" alt="支付宝"/></a><div class="post-qr-code-desc">支付宝</div></li></ul></div></div><br/><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="far fa-comment-alt fa-fw"></i><span> 评论</span></div></div><div class="comment-wrap"><div><div id="gitalk-container"></div></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="/img/avatar.jpg" onerror="this.onerror=null;this.src='/img/loading.gif'" alt="avatar"/></div><div class="author-info__name">Jason</div><div class="author-info__description">Debug the World！</div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">60</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">39</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">10</div></a></div><a id="card-info-btn"><i class="fab fa-microsoft"></i><span>Ctrl + D 收藏</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/JasonsGong" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="tencent://AddContact/?fromId=45&amp;fromSubId=1&amp;subcmd=all&amp;uin=2602183349&amp;website=www.oicqzone.com" target="_blank" title="QQ"><i class="fab fa-qq"></i></a><a class="social-icon" href="mailto:2602183349@qq.com" target="_blank" title="Email"><i class="fas fa-envelope-open-text"></i></a><a class="social-icon" href="https://github.com/JasonsGong?tab=repositories" target="_blank" title="代码仓库"><i class="fas fa-database"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">本网站是静态网站,更新页面资源请使用Ctrl+F5;若网站内文章对你有帮助,请使用Ctrl+D收藏该网站！</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content is-expand"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%80-%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95%E9%97%AE%E9%A2%98"><span class="toc-text">一.经典算法问题</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E7%9A%84%E6%A6%82%E8%BF%B0"><span class="toc-text">二.数据结构与算法的概述</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-1-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E7%9A%84%E5%85%B3%E7%B3%BB"><span class="toc-text">2.1 数据结构与算法的关系</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-2%E8%A7%A3%E5%86%B3%E5%AE%9E%E9%99%85%E7%9A%84%E9%97%AE%E9%A2%98"><span class="toc-text">2.2解决实际的问题</span></a></li><li class="toc-item toc-level-3"><
Site updated: 2024-01-13 16:32:42
2024-01-13 16:32:52 +08:00
function initGitalk () {
var gitalk = new Gitalk(Object.assign({
clientID: '00fb27b1e484536359c2',
clientSecret: 'be41a12281c68b6e228d1a27e8d08aeb91541145',
repo: 'BlogComment',
owner: 'JasonsGong',
admin: ['JasonsGong'],
id: '6ebda012d4e8be7e5b2b8b4687b857f7',
updateCountCallback: commentCount
},null))
gitalk.render('gitalk-container')
}
if (typeof Gitalk === 'function') initGitalk()
else {
Site updated: 2024-01-13 17:50:05
2024-01-13 17:50:17 +08:00
getCSS('/cdn/css/gitalk.min.css')
getScript('/cdn/js/gitalk.min.js').then(initGitalk)
Site updated: 2024-01-13 16:32:42
2024-01-13 16:32:52 +08:00
}
}
function commentCount(n){
let isCommentCount = document.querySelector('#post-meta .gitalk-comment-count')
if (isCommentCount) {
isCommentCount.textContent= n
}
}
if ('Gitalk' === 'Gitalk' || !true) {
if (true) btf.loadComment(document.getElementById('gitalk-container'), loadGitalk)
else loadGitalk()
} else {
function loadOtherComment () {
loadGitalk()
}
}</script></div><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span> 数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div><br/><div class="no-result" id="local-search-results"></div><div id="local-search-stats-wrap"></div></div></div><div id="search-mask"></div><script src="/js/search/local-search.js"></script></div></div><!-- hexo injector body_end start --><script data-pjax>
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
function butterfly_swiper_injector_config(){
Site updated: 2024-01-13 22:42:16
2024-01-13 22:42:28 +08:00
var parent_div_git = document.getElementById('recent-posts');
Site updated: 2024-06-14 22:00:18
2024-06-14 22:00:25 +08:00
var item_html = '<div class="recent-post-item" style="height: auto;width: 100%"><div class="blog-slider swiper-container-fade swiper-container-horizontal" id="swiper_container"><div class="blog-slider__wrp swiper-wrapper" style="transition-duration: 0ms;"><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="posts/19306.html" alt=""><img width="48" height="48" src="/img/1.png" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-04-21</span><a class="blog-slider__title" href="posts/19306.html" alt="">Docker容器化技术</a><div class="blog-slider__text">Docker</div><a class="blog-slider__button" href="posts/19306.html" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="posts/47003.html" alt=""><img width="48" height="48" src="/img/5.png" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-03-10</span><a class="blog-slider__title" href="posts/47003.html" alt="">常用正则表达式大全</a><div class="blog-slider__text">正则表达式</div><a class="blog-slider__button" href="posts/47003.html" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="posts/20683.html" alt=""><img width="48" height="48" src="/img/8.png" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-06-05</span><a class="blog-slider__title" href="posts/20683.html" alt="">Linux中开发环境的搭建</a><div class="blog-slider__text">环境搭建</div><a class="blog-slider__button" href="posts/20683.html" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="posts/63333.html" alt=""><img width="48" height="48" src="/img/10.png" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-06-03</span><a class="blog-slider__title" href="posts/63333.html" alt="">开发环境的搭建</a><div class="blog-slider__text">环境搭建</div><a class="blog-slider__button" href="posts/63333.html" alt="">详情 </a></div></div></div><div class="blog-slider__pagination swiper-pagination-clickable swiper-pagination-bullets"></div></div></div>';
Site updated: 2024-01-13 22:42:16
2024-01-13 22:42:28 +08:00
if (parent_div_git !== null && typeof parent_div_git !== 'undefined') {
parent_div_git.insertAdjacentHTML("afterbegin",item_html)
}
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
}
var elist = 'undefined'.split(',');
var cpage = location.pathname;
Site updated: 2023-10-28 10:47:13
2023-10-28 10:47:20 +08:00
var epage = 'all';
Site updated: 2023-09-22 21:57:09
2023-09-22 21:57:28 +08:00
var flag = 0;
for (var i=0;i<elist.length;i++){
if (cpage.includes(elist[i])){
flag++;
}
}
if ((epage ==='all')&&(flag == 0)){
butterfly_swiper_injector_config();
}
else if (epage === cpage){
butterfly_swiper_injector_config();
}
Site updated: 2024-01-13 22:10:46
2024-01-13 22:10:58 +08:00
</script><script defer src="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper.min.js"></script><script defer data-pjax src="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper_init.js"></script><!-- hexo injector body_end end --></body></html>
Reference in New Issue Copy Permalink