冒泡排序只会操作相邻的数据，每次冒泡都会对相邻的两个数据做比较，看是否满足大小关系，若不满足，则交换
冒泡排序，每一次冒泡，会移动一个元素到它应该在的位置。整个排序完成需要n次冒泡才能完成

一次冒泡的过程如下：

如下图所示，第一次冒泡。将最后一个元素位置放上了最大的元素。完成一次冒泡

image.png

JAVA对冒泡排序的实现

  1. public class BubbleSort {
  3.     @Test
  4.     public void bubbleSortTest(){
  5.         int[] arrays = {1,8,4,3,7,9,2};
  6.         bubbleSort(arrays);
  7.         for(int i : arrays) {
  8.             System.out.print(i+",");
  9.         }
  10.     }
  12.     /**
  13.      * 冒泡排序
  14.      * @param arrays  需要排序的整形数组
  15.      */
  16.     public void bubbleSort(int[] arrays){
  17.         int length = arrays.length;
  18.         //循环每一次冒泡
  19.         for(int i = 0 ; i < length ; i++){
  20.             //是否冒泡结束的标志
  21.             boolean flag = false;
  22.             //只循环没有冒泡的元素就可以，所有length-i
  23.             for(int j = 0 ; j < length - i -1 ; j++){
  24.                 //满足大小关系，则交换位置
  25.                 if(arrays[j] > arrays[j+1]){
  26.                     int temp = arrays[j+1];
  27.                     arrays[j+1] = arrays[j];
  28.                     arrays[j] = temp;
  29.                     flag = true;
  30.                 }
  31.             }
  32.             if(!flag){
  33.                 break;
  34.             }
  35.         }
  36.     }
  37. }

执行结果：

  1. 1,2,3,4,7,8,9

算法性能分析

稳定性：由于当两个元素的不满足大小关系时，不交换位置，所以当两个元素值相同时，冒泡排序不会改变原有的顺序，即保证了稳定性。

时间复杂度：O(n*n)

空间复杂度：O(1)