前言:排序算是编程的一项基础技能,但是排序的过程并不直观,在新手入门的时候可能会在理解上产生一定的阻碍,所以本文将通过 js
来实现一些简单的排序,将整个排序的过程可视化出来,让排序知识更加通俗易懂。
重点知识
setInterval
, 按指定周期计算函数(重复计算)setTimeout
, 指定时间后计算函数(计算一次)
冒泡排序
原理: 通过比较相邻元素的大小,元素值大的进行往后挪。
由于我们要使用 setInterval
来实现循环模拟,所以在函数开始的位置得事先设置定时器,在排序完成之后清除定时器。
为了使排序的动画更加显著,当前正在比较的两个元素设置为活跃状态即外边框为红色。具体设置的代码如下:
function setCss(){
$mylist.removeClass('active');
// 首先将之前比较的元素设置为不活跃状态
$($mylist[current]).addClass("active");
$($mylist[next]).addClass("active");
}
然后就是如何实现两个元素的交换动画,在这里引用Github中他人实现交换代码。
传送门:https://github.com/tejanium/jquery.swap
接下来就是一步一步的进行比较,当比较到最后一个元素时,将当前元素置 0,下一个元素置 1。 具体代码如下:
timer = setInterval(function(){
if(times < count-1){
finished = exchange();
if(!finished){
current++;
next++;
if(current == count-times-1){
times++;
current = 0;
next = 1;
drawProcess();
}
setCss();
}
}
else{
clearInterval(timer);
$mylist.removeClass('active');
}
}, 1000)
选择排序
原理:在每一趟排序中,选择出最大的元素,然后将这个元素放置在未排好序元素的末尾。
比较连个元素的大小时,先获取元素的文本,再将文本转化为整型,即可进行比较。具体实现如下:
function compare(){
$mylist = $("#unorder li")
var cur_val = parseInt($($mylist[current]).text());
var max_val = parseInt($($mylist[max_pos]).text());
if(cur_val > max_val){
return true;
}
return false;
}
关键步骤
首先假定最大元素在首位,依次将其后无序的元素与其进行比较,如果当前元素大于最大元素值,则更新最大元素值的位置,直到到最后一个元素,进行交换。之后,更新最大元素的位置为 0。
代码如下
function start(){
setCss();
timer = setInterval(function(){
if(times > 0){
var comp = compare();
if(comp){
max_pos = current;
current++;
}
else{
current++;
}
if(current == times+1){
exchange();
times --;
current = 1;
max_pos = 0;
setTimeout(drawProcess, 1000);
}
setCss();
}
else{
$mylist.removeClass('max');
$mylist.removeClass('active');
clearInterval(timer);
}
}, 1000)
}
插入排序
原理:与玩扑克牌的原理一致,每次找准每个元素的位置,然后插入进去。
由于插入效果代码并没有在网上找到,于是便根据上诉交换的效果的代码,自己依葫芦画瓢实现了一个。但是一个缺点就是没有做到很好的封装性,无法适用于所有情况,具体如下:
(function ($){
$.fn.insert = function(a, b){
t = this;
if(t.length >= 1 && typeof(a) === "number" && a <= t.length){
if(a == 0){
_insert(t[0], b, true);
}
else{
_insert(t[a-1], b, false);
}
return t;
}
else if(t.length === 0){
b_clone = $(b).clone().css("opacity", 0);
$("#order").prepend(b_clone);
var first = $("#order li");
first.insert(0, b);
b_clone.remove();
}
};
function _insert(a, b, option){
var from = $(b),
dest = $(a),
from_pos = from.offset(),
dest_pos= from.offset(),
from_clone = from.clone(),
dest_clone = dest.clone();
from.css("opacity", 0);
from_clone.insertAfter(from).css({position: "absolute", width: from.outerWidth(), height: from.outerHeight()}).offset(from_pos).css("z-index", "999");
if(option){
dest_clone.insertBefore(dest).css("opacity", 0);
}
else{
dest_clone.insertAfter(dest).css("opacity", 0);
}
var route_from_vertical = dest_clone.offset().top - from_clone.offset().top;
var route_from_horizontal = dest_clone.offset().left - from_clone.offset().left;
from_clone.animate({
top: "+=" + route_from_vertical + "px",
left: "+=" + route_from_horizontal + "px",
},
"slow",
function(){
from.insertBefore(dest_clone).css("opacity", 1);
$(this).remove();
dest_clone.remove();
});
return from;
}
})(jQuery);
关键步骤
将每个元素与排好序的元素进行比较,找准元素的位置进行插入。第一元素无需进行比较,直接进行插入。代码如下:
function start(){
mylist = $("#unorder li");
var firstElement = mylist[0];
sortList = $("#order li");
sortList.insert(0, firstElement);
setCSS();
timer = setInterval(function(){
mylist = $("#unorder li");
firstElement = mylist[0];
sortList = $("#order li");
var comp = compare(firstElement, sortList[cur_pos]);
if(comp){
cur_pos++;
if(cur_pos === sortList.length){
sortList.insert(cur_pos, firstElement);
cur_pos = 0;
}
}
else{
sortList.insert(cur_pos, firstElement);
cur_pos = 0;
}
setCSS();
sortList = $("#order li");
if(sortList.length === count){
clearInterval(timer);
}
}, 1000);
}
最后做成的网页如下图所示,可选项是三种排序方法,每一次刷新网页都会随机生成一个数组。
存在的bug
上诉效果演示是使用了bootstrap作为页面显示的前端框架,而不用框架的话,效果会更加生动,元素首先会变大,然后在缩小,具体如下:
我不知道为何用了bootstrap之后,元素的效果是没有变大,而是直接进行了交换?在控制台惊醒调试的时候发现了这个。
这个是在用了bootstrap之后的调试结果:
这个是没有用bootstrap之后调试的结果:
我不明白css都是用的同样的代码,为什么两者的宽度会是截然不同的?
潜在的bug,一直未能解决?