冒泡排序（Bubble Sort）是最简单的一个排序算法，它具有两个优点：
1.逻辑简单，很容易写出代码；
2.具有稳定性。

冒泡排序算法的思想是将无序表中的所有记录，通过两两比较关键字，得出升序序列或者降序序列。它重复地访问要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。访问数列的工作是重复地进行直到没有再需要交换的位置，也就是说该数列已经排序完成。
冒泡排序和选择排序有异曲同工之妙，可以把冒泡排序理解为另外一种选择排序，选择前面元素中的最大值，放到未排序位置的末尾；而选择排序则是选择未排序位置的最小值，放到未排序的头部。即一个是从后向前排，一个是从前向后排。

1 算法步骤

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

2 排序示例

对无序表 {65 ,5 ,10, 30, 75, 70 } 进行排序，通过一次次循环，将数组中最大的值向后传递，最后到未排序部分的尾部。
如下图，第一次循环的时候，从首部开始，一个一个数据比较下去，直到将整个数组中最大值75放在了最后的位置。然后第二次循环的时候，再从首部开始，一个一个数据比较下去，直到找到最大数据70并放在75的前一位置为止。然后依此循环下去，直到最终排序结束。
image.png
通过一趟趟的比较，一个个的“最大值”被找到并移动到相应位置，直到检测到表中数据已经有序，或者比较次数等同于表中含有记录的个数，排序结束。

3 时间复杂度

无序数组长度为n
在第一次循环的时候，它需要进行n-1次比较
在第二次循环的时候，它需要进行n-2次比较
…
在最后一次循环的时候，它需要进行1次比较
所以总共比较次数为 1+2+…+n-2+n-1 = （（1+n-1）/2）（n-1）=(1/2)n2-(1/2)n
所以其时间复杂度为O(n2)

3 排序代码Java实现

  1. public class BubbleSort {
  3.     public int[] bubbleSort(int[] nums){
  4.         // 数组不能为null，为null则抛出异常
  5.         if(null == arrays){
  6.             throw new NullPointerException("arrays is null");
  7.         }
  8.         // 如果数组长度为0，则返回该空数组
  9.         if(!(arrays.length>0)){
  10.             return arrays;
  11.         }
  12.         return sort(nums);
  13.     }
  15.     public int[] sort(int[] nums){
  16.         int size = nums.length;
  18.         for(int i = size-1;i>=0;i--){
  19.              // 建立一个标志 flag
  20.             // 用于记录在此次循环中是否发生了数据交换
  21.             boolean flag = true;
  22.             for(int j = 1;j<=i;j++){
  23.                 if(nums[j]<nums[j-1]){
  24.                     int temp = nums[j];
  25.                     nums[j] = nums[j-1];
  26.                     nums[j-1] = temp;
  27.                     flag = false;
  28.                 }
  29.             }
  30.             //如果发生了交换，flag为false，则不会beak
  31.             //如果没有发生交换，flag为true，则break
  32.              if (flag) {
  33.                     break;
  34.                 }
  35.         }
  36.         return nums;
  37.     }
  38.     public void println(int [] a) {
  39.         for(int x:a) {
  40.             System.out.print(" "+x);
  41.         }
  42.         System.out.println("");
  43.     }
  45.     public static void main(String[] args) {
  46.         BubbleSort bubbleSort = new BubbleSort();
  47.         int[] nums = {5,3,4,6,7,1,2,8,4,10};
  48.         bubbleSort.println(bubbleSort.bubbleSort(nums));
  49.     }
  51. }