冒泡排序算法优化

72 阅读 0 评论 48 点赞

我是靠谱客的博主繁荣猫咪，最近开发中收集的这篇文章主要介绍冒泡排序算法优化，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

冒泡排序算法的原理如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

如下图对 7 4 9 5 6 8,按照从小到大的顺序排列:

第一轮交互:先比较 7 和 4 , 7 比 4 大, 7 和 4 交换位置, 交换后数字变成如图第二列; 再比较 7和 9;7 比 9 小,不用交换位置,(用圆圈表示不用交换位置),就这样依次比较相邻元素,直到数组中最后两个数字交换位置,第一轮比较完成.

(向下的箭头,标出1,2,3,4,5 分别代表五轮比较) 可以看出当我们每完成一轮比较后会有一个最大的数子沉底,这个最大的位置已经坐实,不需要比较, 因此每比较一轮,相邻元素之间的比较就会减少一次;

<script>
var arr = [7,4,9,5,6,8];
var i = arr.length - 1;//数组中6个元素需要比较5轮,因此是arr.length - 1;
var temp;//临时交换变量
while(i > 0){
for(var j = 0;j < i; j++){
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
i--;
}
for(i = 0;i < arr.length; i++){
document.write(arr[i]+"&nbsp;")
}
</script>

这个算法的最大复杂度 (所有元素全为逆序),需要比较 (n-1)+(n-2)+(n-3)+...+2+1= n^2 / 2; 即；

最小复杂度,则是当数组中所有元素全为正序,则只需要比较一次即可,复杂度即为;

显然上面的算法为最大复杂度.下面我们来讨论如何优化算法;

上面的手绘演示冒泡法的图片中可以看到:到第二轮循环后,实际上已经是正序,只需遍历一边数组,确定位置已经是正序,不需要再进行3,4,5轮比较. 因此可以定义一个变量lastExchangeIndex来记录每次遍历数组最后一次交换的位置;来调整循环的次数即可;

//优化算法
var arr = [7,4,9,5,6,8];
var i = arr.length - 1;
var temp;//临时交换变量
var lastExchangeIndex;//用来记录每次遍历数组,最后一次交换元素的位置
while(i > 0){
lastExchangeIndex = 0;//初始化为0
for(var j = 0;j < i; j++){
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
lastExchangeIndex = j;//每次满足if条件即进行交换,lastExchangeIndex也随之变化,
// 直到内层循环结束,lastExchangeIndex的值为最后一次交换的位置
}
}
i = lastExchangeIndex;//让i = lastExchangeIndex,若 遍历数组后,没有任何元素交换,即数组中的元素都满足
//正序,那么lastExchangeIndex的值仍未初始值0;那么此时传给i的值也为0;i = 0不满足
//while循环条件,循环终止.排序完成!
}
for(i = 0;i < arr.length; i++){
document.write(arr[i]+"&nbsp;")
}