冒泡排序细究java

对话、

发布于 2022-02-22 14:03:50

2140

发布于 2022-02-22 14:03:50

文章被收录于专栏：Android-Xj

说起排序大家最熟悉的莫过于冒泡排序了

今天就和大家细究一下冒泡排序

首先看看基础版冒泡排序的实现代码

public  static  void  sort(int array[]){
		//外层循环控制排序的次数
        for (int i = 0; i < array.length; i++) {
        //内层循环控制每一次排序的冒泡处理
            for (int j = 0; j <array.length-i-1 ; j++) {
            //声明一个变量（可以比作一个笔筒）
                int tmp=0;
                //进行前后比较（如果前面的值比后面的值大）
                if (array[j]>array[j+1]){
                //把前面的值先放入笔筒里
                    tmp=array[j];
                    //把后面的值赋值给前面的值
                    array[j]=array[j+1];
                    //把笔筒里存放的前面的值赋值给后面的值
                    array[j+1]=tmp;
                    //到此排序过程就完成了
                }
            }
        }
    }

测试后我们发现这种写法存在一些问题，例如：当我们第array.length-1次排序时，这时的顺序已经排好，我们再排一次就是浪费时间了。所以我们可以进一步优化

/**
     * 优化版冒泡排序：如果判断数列已经有序，并做出标记，那么剩下的几轮排序就不必执行了，可以提前结束工作
     * @param array
     */
   public  static  void  sort(int array[]){
       for (int i = 0; i <array.length-1 ; i++) {
           //有序标记，每一轮的初始值都是true
           boolean isSorted=true;
           for (int j = 0; j < array.length-i-1; j++) {
               int tmp=0;
               if (array[j]>array[j+1]){
                   tmp=array[j];
                   array[j]=array[j+1];
                   array[j+1]=tmp;
                   //因为有元素进行交换，所以不是有序的，标记变为false
                   isSorted=false;
               }
           }
        if (isSorted){
            break;
        }
       }
   }

我们再次测试发现这种写法也存在问题:问题在于我们已经排序好了的元素，在后面的比较中又再次进行了比较，这样就会再次浪费效率。好，让我们进一步优化。

  /**
     * 优化版冒泡排序：每一轮排序后，记录下来最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了
     * @param array
     */
   public  static  void  sort(int array[]){
       //记录最后一次交换的位置
       int lastExchangeIndex=0;
       //无序数列的边界，每次比较只需要比到这里为止
       int sortBorder=array.length-1;
       for (int i = 0; i <array.length-1 ; i++) {
            //有序标记，每一轮的初始值都是true
            boolean isSorted=true;
           for (int j = 0; j <sortBorder ; j++) {
               int tmp=0;
               if (array[j]>array[j+1]){
                   tmp=array[j];
                   array[j]=array[j+1];
                   array[j+1]=tmp;
                   //因为有元素进行交换，所以不是有序的，标记变为false
                   isSorted =false;
                   //更新为最后一次交换元素位置
                   lastExchangeIndex=j;
               }
           }
           sortBorder=lastExchangeIndex;
           if (isSorted){
               break;
           }
       }
   }