排序-冒泡

冒泡排序

简介

• 冒泡排序属于一种交换排序，
• 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
• 交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

代码

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{18, 4, 69, 3, 10, 20};
        int condition = arr.length - 1;
        for (int i = 0; i < condition; i++) {
            for (int j = 0; j < condition - i; j++) {   // 为什么是 -i，是因为前面循环了i次，就排好了几个，所以需要-i
                if (arr[j] < arr[j + 1]) {
                    int temp = arr[j + 1];  // 交换的逻辑，创建一个临时变量存储一下 需要调换的数值
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

冒泡排序的时间复杂度：

• 最坏情况
  最坏情况：逆序排顺序。假设有n个数，等差数列1+2+3+4+...+n。因此最坏的时间复杂度为O(n^2)。
• 最好情况
  最好情况：有序排有序。对于冒泡排序来说，即使是有序仍然会把每个数进行冒泡。虽然有序，但是冒泡排序不知道呀，仍然按着老套路一个一个比较冒。因此最好的时间复杂度仍为O(n^2)。

优化思想

• 我们定义一个变量，在冒泡的过程中，如果有两个数字进行交换，说明原序列不是有序的，但是如果冒一遍发现，没有数字记性交换，说明该序列是有序的，就没必要继续冒下去了。因此，我们可以定义一个exchange变量，其实赋值为0，如果冒一遍有交换，就让exchange = 1，如果没有交换，不改变exchange的值，我们最后只需要判断exchange的值即可的值序列是否有序。

• 代码

  public class BubbleSort2 {
      public static void main(String[] args) {
          int[] arr = new int[]{18, 4, 69, 3, 10, 20};
          int condition = arr.length - 1;
          for (int i = 0; i < condition; i++) {
              int exchange = 0;
              for (int j = 0; j < condition - i; j++) {
                  if (arr[j]<arr[j+1]){
                      int temp = arr[j+1];
                      arr[j+1] = arr[j];
                      arr[j] = temp;
                      exchange = 1;
                  }
              }
              if (exchange == 0)
                  break;
          }
  
          for (int i = 0;i<arr.length -1;i++){
              System.out.println(arr[i]+" ");
          }
      }
  }
  

• 优化算法的时间复杂度

  • 最坏情况 -- 最坏情况仍是逆序排顺序 时间复杂度O(n^2)

  • 最好情况 -- 本身就有序，我们在第一遍冒泡过程过，exchange没有改变，我们就break了。

    因此此时的时间复杂度是O(n)。

原文：https://blog.csdn.net/qq_58325487/article/details/124228754