排序算法一--冒泡排序

野性酷女 2022-05-10 13:40 211阅读 0赞

冒泡排序(BubbleSort)

**基本思想：**两个数比较大小，较大的数下沉，较小的数冒起来

**思路：**

比较相邻的元素。如果第一个比第二个大，就交换他们两个。  
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。  
针对所有的元素重复以上的步骤，除了最后一个。  
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

举例说明：要排序数组：int\[\] arr=\{6,3,8,2,9,1\};

第一趟排序：

第一次排序：6和3比较，6大于3，交换位置：  3  6  8  2  9  1

第二次排序：6和8比较，6小于8，不交换位置：3  6  8  2  9  1

第三次排序：8和2比较，8大于2，交换位置：  3  6  2  8  9  1

第四次排序：8和9比较，8小于9，不交换位置：3  6  2  8  9  1

第五次排序：9和1比较：9大于1，交换位置：  3  6  2  8  1  9

第一趟总共进行了5次比较， 排序结果：      3  6  2  8  1  9

\---------------------------------------------------------------------

第二趟排序：

第一次排序：3和6比较，3小于6，不交换位置：3  6  2  8  1  9

第二次排序：6和2比较，6大于2，交换位置：  3  2  6  8  1  9

第三次排序：6和8比较，6大于8，不交换位置：3  2  6  8  1  9

第四次排序：8和1比较，8大于1，交换位置：  3  2  6  1  8  9

第二趟总共进行了4次比较， 排序结果：      3  2  6  1  8  9

\---------------------------------------------------------------------

第三趟排序：

第一次排序：3和2比较，3大于2，交换位置：  2  3  6  1  8  9

第二次排序：3和6比较，3小于6，不交换位置：2  3  6  1  8  9

第三次排序：6和1比较，6大于1，交换位置：  2  3  1  6  8  9

第二趟总共进行了3次比较， 排序结果：         2  3  1  6  8  9

\---------------------------------------------------------------------

第四趟排序：

第一次排序：2和3比较，2小于3，不交换位置：2  3  1  6  8  9

第二次排序：3和1比较，3大于1，交换位置：  2  1  3  6  8  9

第二趟总共进行了2次比较， 排序结果：        2  1  3  6  8  9

\---------------------------------------------------------------------

第五趟排序：

第一次排序：2和1比较，2大于1，交换位置：  1  2  3  6  8  9

第二趟总共进行了1次比较， 排序结果：  1  2  3  6  8  9

\---------------------------------------------------------------------

最终结果：1  2  3  6  8  9

**平均时间复杂度：**O(n2)

**代码实现(java)：**

public static void BubbleSort(int [] arr){
    
         int temp;//临时变量
         for(int i=0; i<arr.length-1; i++){   //表示趟数，一共arr.length-1次
             for(int j=arr.length-1; j>i; j--){
    
                 if(arr[j] < arr[j-1]){
                     temp = arr[j];
                     arr[j] = arr[j-1];
                     arr[j-1] = temp;
                 }
             }
         }
     }

**优化：**

*  **针对问题：**  
    数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。
 *  **方案：**  
    设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。  
    这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。

public static void BubbleSort1(int [] arr){
    
       int temp;//临时变量
       boolean flag;//是否交换的标志
       for(int i=0; i<arr.length-1; i++){   //表示趟数，一共arr.length-1次。
    
           flag = false;
           for(int j=arr.length-1; j>i; j--){
    
               if(arr[j] < arr[j-1]){
                   temp = arr[j];
                   arr[j] = arr[j-1];
                   arr[j-1] = temp;
                   flag = true;
               }
           }
           if(!flag) break;
       }
    }