Java最简洁数据结构之冒泡排序快速理解

一、什么是冒泡排序

冒泡排序的英文是bubble sort，它是一种基础的交换排序。说到冒泡是不是就想起了快乐肥宅水呢？汽水中有许多小小的水泡哗啦哗啦的浮到上面来。这是因为组成小气泡的二氧化碳比水轻，所以小气泡可以一点一点地向上浮动。

而冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身的大小，一点一点的向着数组的一侧移动。

二、图解冒泡排序

我们先看一个例子，有七个数字组成一个无序数列{5，6，3，4，1，7}，对他进行冒泡排序。

按照冒泡排序的思想：把相邻的两个数字两两比较，当一个数字大于右侧相邻的数字时，交换他们的位置，当一个数字和他右侧的数字小于或等于的时候，不交换。

这样，作为数列中的最大的数字7就交换到了最右侧。这时第一轮冒泡结束。（有效区域只有最后一个）

根据第一轮的交换细节，第二轮到第六轮的状态为下图。

到此为止，所有的数字都是有序的了，冒泡排序是一种稳定排序，由于该排序算法的每一轮都要遍历所有的数字，一共要遍历n-1，所以时间复杂度为O(n^2)。

那么我们如何区分排序算法是否稳定呢？

如果我们交换的时候，遇到两个相同的数字，如果两个相同的数字在排序之后相对位置没有交换，那么就是稳定的排序，反之则是不稳定的排序。

三、代码实现

   public static void bubbleSort(int arr[]){
       for (int i = 0; i < arr.length-1; i++) {
           for (int j = 0; j <arr.length-i-1 ; j++) {
               int tmp=0;
               if(arr[j]>arr[j+1]){
                   tmp=arr[j+1];
                   arr[j+1]=arr[j];
                   arr[j]=tmp;
               }
           }
       }
   }

public static void main(String[] args) {
       int[] arr = new int[]{5,6,3,2,4,1,7};
       bubbleSort(arr);
       System.out.println(Arrays.toString(arr));
   }

四、代码的优化

1、整体的思路

从上面的例子不难看出，我们可以对原来的冒泡排序进行优化。我们仍然用上面呢个数列{5，6，3，4，1，7}为例子，从上面的图解可以看出在第五轮排序后，整个数列已经是有序的，但是排序算法还是执行了第六轮排序。

优化的思路是：如果能判断出数列已经是有序的了，并且做出标记，那么就不会执行多余的排序。

所以我们可以用布尔变量isSorted作为标记，如果在本轮排序中有元素进行交换，则说明数列无序；如果在本轮排序中，没有元素进行交换，我们则认为此时数列已经为有序的，不需要再去进行下一轮的排序。

2、代码示例

   public static void bubbleSort(int arr[]){
       for (int i = 0; i < arr.length-1; i++) {
           //有序标记，每一轮的初始值都是true
           boolean isSorted=true;
           for (int j = 0; j < arr.length-i-1; j++) {
               int tmp=0;
               if (arr[j]>arr[j+1]){
                   tmp=arr[j];
                   arr[j]=arr[j+1];
                   arr[j+1]=tmp;
                   //因为有元素进行交换，所以不是有序的，标记变为false
                   isSorted=false;
               }
           }
           if (isSorted){
               break;
           }
       }
   }
   public static void main(String[] args) {
       int[] arr = new int[]{5,6,3,2,4,1,7};
       bubbleSort(arr);
       System.out.println(Arrays.toString(arr));
   }

来源：https://blog.csdn.net/AXiYa_Ari/article/details/121295558