BubbleSort
先说说这个最慢的排序吧,很好理解,从字面上来看排序的方式就像冒泡一样,所以是最慢的
解:
(1)比较相邻的两个元素,如果前面的比后面的大就交换位置
(2)那么第一轮下来,最后一个就是最大的
(3)再按照第一步,这时候就不用比较上最后一个了,所以要每次减掉最后一个最大的值再进行下一轮比较
好了,聪明的你已经知道怎么写了
1.定义一个方法,需要传入数组比较吧
function BubbleSort(arr){}
2.遍历数组,因为每次最后一个都是最大的,所以要length-1,还要拿出相邻元素比较,所以再遍历一遍取出相邻元素
function BubbleSort(arr){
for(var i=0;i<arr.length-1;i++){
for(var j=0;j<arr.length-i-1;j++){
}
}
}
3.现在就判断一下,如果前面比后面大,就交换位置
function BubbleSort(arr){
for(var i=0;i<arr.length-1;i++){
for(var j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
var swap=arr[j];
arr[j]=arr[j+1];//后移
arr[j+1]=swap;//前后交换了
}
}
}
};
完工!下面我们再看一个do-while的写法
function BubbleSort(arr){
var swap;
do{
swap=false;
for(var i=0;i<arr.length-1;i++){
if(arr[i]>arr[i+1]){
var temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
swap=true;
}
}
}while(swap);
};
这样写经过测试,效率稍微高了一点点.可谓能优化则优化
第一种写法经测试平均运行时间是:0.03966ms
第二种写法经测试平均运行时间是:0.04166ms
刚刚想起了时间复杂度,空间复杂度,后面补上!
