排序算法之冒泡排序

排序算法之冒泡排序

冒泡排序原理：比较两个相邻的元素，将大的值交换到右边（降序则相反）

实现步骤：比较相邻的两个元素，如果第一个比第二大就交换他们的位置

依次类推，完成后最后的元素将是最大的一个元素。持续上面的步骤直到

没有需要比较的元素

实现代码：

  public public static void main(String[] args){
          int arr[]=new int []{ 5, 2, 1, 6, 4, 3 };
             Sysotem.out.print("运行结果：");
          for(int i:arr){
              Sysotem.out.print(i);
          } 
}
public static int[] bubbleSort(int arr[]){
       if(arr==null||arr.length==0){
            System.out.println("what?");           
                 return null;
         }

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

                if(arr[j]>arr[j+1]){
                       int tmp=arr[j];
                       arr[j]=arr[j+1];
                       arr[j+1]=tmp;
                   }

             }             

      }

                return arr;
}

运行结果：

过程：

待排序的数组{ 5, 2, 1, 6, 4,3 }（升序）

第一次循环：
第一次比较：5和1比较，5>2,交换位置  结果{2,5,1,6,4,3}
第二次比较：5和1比较，5>1,交换位置  结果{2,1,5,6,4,3}
第三次比较：5和6比较，5<6,位置不变  结果{2,1,5,6,4,3}
第四次比较：6和3比较，6>3,交换位置  结果{2,1,5,4,6,3}
第五次比较：6和4比较，6<4,交换位置  结果{2,1,5,4,3,6}

第一次循环结果：{2,1,5,4,3,6}

第二次循环：
第一次比较：2和1比较，2>1,互换位置 结果{1,2,5,4,3,6}
第二次比较：2和5比较，2<5,位置不变 结果{1,2,5,4,3,6}
第三次比较：5和4比较，5>4,交换位置 结果{1,2,4,5,3,6}
第四次比较：5和3比较，5>3,交换位置 结果{1,2,4,3,5,6}

第二次循环结果：{1,2,4,3,5,6}

第三次循环
第一次比较：1和2比较，1<2,位置不变 结果{1,2,4,3,5,6}
第二次比较：2和4比较，2<4,位置不变 结果{1,2,4,3,5,6}
第三次比较：4和3比较，4>3,交换位置 结果{1,2,3,4,5,6}

第三次循环结果：{1,2,3,4,5,6}

第四次循环结果：{1,2,4,3,5,6}
第一次比较：1和2比较，1<2,位置不变 结果{1,2,3,4,5,6}
第二次比较：2和3比较，2<4,位置不变 结果{1,2,3,4,5,6}

第四次循环结果：{1,2,3,4,5,6}

第五次循环结果：{1,2,4,3,5,6}
第一次比较：1和2比较，1<2,位置不变 结果{1,2,3,4,5,6}

第五次循环结果：{1,2,3,4,5,6}

由循环过程发现在第3次的时候已经排好序了，第四次和第五次循
环完全是多余的所以为了减少资源的 浪费需要在不进行交换时让
其结束循环，于是在其循环后加入判断以节省资源

冒泡排序优化版

 public static int[] bubbleSort(int arr[]){ 
    if(arr==null||arr.length==0){
         System.out.println("what?");           
              return null;
      }
    boolean bool=true;
    for(int i=0;i<arr.length-1;i++){
          bool=false;
          for(int j=0;j<arr.length-1-i;j++)
             if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                    bool=true;
                }
          }    
         if(!bool){
               break;//结束循环，达到节省资源的目的
          }         
  }

好了冒泡排序就介绍到这里了。