① 用Javascript写排序算法的动画演示
1.让JavaScript暂停下来,慢下来。
JavaScript排序是很快的,要我们肉眼能看到它的实现过程,我首先想到的是让排序慢下来。 排序的每一个循环都让它停300ms然后再继续进行。 怎么样才能停下来呢。查了一下JavaScript貌似没有sleep()这样的函数。暂停做不到,但是可以想办法让实现跟暂停差不多的效果。比如在循环里做一些无关的事情 。
首先尝试了让while(true)来一直执行一个空操作。执行一段时间再回到排序逻辑。代码大致是这样:
for (var i = 0; i < 3; i++) {
document.writeln(i); //DOM操作
var now = new Date().getTime();
while(new Date().getTime() - now < 3000){}
}
慢是慢下来了。不过太耗资源,排序进行过程中dom并不会有任何改变,直到排序结束, DOM会变成排序好之后的样子。 但是如果设置断点一步步执行的时候 又可以看到一步步的排序变化。估计是因为这个操作太耗资源导致浏览器下达了一个DOM操作的命令但是一直腾不出资源来进行DOM操作。所以真正DOM操作的时候在js代码执行结束之后。
所以让JavaScript排序慢来来还是没有实现。
另一种让JavaScript暂停下来的思路:
写这个文章的时候又想到一种方法来让JavaScript停下来。 那就是AJAX的同步请求,以及超时操作。 也就是在要停下来的地方放一个AJAX请求,同步请求, 然后设置超时。超时的时间就是我们要暂停的时间。为了避免在到达超时请求之前服务 器就返回了我们的AJAX请求。可以在服务端运行类似 sleep()的程序 。从而保证AJAX不会返回。直接超时然后返回到我们的循环。不过这只是个设想。有兴趣的可以去尝试一下。
2.闭包和定时器。 这种思路不需要让排序过程慢下来。而是使用闭包缓存排序过程中数组的变化。然后使用setTimeout来确定展示每一个数组状态的顺序。在排序循环中放入类似下面的代码。
(function(){
var theArr = arr.slice();//当前数组状态的备份
setTimeout(function(){
bubbleSortDom(theArr);//排序的DOM操作。
},500*timeCount);
timeCount++;//定时器的顺序。
})();
不过后来发现这样子写的话代码量会比较大,逻辑有修改的话要修改的地方会有点多。局限性很多,比如要实现排序动画加快或减慢操作几乎是很困难的。所以还要另想办法。
3.缓存排序中的数组状态。
也就是在排序过程中。将数组的每一轮循环的状态保存到一个数组。然后再用这个数组依次将排序状态保存下来。 只需要在排序中加入一句就行。
this.pushHis(arr.slice(),i-1,j,k,temp);
这样就只需要一个setInterval()就可以了。并且可以很方便的实现动画的加快与减慢。逻辑也比较好理解 。
问题二:如何实现JavaScript排序动画的加快与减慢。
我们问题一使用的第三种方法。 得到一个保存了每一步排序状态的数组arr。 然后我们可以使用一个setInterval()定时器一步步展现排序状态。 如果要加快速度或减慢速度。就clearInterval(),修改定时器的执行间隔,重新setInterval(),从前一个定时器执行到数组中的位置开始执行。
问题三:对于使用递归实现的数组怎么办? 不是在原数组上进行操作的怎么办?
使用递归实现的排序。 可能并没有在一个数组上进行操作,只是最后返回一个排序好的数组出来。那么我们要如何获得排序中的数组的完整状态呢。
比如快速排序。
最开始不考虑动画,我的实现是这样的:
function quickSort(arr){
var len = arr.length,leftArr=[],rightArr=[],tag;
if(len<2){
return arr;
}
tag = arr[0];
for(i=1;i<len;i++){
if(arr[i]<=tag){
leftArr.push(arr[i])
}else{
rightArr.push(arr[i]);
}
}
return quickSort(leftArr).concat(tag,quickSort(rightArr));
}
然后为了考虑动画,我改写了它的逻辑,让它在同一个数组上进行了实现。 其实是在递归的时候传入了当前的的子数组在原数组中的起始位置。从而在原数组上进行了操作。
用了两种方法来实现方式。在排序逻辑上略有不同。
第一种是先跟远处的对比。遇到比自己小的放到自己前面去。循环序号+1。比自己大的放到当前排序子数组的最后面去,循环序号不变。直到排列完成。
这种方法的缺点是即使是一个有序数组。它也会重新排。
第二种方法是 除了标记位,再设置一个对比位。 遇到比自己小的,放到前面去,标记位的位置+1,标记位与对比位之间所有的往后面移动一个位置。
遇到比自己大的。标记位不变,对比位+1。
这种方法的缺点是对数组进行的操作太多。优点是对有序数组不会再排。
方式一:
function quickSort(arr,a,b,qArr){
var len = arr.length,leftArr=[],rightArr=[],tag,i,k,len_l,len_r,lb,ra,temp;
if(a == undefined && b == undefined){
a = 0; b= arr.length-1;//初始化起始位置。
}
if(qArr == undefined){
qArr = arr.slice();
}
if((len == 2 && arr[0] == arr[1])||len<2){
return arr;
}
tag = qArr[a];
for (i = 1; i < len;) {
if(qArr[a+i]<=tag){
leftArr.push(qArr[a+i]);
qArr[a+i-1] = qArr[a+i];
qArr[a+i] = tag;
k = a+i;
i++;
}else{
if(leftArr.length+rightArr.length == len-1){
break;
}
temp = qArr[a+i];
qArr[a+i] = qArr[b-rightArr.length];
qArr[b-rightArr.length] = temp;
rightArr.push(temp);
k = a+i-1;
}
this.pushHis(qArr.slice(),a,b,k);
}
len_l = leftArr.length;
len_r = rightArr.length;
if(len_l== 0){
lb = a;
}else{
lb = a+len_l -1;
this.sort(leftArr,a,lb,qArr);
}
if(len_r == 0){
ra = b;
}else{
ra = b + 1 - len_r;
this.sort(rightArr,ra,b,qArr)
}
return qArr
}
方式二:
function quickSort2(arr,a,b,qArr){
var len = arr.length,leftArr=[],rightArr=[],tag,i,j,k,temp,len_l,len_r,lb,ra;
if(a == undefined && b == undefined){
a = 0; b= arr.length-1;//初始化起始位置。
}
if(qArr == undefined){
qArr = arr.slice();
}
if(len<2){
return arr;
}
if(len == 2 && arr[0] == arr[1]){
return arr;
}
tag = qArr[a];
for (i = 1,k = 0; i < len;) {
if(qArr[a+i]>=tag){
rightArr.push(qArr[a+i]);
i++;
}else{
temp = qArr[a+i];
for(j = a+i;j>a+k;j--){
qArr[j] = qArr[j-1];
// this.pushHis(qArr.slice(),a,b,a+k);
}
qArr[a+k] = temp;
leftArr.push(temp);
k++;
i++;
}
this.pushHis(qArr.slice(),a,b,a+k,i-1);
}
len_l = leftArr.length;
len_r = rightArr.length;
if(len_l== 0){
lb = a;
}else{
lb = a+len_l -1;
this.sort(leftArr,a,lb,qArr);
}
if(len_r == 0){
ra = b;
}else{
ra = b + 1 - len_r;
this.sort(rightArr,ra,b,qArr)
}
return qArr;
}
具体的不同下面会有动画演示。
问题四:动画的流畅。
排序动画的DOM操作是很多的很快的。这里我做的优化只是让每一个排序步骤只涉及一个DOM操作。 全部由JavaScript拼接好,一次替换。类似下面的代码。
效果图:
主要实现了:
冒泡排序JavaScript动画演示
插入排序JavaScript动画演示
选择排序JavaScript动画演示
快速排序JavaScript动画演示
归并排序JavaScript动画演示
希尔排序JavaScript动画演示
② 冒泡排序算法 [“排序算法设计”教学设计]
一、教材依据本节课是奥教版《算法与程序设计》(选修1)第四章《算法与程序实现》的第4节第1课时。二、设计思想【教学指导思想】:基于问题主导的教学模式。
【设计理念】:本节课采用基于问题主导的创新教学模式,指导学生在问题解决视野下去亲历算法分析与程序设计实践、理解算法思想、发现新问题,从而全面提升学生的能力。
【教材分析】:排序算法是程序设计的基本算法,主要要求学生理解选择排序算法,选择排序算法的特点,进一步分析排序算法时间和空间效率。
【学情分析】:高二年级的学生在高一阶段袜亩山的必修教材中已经学习了编制程序解决问题,他们已经具有较强的逻辑思维能力和分析问题的能力,只要讲清楚算法,本节课的内容对学生来说应该容易掌握。
三、教学目标
【知识目标】:理解选择排序算法思想,学会使用选择排序算法思想解决问题。
【能力目标】:通过学习选择排序算法,提高学生分析与解决问题的能力。
【情感态度与价值观】:通过上机完成“大型国际运动会上的国家排序问题"VB程序设计,体验编程快乐、感受成功的喜悦与程序的魅力。
四、教学重点
选择排序算法的基本思想及相关的程序实现。
五、教学难点
如何使用选择排序算法解决实际的问题。
六、教学准备
1.用PowerPoint 2003制作的课件。
2.从网上下载选择排序的动画演示文件。
七、教学过程
1.引入新课:(以一些现实生活的实际问题开始,启发同学们去思考)
教师:同学们每次的考试成绩我们会以Excel表格的形式公布给大家,同学们想想计算机是如何在瞬间进行分数排序的呢?
学生想。
2.启发思考,分析选择排序算法及程序实现。
教师:好,今天我们就来学习选择排序算法。
开始新课学习:
教师:现在我们一起看看人工是如何进行数据的排序的,老师给出8位同学的分数,同学们把它们由小到大地排成顺序。数据分别是:86.5,77.5,87,68.9,89.6,77.2,79.7,71.1。同学们想想笫一个位置应该放哪个数?
学生:放最小的。
教师:好,那么,我们是不是只需要将最小的数68.9与在第一个位置的数86.5进行交换呢?
学生:是。
教师:同学们再想一下第二个位置是不是应该放置的是除了第一个以外的数中最小的呢?
学生:是。
教师:那么第N-1个位置应该放什么呢?
学生:应该放置告中的是除了前N-2个以外的数中最小的。
教师:老师是不是可以总结我们刚才的算法,所谓选择排序,就是给数组的N-1个位置选择合适的数据,而每次是选择第i个位置的数据到最后一个位置(第Ⅳ个位置)的数据的最小值,然后将找到的最小数据与第i个位置上的数据交换?
学生:是的。
教师:下面我用一个动画演示刚才的算法,请同学们看大屏幕。
现在我们只需要将刚才的算法用VB语言表达出来,就是选择排序的程序,那么我们需要解决三个问题:
(1)给数组的N-1个位置选择合适的数据?这个问题显然我们可以用一个循环结构来完成:For i=l【o
N-1Next i
(2)如何寻找第i个位置的数据到最后一个位置(第Ⅳ个位置)的数据的最小值?
这个问题也就是在数组中的极值(最大值或最小值)的问题。其实我们只关心最小值数据的位置,用变量M记录其位置。
于是我们很容易写出选择排序的程序。
3.调试程序:
教师:同学们想不想看一下运行结果呢?
学生:想(很耐橘强烈)。
教师:运行程序后,输入测试数据,可得排序后的输出结果在窗体上。
4.课堂实践练习与知识拓宽:
(1)完成课本127页的国家名排序问题。
【设计意图】:使学生看到选择排序不仅可以对数字排序,也可以对字符串排序,同时也能达到对选择排序的应用练习。
(2)明明的随机数(题目描述发送到学生机的桌面)
【设计意图】:这个问题是很现实的例子,学生对这个问题很感兴趣,激发他们探索的欲望,要求学习优秀的学生必须完成,我想通过这个问题,一方面提升学生学习的积极性;另一方面再通过这个实际问题的解决,实现本节课的知识目标。
【学习评价】:教师随机让个别学生讲解练习题的算法、演示其所编程序,师生共同进行点评。
【课堂小结】:
(1)什么是选择排序算法?
(2)选择排序算法的实质及时间和空间效率。
(3)选择排序算法的优点、缺点。
八、教学反思
通过本节课的 教学设计 ,我认识到信息技术教学的关键是要调动学生的积极性,算法与程序设计这部分知识如果课堂教学设计不当,就会让学生觉得很枯燥,所以我将抽象的问题通俗化,复杂的问题分解成几个小问题来解决,这样学生就很容易接受,再加上所举的例子都是学生身边的实际事例,使学生很想知道问题的答案,从而极大地调动了学生的积极性。
(作者单位陕西省成阳市礼泉县第一中学)
③ 希尔排序法原理
希尔排序法(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序的方法。
算法思想简单描述
在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,
并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为
增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除
多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中
记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量
对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成
一组,排序完成。
下面的函数是一个希尔排序算法的一个实现,初次取序列的一半为增量,
以后每次减半,直到增量为1。
希尔排序是不稳定的。
④ 面试必会八大排序算法(Python)
一、插入排序
介绍
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。
算法适用于少量数据的排序,时间复杂度为O(n^2)。
插入排算法是稳定的排序方法。
步骤
①从第一个元素开始,该元素可以认为已经被排序
②取出下一个元素,在已经排序的元素序列中从后向前扫描
③如果该元素(已排序)大于新元素,将该元素移到下一位置
④重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置中
⑥重复步骤2
排序演示
算法实现
二、冒泡排序
介绍
冒泡排序(Bubble Sort)是一种简单的排序算法,时间复杂度为O(n^2)。
它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
原理
循环遍历列表,每次循环找出循环最大的元素排在后面;
需要使用嵌套循环实现:外层循环控制总循环次数,内层循环负责每轮的循环比较。
步骤
①比较相邻的元素。如果第一个比第二个大,就交换他们两个。
②对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
③针对所有的元素重复以上的步骤,除了最后一个。
④持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
算法实现:
三、快速排序
介绍
快速排序(Quicksort)是对冒泡排序的一种改进,借用了分治的思想,由C. A. R. Hoare在1962年提出。
基本思想
快速排序的基本思想是:挖坑填数 + 分治法。
首先选出一个轴值(pivot,也有叫基准的),通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
实现步骤
①从数列中挑出一个元素,称为 “基准”(pivot);
②重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边);
③对所有两个小数列重复第二步,直至各区间只有一个数。
排序演示
算法实现
四、希尔排序
介绍
希尔排序(Shell Sort)是插入排序的一种,也是缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法,时间复杂度为:O(1.3n)。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
·插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率;
·但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位。
基本思想
①希尔排序是把记录按下标的一定量分组,对每组使用直接插入算法排序;
②随着增量逐渐减少,每组包1含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法被终止。
排序演示
算法实现
五、选择排序
介绍
选择排序(Selection sort)是一种简单直观的排序算法,时间复杂度为Ο(n2)。
基本思想
选择排序的基本思想:比较 + 交换。
第一趟,在待排序记录r1 ~ r[n]中选出最小的记录,将它与r1交换;
第二趟,在待排序记录r2 ~ r[n]中选出最小的记录,将它与r2交换;
以此类推,第 i 趟,在待排序记录ri ~ r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
排序演示
选择排序的示例动画。红色表示当前最小值,黄色表示已排序序列,蓝色表示当前位置。
算法实现
六、堆排序
介绍
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。
利用数组的特点快速指定索引的元素。
基本思想
堆分为大根堆和小根堆,是完全二叉树。
大根堆的要求是每个节点的值不大于其父节点的值,即A[PARENT[i]] >=A[i]。
在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。
排序演示
算法实现
七、归并排序
介绍
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
基本思想
归并排序算法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
算法思想
自上而下递归法(假如序列共有n个元素)
① 将序列每相邻两个数字进行归并操作,形成 floor(n/2)个序列,排序后每个序列包含两个元素;
② 将上述序列再次归并,形成 floor(n/4)个序列,每个序列包含四个元素;
③ 重复步骤②,直到所有元素排序完毕。
自下而上迭代法
① 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
② 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
③ 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
④ 重复步骤③直到某一指针达到序列尾;
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。
排序演示
算法实现
八、基数排序
介绍
基数排序(Radix Sort)属于“分配式排序”,又称为“桶子法”。
基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m) ,其中 r 为采取的基数,而m为堆数。
在某些时候,基数排序法的效率高于其他的稳定性排序法。
基本思想
将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
基数排序按照优先从高位或低位来排序有两种实现方案:
MSD(Most significant digital) 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等,再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。
LSD (Least significant digital)从最右侧低位开始进行排序。先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。
排序效果
算法实现
九、总结
各种排序的稳定性、时间复杂度、空间复杂度的总结:
平方阶O(n²)排序:各类简单排序:直接插入、直接选择和冒泡排序;
从时间复杂度来说:
线性对数阶O(nlog₂n)排序:快速排序、堆排序和归并排序;
O(n1+§))排序,§是介于0和1之间的常数:希尔排序 ;
线性阶O(n)排序:基数排序,此外还有桶、箱排序。
⑤ 用VB编制一个动态的演示排序操作的实用程序
现在VB的话一般用ADO连接数据的比较多,可以用控件ADODC直接生成连接数据的语句,最好把最后连接的机器的名称改成IP。
1.在数据库中建立HM和HM2两个表,注意你建立数据表的时候各列名称设定好。
2.VB中触发时间是List1的CLICK时间,然后检测是否收到ASC码13(即回车符)检测到后往下执行
3.对输入的字符串做检测,可以先检测长度是否7位或11位,然后对各个位是否为数字做检测(可以循环去ASC的办法),是则往下执行,否则List1清零。
4.VB连接数据库,去其中号码与List1对用的那条记录,然后去各个列的内容分别填入list2、list3、list4、list5就OK了。
总体而言的话这个程序应该不难,不过我没用VB连接ACESS所以不能给你全部的代码,其他的我有部分类似的程序,你要的话发消息给我吧。
⑥ 十大经典排序算法动画演示
姓名:邓霜意 学号:20021210598
【嵌牛导读】:排序算法是算法学习中的重难点,本文通过动画的形式清楚明了的展示经典排序算法的原理槐野与思想。
【嵌牛鼻子】:快速排序 选择排序 堆排序 希尔排序 归并排序
【嵌牛提问】:最好的排序算法是什么?
【嵌牛正文】:
1、Sorting Algorithms Animations
2、算法的分碧森类
3、时间复杂度
算法
1、冒泡排序
2、快速排序
3、直接插入排序
4、选择排序
5、归并排序
6、堆排序
7、希尔排序
8、计数排序
9、基数排序
10、桶排序
总结: 目前并没有十全十美的排序算法,有优点就会有缺点,即便是快速排序算法,也只是整体性能上优越,它也存在排序不稳定、需要大量的辅助空间、对少量数据排序无优势等不铅慧喊足。因此我们需要根据待排序数据的具体情况以及性能要求选择合适的排序算法。