冒泡排序优化版

偏执的太偏执、 2022-10-02 10:41 156阅读 0赞

上一篇我们讲了冒泡排序，它需要重复的走过所有元素，并需要进行比较，直到没有交换的元素，这样导致，在很多情况下效率比较低下。比如【1，2，5，8，9，10，11，14，13】 这样一组元素，第一趟就已经全部排序完成。

优化方案：设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成，从而大大提高效率；

程序代码（Java版）：

public class BuddingSort \{  
    public static void main(String\[\] args) \{  
           
         Integer\[\] arrA=new Integer\[10000\];  
         for(int i=0;i<arrA.length;i++)\{  
            arrA\[i\]=new Random().nextInt(10000)+1;  
         \}  
           
         Long timeABegin = System.currentTimeMillis();  
         sort(arrA);  
         Long timeAEnd = System.currentTimeMillis();  
         System.out.println("优化前花费时间（毫秒）："+(timeAEnd-timeABegin));          
              
         Integer\[\] arrB=new Integer\[10000\];  
         for(int i=0;i<arrB.length;i++)\{  
            arrB\[i\]=new Random().nextInt(10000)+1;  
         \}

Long timeBBegin = System.currentTimeMillis();  
         sort\_optimization(arrB);  
         Long timeBEnd = System.currentTimeMillis();  
         System.out.println("优化前花费时间（毫秒）："+(timeBEnd-timeBBegin));          
              
    \}  
      
    //假如状态，记录当前以前原来  
    public static void sort\_optimization(Integer\[\] array) \{  
          
        for(int i=0;i<array.length-1;i++) \{  
             // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。  
            Boolean status = true;  
              
            for(int j=0;j<array.length-i-1;j++) \{  
                if(array\[j\]>array\[j+1\]) \{  
                    int temp = array\[j\];  
                    array\[j\] = array\[j+1\];  
                    array\[j+1\] = temp;  
                    status = false;  
                \}  
            \}  
              
            if(status) \{  
                break;  
            \}  
        \}  
    \}  
   
    public static void sort(Integer\[\] array) \{  
        for(int i=0;i<array.length-1;i++) \{  
            for(int j=0;j<array.length-i-1;j++) \{  
                if(array\[j\]>array\[j+1\]) \{  
                    int temp = array\[j\];  
                    array\[j\] = array\[j+1\];  
                    array\[j+1\] = temp;  
                \}  
            \}  
        \}  
    \}  
\}

当数据量达到10000时，运行结果如下：

优化前花费时间（毫秒）：345  
           优化前花费时间（毫秒）：338  
特别提醒：就算已经优化的冒泡排序，一旦数据量大的时候，跟其他排序算法相比也是比较耗时的，应根据实际选择其他排序算法；