交换排序算法--冒泡排序

交换排序有2种，冒泡排序和快速排序

这里先谈冒泡排序，冒泡排序的原理是什么？

大的数往下沉，小的数往上冒。通俗来讲，就是对相邻的2个数做比较，如果前一个数比后一个数大，交换他们的位置，最后达到大的数在后面，小的数在前面的效果；

还是用代码来讲解，写一个函数：

function maopao(arr){

    for(var j = 0;j < arr.length-1;j++){

        for(var i = 0;i < arr.length-1;i++){

            if (arr[i] >arr[i+1]) { //前一个数大于后一个数，交换

                  var tmp = arr[i];

                  arr[i]=arr[i+1];

                  arr[i+1] = tmp; 

            }

        }

    }

    return arr;

}

当然这个是最传统的冒泡排序,这种排序方式的结果是无论对什么数组，都需要进行完整的n * n次for循环。这里有2种改进方式，让他的循环次数少一些。

第一种：我们设置一个变量pos，让它来记录一次循环之后最后交换的位置，而pos后面的数不需要交换了。当pos等于0的时候，说明整个数组已经没有要交换的了。

接下来我们看看代码怎么实现，依然是写一个函数：

function maopao1(arr){

      var n  = arr.length-1; 

     while(n>0){     

          var pos = 0;

          for(var i = 0; i < n; i++){

              if(a[i]>a[i+1]){

                     pos = i; //记录pos,由于for循环会走完，所以pos记录的是此次循环最后的i值

                     var a = arr[i];

                     arr[i] = arr[i+1];

                     arr[i+1]=a;

               }

          }

         n = pos; //下次循环就只到pos了

     }

    return arr;

}

上面是第一种改进方式，接下来说说第二种改进方式。

冒泡排序的一次循环可以排出数组的最大值或最小值，那我们试着用2个循环求出最大值和最小值。然后就不再去管最大值和最小值了，每次循环就少计算2个数。

代码来看，写一个函数：

function maopao2(arr){

     var max = arr.length-1;

     var min = 0;

     if (max>min) {

          for(var i = min; i < max;i++){

              if (arr[i] > arr[i+1]) {

                   var a = arr[i];

                   arr[i] = arr[i+1];

                   arr[i+1]=a;

              }

          }

          max--;

          for(var i = max; i > min;i--){

               if (arr[i] < arr[i-1]) {

                    var a = arr[i];

                    arr[i] = arr[i+1];

                    arr[i+1]=a;

               }

          } 

          min++;

     }

      return arr;

}