冒泡排序(BubbleSort)

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

刚刚想起了时间复杂度,空间复杂度,后面补上!