本文实例讲述了JavaScript数据结构与算法之基本排序算法定义与效率比较。分享给大家供大家参考,具体如下:
javascript数据结构与算法--基本排序算法(冒泡、选择、排序)及效率比较
一、数组测试平台
javascript数据结构与算法--基本排序(封装基本数组的操作),封装常规数组操作的函数,比如:插入新数据,显示数组数据,还有交换数组元素等操作来调用不同的排序算法
function CArray(numElements) { this.dataStore = []; this.pos = 0;//是一个索引值,默认为0,从第一个开始 this.numElements = numElements;//是保存所有的数组元素 this.insert = insert;//向数组中插入一个元素的方法 this.toString = toString;//显示数组中所有元素 this.clear = clear;//清空数组数据 this.setData = setData;//生成了存储在数组中的随机数字 this.swap = swap;//交换数组中两个元素的位置 this.bubbleSort = bubbleSort; /*将传入的数组,存储在datastore中*/ for (var i = 0; i < numElements.length; ++i) { this.dataStore[i] = numElements[i]; } } function setData() { for (var i = 0; i < this.numElements; ++i) { this.dataStore[i] = Math.floor(Math.random() * (this.numElements+1)); } } function clear() { for (var i = 0; i < this.dataStore.length; ++i) { this.dataStore[i] = 0; } } function insert(element) { this.dataStore[this.pos++] = element; } function toString() { var retstr = ""; for (var i = 0; i < this.dataStore.length; ++i) { retstr += this.dataStore[i] + " "; if (i > 0 && i % 10 == 0) { retstr += "\n"; } } return retstr; } function swap(arr, index1, index2) { var temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } //测试生成一组数组数据(随机数) var numElements = 100; var myNums = new CArray(numElements); myNums.setData(); console.log(myNums.toString());
17 94 81 80 25 24 73 76 24 35 81
63 81 59 4 76 30 47 73 98 18
54 36 53 47 22 60 88 41 66 24
73 94 40 45 72 74 14 61 92 48
36 12 42 11 12 82 24 84 60 1
17 98 63 36 84 13 18 50 89 26
98 1 6 54 52 69 6 52 98 14
79 28 19 69 76 99 97 100 10 7
24 54 81 73 18 21 45 73 66 30
28 56 54 21 88 31 20 86 48
二、冒泡排序算法
我们先来了解一下冒泡排序算法,它是最慢的排序算法之一,但也是一种最容易实现的排序算法。
之所以叫冒泡排序是因为使用这种排序算法排序时,数据值会像气泡一样从数组的一端漂浮到另一端。
假设正在将一组数字按照升序排列,较大的值会浮动到数组的右侧,而较小的值则会浮动到数组的左侧。
之所以会产生这种现象是因为算法会多次在数组中移动,比较相邻的数据,当左侧值大于右侧值时将它们进行互换。
JS代码如下:
function CArray(numElements) { this.dataStore = []; this.pos = 0;//是一个索引值,默认为0,从第一个开始 this.numElements = numElements;//是保存所有的数组元素 this.insert = insert;//向数组中插入一个元素的方法 this.toString = toString;//显示数组中所有元素 this.clear = clear;//清空数组数据 this.setData = setData;//生成了存储在数组中的随机数字 this.swap = swap;//交换数组中两个元素的位置 this.bubbleSort = bubbleSort;//冒泡算法 /*将传入的数组,存储在datastore中*/ for (var i = 0; i < numElements.length; ++i) { this.dataStore[i] = numElements[i]; } } function setData() { for (var i = 0; i < this.numElements; ++i) { this.dataStore[i] = Math.floor(Math.random() * (this.numElements+1)); } } function clear() { for (var i = 0; i < this.dataStore.length; ++i) { this.dataStore[i] = 0; } } function insert(element) { this.dataStore[this.pos++] = element; } function toString() { var retstr = ""; for (var i = 0; i < this.dataStore.length; ++i) { retstr += this.dataStore[i] + " "; if (i > 0 && i % 10 == 0) { retstr += "\n"; } } return retstr; } function swap(arr, index1, index2) { var temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } function bubbleSort() { var numElements = this.dataStore.length; for (var outer = numElements; outer >= 2; --outer) { for (var inner = 0; inner <= outer-1; ++inner) { if (this.dataStore[inner] > this.dataStore[inner+1]) { swap(this.dataStore, inner, inner+1); } } console.log("outer为" + outer + ": " + this.toString()); } } //测试冒泡排序算法 var numElements = [2,4,1,3]; var myNums = new CArray(numElements); console.log("原来的数组:"+myNums.toString()); myNums.bubbleSort(); console.log("排序后的数组:"+myNums.toString());
冒泡算法代码分析如下:
原先数组为 [2,4,1,3];
1. outer为4的时候
1. inner为0,值为2,inner+1为1,值为4,不符合,不交换。
2. inner为1,值为4,inner+1为2,值为1,交换,数组变为[2,1,4,3]
3. inner为2,值为4,inner+1为3,值为3,交换 数组变为[2,1,3,4]
4. inner为3,值为4,inner+1为4,不符合 不交换。
2. outer为3的时候
1. inner为0,值为2,inner+1为1,值为1,交换 数组变为[1,2,3,4]
2. inner为1, 值为2,inner+1为2,值为3 不符合 不交换。
3. inner为2, 值为3,inner+1为3,值为4,不符合 不交换。
再下面继续循环都不符合条件,所以如上就是最后一步了。这就是冒泡排序。
三、选择排序算法
选择排序从数组的开头开始,将第一个元素和其他元素进行比较。
检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续。
这个过程一直进行,当进行到数组的倒数第二个位置时,所有的数据便完成了排序。
选择排序会用到嵌套循环。
外循环从数组的第一个元素移动到倒数第二个元素;
内循环从第二个数组元素移动到最后一个元素,查找比当前外循环所指向的元素小的元素。
每次内循环迭代后,数组中最小的值都会被赋值到合适的位置。
JS代码如下:
function CArray(numElements) { this.dataStore = []; this.pos = 0;//是一个索引值,默认为0,从第一个开始 this.numElements = numElements;//是保存所有的数组元素 this.insert = insert;//向数组中插入一个元素的方法 this.toString = toString;//显示数组中所有元素 this.clear = clear;//清空数组数据 this.setData = setData;//生成了存储在数组中的随机数字 this.swap = swap;//交换数组中两个元素的位置 this.selectionSort = selectionSort;//选择排序算法 /*将传入的数组,存储在datastore中*/ for (var i = 0; i < numElements.length; ++i) { this.dataStore[i] = numElements[i]; } } function setData() { for (var i = 0; i < this.numElements; ++i) { this.dataStore[i] = Math.floor(Math.random() * (this.numElements+1)); } } function clear() { for (var i = 0; i < this.dataStore.length; ++i) { this.dataStore[i] = 0; } } function insert(element) { this.dataStore[this.pos++] = element; } function toString() { var retstr = ""; for (var i = 0; i < this.dataStore.length; ++i) { retstr += this.dataStore[i] + " "; if (i > 0 && i % 10 == 0) { retstr += "\n"; } } return retstr; } function swap(arr, index1, index2) { var temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } function selectionSort() { var min, temp; for (var outer = 0; outer <= this.dataStore.length-2; ++outer) { min = outer; for (var inner = outer + 1;inner <= this.dataStore.length-1; ++inner) { if (this.dataStore[inner] < this.dataStore[min]) { min = inner; } } swap(this.dataStore, outer, min); console.log("第"+outer +"次:"+myNums.toString()); } } //测试排序算法 var numElements = [2,4,1,3]; var myNums = new CArray(numElements); console.log("原来的数组:"+myNums.toString()); myNums.selectionSort(); console.log("排序后的数组:"+myNums.toString());
原来的数组:2 4 1 3
第0次:1 4 2 3
第1次:1 2 4 3
第2次:1 2 3 4
排序后的数组:1 2 3 4
四、插入排序算法
插入排序有两个循环。
外循环将数组元素挨个移动,而内循环则对外循环中选中的元素及它前面的那个元素进行比较。
如果外循环中选中的元素比内循环中选中的元素小,那么数组元素会向右移动,为外循环中的这个元素腾出位置
function CArray(numElements) { this.dataStore = []; this.pos = 0;//是一个索引值,默认为0,从第一个开始 this.numElements = numElements;//是保存所有的数组元素 this.insert = insert;//向数组中插入一个元素的方法 this.toString = toString;//显示数组中所有元素 this.clear = clear;//清空数组数据 this.setData = setData;//生成了存储在数组中的随机数字 this.swap = swap;//交换数组中两个元素的位置 this.insertionSort = insertionSort;//插入排序算法 /*将传入的数组,存储在datastore中*/ for (var i = 0; i < numElements.length; ++i) { this.dataStore[i] = numElements[i]; } } function setData() { for (var i = 0; i < this.numElements; ++i) { this.dataStore[i] = Math.floor(Math.random() * (this.numElements+1)); } } function clear() { for (var i = 0; i < this.dataStore.length; ++i) { this.dataStore[i] = 0; } } function insert(element) { this.dataStore[this.pos++] = element; } function toString() { var retstr = ""; for (var i = 0; i < this.dataStore.length; ++i) { retstr += this.dataStore[i] + " "; if (i > 0 && i % 10 == 0) { retstr += "\n"; } } return retstr; } function swap(arr, index1, index2) { var temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } function insertionSort() { var temp, inner; //外循环将数组元素挨个移动 for (var outer = 1; outer <= this.dataStore.length-1; ++outer) { temp = this.dataStore[outer];//外循环选中的元素temp inner = outer; //内循环对外循环中选中的元素temp与temp前面的元素一个个进行比较。 //如果外循环中选中的元素temp比内循环中选中的元素小,那么数组元素会向右移动,为外循环中的这个元素腾出位置 while (inner > 0 && (this.dataStore[inner-1] >= temp)) { this.dataStore[inner] = this.dataStore[inner-1]; --inner; } this.dataStore[inner] = temp; console.log("第"+outer+"次:"+myNums.toString()); } } //测试排序算法 var numElements = [9,1,8,6,2,3,5,4]; var myNums = new CArray(numElements); console.log("原来的数组:"+myNums.toString()); myNums.insertionSort(); console.log("排序后的数组:"+myNums.toString());
原来的数组:9 1 8 6 2 3 5 4 //先用1和1前面的对比,9比1大,所以9向右移动一个位置,给1腾位置
第1次:1 9 8 6 2 3 5 4 //用8与8前面的对比,9比8大,所以9向右移动一个位置,给8腾位置
第2次:1 8 9 6 2 3 5 4 //用6与6前面的对比,8,9比6大,所以8、9向右移动一个位置,给6腾位置
第3次:1 6 8 9 2 3 5 4
第4次:1 2 6 8 9 3 5 4
第5次:1 2 3 6 8 9 5 4
第6次:1 2 3 5 6 8 9 4
第7次:1 2 3 4 5 6 8 9
排序后的数组:1 2 3 4 5 6 8 9
五、基本排序算法的效率比较
function CArray(numElements) { this.dataStore = []; this.pos = 0;//是一个索引值,默认为0,从第一个开始 this.numElements = numElements;//是保存所有的数组元素 this.insert = insert;//向数组中插入一个元素的方法 this.toString = toString;//显示数组中所有元素 this.clear = clear;//清空数组数据 this.setData = setData;//生成了存储在数组中的随机数字 this.swap = swap;//交换数组中两个元素的位置 this.bubbleSort = bubbleSort;//冒泡排序算法 this.selectionSort = selectionSort;//选择排序算法 this.insertionSort = insertionSort;//插入排序算法 /*将传入的数组,存储在datastore中*/ for (var i = 0; i < numElements.length; ++i) { this.dataStore[i] = numElements[i]; } } function setData() { for (var i = 0; i < this.numElements; ++i) { this.dataStore[i] = Math.floor(Math.random() * (this.numElements+1)); } } function clear() { for (var i = 0; i < this.dataStore.length; ++i) { this.dataStore[i] = 0; } } function insert(element) { this.dataStore[this.pos++] = element; } function toString() { var retstr = ""; for (var i = 0; i < this.dataStore.length; ++i) { retstr += this.dataStore[i] + " "; if (i > 0 && i % 10 == 0) { retstr += "\n"; } } return retstr; } function swap(arr, index1, index2) { var temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } function bubbleSort() { var numElements = this.dataStore.length; for (var outer = numElements; outer >= 2; --outer) { for (var inner = 0; inner <= outer-1; ++inner) { if (this.dataStore[inner] > this.dataStore[inner+1]) { swap(this.dataStore, inner, inner+1); } } // console.log("outer为" + outer + ": " + this.toString()); } } function selectionSort() { var min, temp; for (var outer = 0; outer <= this.dataStore.length-2; ++outer) { min = outer; for (var inner = outer + 1;inner <= this.dataStore.length-1; ++inner) { if (this.dataStore[inner] < this.dataStore[min]) { min = inner; } } swap(this.dataStore, outer, min); // console.log("第"+outer +"次:"+this.toString()); } } function insertionSort() { var temp, inner; //外循环将数组元素挨个移动 for (var outer = 1; outer <= this.dataStore.length-1; ++outer) { temp = this.dataStore[outer];//外循环选中的元素 inner = outer; //内循环则对外循环中选中的元素与它前面的那个元素进行比较。 //如果外循环中选中的元素比内循环中选中的元素小,那么数组元素会向右移动,为外循环中的这个元素腾出位置 while (inner > 0 && (this.dataStore[inner-1] >= temp)) { this.dataStore[inner] = this.dataStore[inner-1]; --inner; } this.dataStore[inner] = temp; // console.log("第"+outer+"次:"+this.toString()); } } /*测试冒泡、选择、插入算法的效率*/ var numElements = 10000; var nums = new CArray(numElements); nums.setData(); var start = new Date().getTime(); nums.bubbleSort(); var stop = new Date().getTime(); var elapsed = stop - start; console.log("用冒泡算法,排序 " + numElements + " 个元素耗时 : " + elapsed + " milliseconds."); start = new Date().getTime(); nums.selectionSort(); stop = new Date().getTime(); elapsed = stop - start; console.log("用选择算法,排序 " + numElements + " 个元素耗时: " + elapsed + " milliseconds."); start = new Date().getTime(); nums.insertionSort(); stop = new Date().getTime(); elapsed = stop - start; console.log("用插入算法,排序 " + numElements + " 个元素耗时: " + elapsed + " milliseconds.");
运行结果:
选择排序和插入排序要比冒泡排序快,插入排序是这三种算法中最快的。
感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具:http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。
PS:这里再为大家推荐一款关于排序的演示工具供大家参考:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具:
http://tools.jb51.net/aideddesign/paixu_ys
更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。
更新日志
- 【原神】V5.1攻略 | 纳西妲一图流攻略
- 群星.2003-重遇80·感动今天的都市人2CD【SONY】【WAV+CUE】
- 希文.2024-沉溺【StreetVoice】【FLAC分轨】
- 韩红.2005-精丫麒麟童】【WAV+CUE】
- 2D像素风日式美学动作游戏《雨魂》将登陆Xbox Series
- 《龙腾世纪4》评分造假?仅将评测代码给好评媒体!
- 《怪猎荒野》推出蜘蛛恐惧症设定 蜘蛛秒变史莱姆
- 《张韶涵单8CD+无损单曲合集》[WAV/FLAC][6.5G]
- 自然声带《大自然 雨声 白噪音》[320K/MP3][135.32MB]
- 自然声带《大自然 雨声 白噪音》[FLAC/分轨][416.27MB]
- 2024年度计划曝光!《暗黑破坏神:不朽》X《魔兽世界》11月开启联动
- 逆流而上!成都Wolves后发制人韧性十足!——《第五人格》2024秋季赛第四周赛报
- 复归之刻,七烛庆典,狼人杀七周年掌门表演赛活动来袭!
- 炉石传说野兽流最终阵容推荐 酒馆战棋野兽流最终阵容图文一览
- 炉石传说野猪人流最终阵容推荐 酒馆战棋野猪人流最终阵容图文一览