javascript实现冒泡排序算法

热网热热 5评论
冒泡排序是编程算法中很经典也是比较简单的一种排序算法。冒泡排序属于交换排序算法中的一种。下面我们就是用js来实现一下冒泡排序算法,个人拙见请勿见笑。

冒泡排序的基本思想

冒泡排序顾名思义,就是待排序元素当做气泡一样,轻的气泡逐渐网上冒,重的气泡下沉。通过比较相邻两个元素的大小,来实现元素的上浮或者下沉。这里的每一次比较只针对两个元素,而上浮和下沉也只是这两个元素的位置交换。日A[n]与A[n-1]两个元素比较,若A[n]小于A[n-1],则A[n]与A[n-1]交换位置,表现为两个元素的上浮和下沉。

冒泡排序算法的实现

很明显我们需要通过循环的方式来比较元素的大小,一次循环可以比较两个元素的大小,第一次循环只可以实现最轻的气泡上浮,显然一层不能解决我们的实际问题,所以我们需要两层循环,才能完成对整个待排序数组的冒泡排序。
原因也很简单,A层循环完成最轻气泡上浮,B层循环重置A层循环初始条件,A循环完成一次之后,最轻气泡已经上浮, 所以我们需要再来一次A循环,并且待排序数组中少了一个需要排序的元素,所以我们需要B层循环。
冒泡排序
下面直接上js代码
var a = [11,1,5,8,5.2,9,66,12,441,21,4];
for(var i = 0; i < a.length; i++){
for(var n = a.length - 1; n >= i + 1; n--){
if(a[n] < a[n-1]){
var temporary = a[n-1];
a[n-1] = a[n];
a[n] = temporary;
}
}
}
console.log(a)//[1, 4, 5, 5.2, 8, 9, 11, 12, 21, 66, 441]
如代码所示,最外层的就是B循环,最里层的就是A循环。
外层循环是控制循环排序的趟次,里面的循环外层最新元素排到最前面。

算法性能分析

算法的最好时间复杂度
若待排序记录为有序(最好情况),则一趟扫描完成,关键比较次数为n-1次且没有移动,比较的时间复杂度为O(n)。
算法的最坏时间复杂度
若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。总的比较次数为:(n-1)+(n-2)+…+1= n(n-1)/2;总的移动次数为3n(n-1)/2。在平均情况下,比较和移动记录的总次数大约为最坏情况下的一半,所以,冒泡排序算法的时间复杂度为O(n2)。
算法的空间复杂度
冒泡排序的空间复杂度为O(1),是就地排序
算法稳定性
冒泡排序是稳定的。

转载请注明觅施南网,javascript实现冒泡排序算法:https://www.rewonng.com/qianduanzhishi/154.html

查看剩余内容

相关内容推荐

猜你喜欢内容