冒泡排序由于比较简单和容易理解,往往会成为人们首先想到的排序算法。最基本的想法就是在一次里面比较两个数字,并且确保他们在移动到其他项目之前有一个正确的顺序。在每一关结束,有价值的“排序”到正确的位置,最终只留下其他项目排序。
这个过程就是重复数次直到数据完全排序完毕,在每一次循环中,由于每一次的最后一项都是正确的排序,所以排序的项就越来越少。为了更好的理解,我们来进行一个数组对比一下:[3, 2, 4, 5, 1].
实现冒泡排序的第一步就是创建一个方法来交换数组里面的两项,这个方法在很多低效率的排序中是比较常见的。一个简单的javascript实现代码为:
function swap(items, firstIndex, secondIndex){ var temp = items[firstIndex]; items[firstIndex] = items[secondIndex]; items[secondIndex] = temp;}
如上所述,这个排序算法由于需要进行多次的排序,效率是比较低的。假设一个数组有n个项,那么则需要2的n次方来计算,让我们来看看这个
function bubbleSort(items){ var len = items.length, i, j, stop; for (i=0; i < len; i++){ for (j=0, stop=len-i; j < stop; j++){ if (items[j] > items[j+1]){ swap(items, j, j+1); } } } return items;}
外面的循环是控制了循环周期数,里面的循环则是项与项之间的排序比较。
function bubbleSort(items){ var len = items.length, i, j; for (i=len-1; i >= 0; i--){ for (j=len-i; j >= 0; j--){ if (items[j] < items[j-1]){ swap(items, j, j-1); } } } return items;}
上面两个代码的结果是一样的,都是从小到大排序,只是循环的顺序略有不同,都是正序冒泡。
其实就是判断大小改变,第一项小于第二项时,交换位置,依次类推。
function bubbleSort2(items){var len = items.length,i,j,stop;for(i=0;i<len; i++){for(j=0,stop=len-i;j<stop;j++){if(items[j]<items[j+1]){swap(items,j,j+1);}}}return items;}
再次说明一下,冒泡排序可能并不适用于你的实际工作中哦,它只是一个简单的工具帮助我们了解算法并且为进一步获取更多的知识打下基础。而我们用得最多的可能是内置的Array.prototype.sort() 原型方法,这是由于它具有更高效率。
发现研究这些算法也挺有意思的,后面我将继续与大家分享更多的JavaScript算法知识,欢迎朋友们登录留言,与前端博客一起交流这方面的知识。
一起学吧部分文章转载自互联网,供读者交流和学习,若有涉及作者版权等问题请及时与我们联系,以便更正、删除或按规定办理。感谢所有提供资讯的网站,欢迎各类媒体与一起学吧进行文章共享合作。