JavaScript冒泡排序+Vue可视化冒泡动画
<p><img src="https://img2023.cnblogs.com/blog/151257/202212/151257-20221217212826600-1640242755.gif" alt="1.gif" loading="lazy"></p><p>冒泡排序（Bubble Sort）算是前端最简单的算法，也是最经典的排序算法了。网上JavaScript版本的冒泡排序很多，今天用Vue实现一个动态的可视化冒泡排序。</p>
<h1 id="01javascript冒泡排序">01、JavaScript冒泡排序</h1>
<p>冒泡排序原理也比较简单，就是相邻元素两两比较排序，把大的元素冒泡排序到后面，递归所有相邻元素组合完成排序。</p>
<h2 id="11原理">1.1、原理</h2>
<p>有一个无序数组：<code>let arr = </code>，长度为<code>len=6</code>。</p>
<ul>
<li><strong>①</strong>、从第一位元素100（0索引）开始，比较相邻<code>arr、arr</code>元素的大小，大的排后面，如果<code>arr>arr</code>则交换值位置。</li>
<li><strong>②</strong>、如下图，依次相邻元素比较、交换，一轮完成后，最大元素就到了最右边了。这个过程中，最大的元素（最大的泡泡）就像冒泡一样到了末尾。</li>
</ul>
<p><img src="https://img2023.cnblogs.com/blog/151257/202212/151257-20221217213018563-569286759.png" alt="image" loading="lazy"></p>
<ul>
<li>③、然后继续对剩下的前面<code>len-1=5</code>个元素重复上述步骤，直到只剩下一个元素。这是一个递归的过程，递归到第一个元素，就完成了冒泡排序。</li>
</ul>
<p><img src="https://img2023.cnblogs.com/blog/151257/202212/151257-20221217213051175-2071847947.png" alt="image" loading="lazy"></p>
<p>冒泡排序的动画过程如下图，排序过程很直观，一目了然，下一章节也实现一个跟好的。</p>
<p><img src="https://img2023.cnblogs.com/blog/151257/202212/151257-20221217212826597-555262192.gif" alt="" loading="lazy"></p>
<h2 id="12javascript实现">1.2、JavaScript实现</h2>
<p>经典冒泡排序算法，用两个<code>for</code>循环来实现所有元素的两两对比排序。统计了一下排序次数，一共比较了15次。冒泡排序的时间复杂度是O(n^2)，这是最大值，最小为O(n)。</p>
<pre><code class="language-javascript">//经典冒泡排序算法
//从小到大冒泡排序
let arr = ;
let count=0; //计数器
function bubbleSort(arr) {
const len = arr.length;
let t;count=0;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - i - 1; j++) {
count++;
//比较相邻两个元素
if (arr > arr) {
//交换两个元素，大的往后排列
t = arr;
arr = arr;
arr = t;
}
}
}
return arr;
}
console.log(bubbleSort(arr),"比较次数：",count);
// '比较次数：' 15
</code></pre>
<p>上面代码中交换两个元素位置的时候，用了一个中间变量（t），可以改进一下。用一个解构赋值来交换值，就不用额外的一个中间变量（t）了。</p>
<pre><code class="language-javascript">let arr = ;
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - i - 1; j++) {
//比较相邻两个元素
if (arr > arr) {
//用结构赋值进行交换
, arr] = , arr];
}
}
}
return arr;
}
console.log(bubbleSort(arr));
//
</code></pre>
<hr>
<h1 id="02vue实现一个冒泡动画">02、Vue实现一个冒泡动画</h1>
<p>用Vue来实现一个可视化的冒泡排序，用Vue就不用去操作Dom了，只需要要处理好排序过程即可，因此首先要对排序过程进行改造。</p>
<h2 id="21排序过程改造">2.1、排序过程改造</h2>
<p>上一章节的排序是连续执行，瞬间完成的。要实现可视化的排序效果，每一个排序步骤之间得有间隔，给过渡动画留时间。就需要把排序的每一个步骤拆开，可以单独控制执行。</p>
<ul>
<li>定义一个排序对象<code>SortItem</code>，包装待排序元素，用于可视化展示，属性包括排序值、泡泡大小、泡泡颜色。</li>
<li>用上面的排序对象<code>SortItem</code>，生成排序对象集合，正式排序步骤中用该集合。方法的参数为排序元素字符串，空格隔开，如“9 100 6 17 3 1”。</li>
</ul>
<pre><code class="language-javascript">//定义一个排序对象，包装待排序元素
function SortItem(n) {
this.value = n;
this.size = 30 + n + 'px';//泡泡大小，初试大小30px
this.color = bubbleColor.default;
}
//生成排序对象集合，参数为排序元素字符串，如“9 100 6 17 3 1”
function generateSortItems(arrStr) {
let arrItems = [];
let arr = arrStr.trim().split(' ');
for (let i = 0; i < arr.length; i++) {
arrItems = new SortItem(window.parseInt(arr));
}
return arrItems;
}
</code></pre>
<p>泡泡列表展示效果如下：</p>
<p><img src="https://img2023.cnblogs.com/blog/151257/202212/151257-20221217212826580-1685773223.png" alt="image.png" loading="lazy"></p>
<ul>
<li>然后就是排序过程了，对排序对象集合进行遍历，把每一次排序操作包装成一个（闭包）函数，放到一个集合里，后面就可自定义调用执行了。</li>
<li>先是用集合实现了一遍，发现这个场景用迭代器<code>Generator</code>更优雅，马上重构，上迭代器！每次迭代<code>yield</code>返回排序的函数。</li>
</ul>
<pre><code class="language-javascript">//迭代器实现排序步骤的拆分
function* generateSortFunc(items) {
const len = items.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - i - 1; j++) {
//迭代器返回的是一个（闭包）函数，为每一个排序步骤
yield () => {
//执行排序前重置泡泡颜色
resetColor(items);
//正在排序的泡泡元素高亮
items.color = bubbleColor.inprocess;
items.color = bubbleColor.inprocess;
if (items.value > items.value) {
, items] = , items];
}
}
}
//完成一轮排序，末尾泡泡元素标记为完成态颜色
items.color = bubbleColor.completed;
}
}
</code></pre>
<p><strong>🔸什么是Generator？</strong></p>
<ul>
<li>她是一个<strong>迭代器</strong>，返回一个遍历器对象，符合可迭代协议和迭代器协议，可用<code>next()</code>、<code>for(of)</code>迭代。</li>
<li>她是<strong>可控函数</strong>：内部代码可以自由控制暂停和继续执行。标准的函数是一次性执行完毕，直到末尾或<code>return</code>语句。而生成器的函数可以由<code>yield</code>暂停执行（交出控制权），<code>next()</code>恢复执行。</li>
<li>她是一个<strong>状态机</strong>，封装了多个内部状态。</li>
<li>她是<strong>异步任务管理容器</strong>，提供一种异步的实现方案。</li>
</ul>
<p>Generator 使用一个特殊的函数语法<code>function*</code>（带星<code>*</code>号）创建生成器<code>generator</code>，调用生成器函数获得一个生成器对象，该对象的实例方法：</p>
<table>
<thead>
<tr>
<th><strong>实例方法</strong></th>
<th><strong>描述</strong></th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>next</strong>()</td>
<td>恢复执行，返回一个由 <code>yield</code>表达式生成的值：<code>{value: 1, done: false}</code></td>
</tr>
<tr>
<td><strong>return</strong>(value?)</td>
<td>返回给定的值并结束生成器，可提前中止生成器。</td>
</tr>
<tr>
<td><strong>throw</strong>()</td>
<td>向生成器抛出一个错误，生成器内部如没处理则会中止</td>
</tr>
</tbody>
</table>
<h2 id="22可视化排序">2.2、可视化排序</h2>
<p>接下来就不难了，排序的执行就是调用执行器的<code>next()</code>方法，如果返回对象的<code>done</code>属性为<code>true</code>，则表示迭代完成，否则继续迭代，执行排序函数。</p>
<pre><code class="language-javascript">//单步执行
play() {
let next = this.sortFunc.next();
if (next.done) {
this.sortItems.forEach(item => item.color = bubbleColor.completed);
this.stop();
}
else
next.value();
},
</code></pre>
<ul>
<li><code><li></code>元素来显示排序对象。</li>
<li>移动动画用的Vue的<code><transition-group></code>组件来实现。</li>
<li>“单步执行”就是点击一次只执行一步，“自动执行”则会自动顺序执行。</li>
<li>修改参数后需”重置“进行初始化。</li>
</ul>
<p>手动单步执行效果：</p>
<p><img src="https://img2023.cnblogs.com/blog/151257/202212/151257-20221217212826600-1640242755.gif" alt="1.gif" loading="lazy"></p>
<p>自动执行或更多排序参数可以直接查看在线代码示例：掘金-代码（可视化冒泡），完整代码也在这里。</p>
<p>点击查看【juejin】</p>
<hr>
<h1 id="参考资料">参考资料</h1>
<ul>
<li>https://visualgo.net/zh/sorting</li>
<li>冒泡排序</li>
<li>掘金-代码（可视化冒泡）</li>
</ul>
<hr>
<blockquote>
<p><strong>©️版权申明</strong>：版权所有@安木夕，本文内容仅供学习，欢迎指正、交流，转载请注明出处！<em>原文编辑地址-语雀</em></p>
</blockquote><br><br>
来源：https://www.cnblogs.com/anding/p/16989579.html
頁:
[1]