数据结构学习笔记之冒泡排序

冒泡排序是一种稳定排序，因为比较和交换发生在两个相邻元素之间，通过相邻元素的比较，如果不是顺序排列则交换位置，是则从下一个元素开始。

image.png

这就是一轮排序代码很容易理解

import java.util.Arrays;

public class BubbleSort {
    public static void main (String[] args) {
        int arr[] = {3, 15, 151, 181, 81, 2, 8, 1};

        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1 - j; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i + 1];
                    arr[i + 1] = arr[i];
                    arr[i] = temp;
                    flag = true;
                }
            }
            if (flag==false)
                break;
            else
                flag=false;
        }
        System.out.println (Arrays.toString (arr));
    }
}

如果经过比较未进入交换则flag为false，即顺序排列跳出循环。
这就能基本上完成冒泡排序但是会遇到这种情况：
例如有一串数组{2，3，4，5，6，7，1}
前面都是排好的顺序但唯独最后一个是最小的，这样还是会一步一步的替换比较。
对此我们进行优化，将单向冒泡改为双向冒泡。
代码如下：

        long start=System.currentTimeMillis ();
        boolean flag = false;
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = j; i < arr.length - 1 - j; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i + 1];
                    arr[i + 1] = arr[i];
                    arr[i] = temp;
                    flag = true;
                }
            }
            if (flag==false)
                break;
            else
                flag=true;

            for (int i= arr.length-1-j; i>0;i--){
                if (arr[i-1] > arr[i]) {
                    int temp = arr[i];
                    arr[i] = arr[i-1];
                    arr[i-1] = temp;
                    flag = true;
                }
            }
                if (flag==false)
                    break;
                else
                    flag=true;
        }