冒泡排序算法拆分讲解及优化

<a href="#java_8">java冒泡排序</a> <a href="#_13">一、代码的拆分讲解</a>

  <a href="#j1forj_80">从上面步骤，可以观察到每次的j都相对于前一趟进行-1操作，所以可以把这些操作套在一个for循环里来控制j即可。</a>            <a href="#_82">二、冒泡排序的代码</a>   


 
  <a href="#_111">优化的目的：数组有可能在中间某一过程就已经有序，无序再进行后面操作。</a>            

<hr color="#000000" size="1"">

java冒泡排序

以3,9,-1,10,-2这组数为例，对这组数使用冒牌排序使其有序

一、代码的拆分讲解

首先创建一个数组和一个用于三角交换的变量

int arr[] = {3,9,-1,10,-2};
int temp = 0;

首先进行第一趟

 //第一趟排序，就是将最大的数排在最后
      for (int j = 0; j < arr.length - 1; j++) {
         if (arr[j] > arr[j+1]){
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
         }
      }

<font color="#999AAA">第一趟的运行后的数组 </font>

然后第二趟

 //第一趟排序，就是将最大的数排在最后
      for (int j = 0; j < arr.length - 1-1; j++) {
         if (arr[j] > arr[j+1]){
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
         }
      }

第二趟的运行后的数组

第三趟

 //第一趟排序，就是将最大的数排在最后
      for (int j = 0; j < arr.length - 1 -2; j++) {
         if (arr[j] > arr[j+1]){
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
         }
      }

第三趟的运行后的数组

第四趟

 //第一趟排序，就是将最大的数排在最后
      for (int j = 0; j < arr.length - 1 -3; j++) {
         if (arr[j] > arr[j+1]){
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
         }
      }

第四趟的运行后的数组

下面是四趟代码的结果汇总：

从上面步骤，可以观察到每次的j都相对于前一趟进行-1操作，所以可以把这些操作套在一个for循环里来控制j即可。

二、冒泡排序的代码

下面为冒泡排序的代码，并把它写入bubblesSort方法里：

<font color="#999AAA">普通冒泡排序：</font>

   public static void bubbleSort(int[] arr){
      //冒泡排序的时间复杂度为O(n*n)
      int temp = 0;//临时变量
      for (int j = 0; j < arr.length - 1; j++) {

         for (int i = 0; i < arr.length-1 -j ; i++) {
            if (arr[i] > arr[i+1]){
               //三角交换
               temp = arr[i];
               arr[i] = arr[i+1];
               arr[i+1] = temp;
            }
         }
      }
   }

优化的目的：数组有可能在中间某一过程就已经有序，无序再进行后面操作。

<font color="#999AAA">优化冒泡排序：</font>

public static void bubbleSort(int[] arr){
      //冒泡排序的时间复杂度为O(n*n)
      int temp = 0;//临时变量
      boolean flag = false;//用于优化冒泡排序，判断是否进行过交换
      for (int j = 0; j < arr.length - 1; j++) {

         for (int i = 0; i < arr.length-1 -j ; i++) {
            if (arr[i] > arr[i+1]){
                //三角交换
               temp = arr[i];
               arr[i] = arr[i+1];
               arr[i+1] = temp;
               flag = true;
            }
         }
         //如果没有进入三角交换则证明数组已经有序，直接退出循环即可
         //如果进入了三角交换，把flag赋值为false，来判断下一次循环是否进入三角交换
         if (flag == false){
            break;
         }else {
            flag = false;
         }
      }
   }

原文地址：https://blog.csdn.net/weixin_45499166/article/details/118105847?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168474995516800188548878%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=168474995516800188548878&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-11-118105847-null-null.142^v87^control_2,239^v2^insert_chatgpt&utm_term=java%E4%BC%98%E5%8C%96