冒泡排序

最近重新学习算法, 发现这东西真的得时常复习, 或者一次彻底整会, 我选择后者

定义

冒泡排序(Bubble Sort) 是一种交换排序, 它的基本思想是: 两两比较相邻记录的关键字, 如果反序则交换, 知道没有反序的记录为止.

原理

冒泡法其实原理核心就是两两比较, 每一轮比较就得到一个极值.

两个数比较需要一次

三个数比较需要两次

得出: N 个数比较需要 N-1 次(这是外循环)

又因为每次比较都会增长有序序列, 所以吧, 每次比较次数会变少一次, 每次比较次数取决于有序序列的长度. 第 i 趟的排序次数为$(N-i)$次. (这是内循环)

所以可以用嵌套循环, 外层控制循环次数, 内层控制每一次循环的比较次数

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

时间复杂度

最好的情况, 只用走一次, 所以为$O(n)$

最坏的情况, 需要$n-1$次排序,每次$n-i$次比较, 每次比较移动三次, 不算移动开销的话

需要比较$1+2+3+…+(n-1)=\frac{n(n-1)}{2}$ 次.

计算移动开销就是$\frac{3n(n-1)}{2}$ 次

所以总的时间复杂度就是$O(n^2)$

代码

1. 基本实现

   /**
    * 冒泡排序的第一种实现, 没有任何优化
    * @param a
    */
   public static void bubbleSort1(int [] a){
       int i, j;
   
       for(i=0; i<n; i++){//表示n次排序过程。
           for(j=1; j<n-i; j++){
               if(a[j-1] > a[j]){//前面的数字大于后面的数字就交换
                   //交换a[j-1]和a[j]
                   int temp;
                   temp = a[j-1];
                   a[j-1] = a[j];
                   a[j]=temp;
               }
           }
       }
   }

2. 进一步优化

   因为如果数组部分有序, 其实每次比较都不需要再排序了. 所以设置一个 flag, 如果这一趟发生交换, 则为 true, 否则为 false.

   如果有一趟没有发生交换,则排序已经完成.

   public class BubbleSort implements IArraySort {
   
       @Override
       public int[] sort(int[] sourceArray) throws Exception {
           // 对 arr 进行拷贝，不改变参数内容
           int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
   
           for (int i = 1; i < arr.length; i++) {
               // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
               boolean flag = true;
   
               for (int j = 0; j < arr.length - i; j++) {
                   if (arr[j] > arr[j + 1]) {
                       int tmp = arr[j];
                       arr[j] = arr[j + 1];
                       arr[j + 1] = tmp;
   
                       flag = false;
                   }
               }
   
               if (flag) {
                   break;
               }
           }
           return arr;
       }
   }