冒泡排序算法

特点 ：

无论被排的数据特点如何，时间复杂度固定为n^2

空间复杂度为O(1)

思路：

逐个比较相邻两个数 ，若发生逆序，则交换；

有俩种方式进行冒泡，一种是先把小的冒泡到前边去

另一种是把大的元素冒泡到后边。

算法描述

逐个比较相邻两个数 ，若发生逆序，则交换；

有俩种方式进行冒泡，一种是先把小的冒泡到前边去

代码实现：

import java.util.*;

public class BubbleSort {
    public int[] bubbleSort(int[] A, int n) {
       for(int i=0;i<n-1;i++){
           for(int j=0;j<n-i-1;j++){
               if(A[j]>A[j+1]){
                   int temp = A[j+1];
                   A[j+1] = A[j];
                   A[j]=temp;
               }
           }
       }
       return A;
    }
}

稳定性

在相邻元素相等时，它们并不会交换位置，所以，冒泡排序是稳定排序。

适用场景

冒泡排序思路简单，代码也简单，特别适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用。

代码优化

优化：由于每次冒泡都从头到尾亮亮比较完了所有数据， 如果某次冒泡发现没有逆序对，说明当前数列已经是有序的 可以设置个Boolean值来判断这种情况，直接退出所有循环

public static void bubbleSort(int[] arr) {
  int temp = 0;
  boolean swap;
  for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的长度
    swap=false;
    for (int j = 0; j < i; j++) { // 从第一个元素到第i个元素
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swap=true;
      }
    }//loop j
    if (swap==false){
      break;
    }
  }//loop i
}// method bubbleSort