算法（冒泡排序）

冒泡排序

冒泡排序是我们在做排序时很容易使用到的一种排序方法，简单的冒泡排序是这样的

//从大向小进行排序，即从后向前进行排序
    static void SimpleBubbleSort(int arr[]) {
        int temp = 0;
        //外部从0--length-1，内部从0到length-1-i,因为内部的比较是比较arr[j]与arr[j+1]的大小
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
           

这样虽然写起来简单，但是会有很多的无效消耗，假设一个数组为[9，2，3，8]，当第一次排序结束后数组已经有序，那么后面的几次排序都是无效消耗，那么我们可不可以检查数组是否已经有序，如果已经有序就结束排序，这就是下面的写法

static void bubbleSortOptimize1(int arr[]) {
        int temp = 0;
        boolean flag = false;//用来标记此趟排序是否有位置交换
        //外部从0--length-1，内部从0到length-1-i,因为内部的比较是比较arr[j]与arr[j+1]的大小
        for (int i = 0; i < arr.length - 1; i++) {
            flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }
           

上面的写法可以判断数组是否有序，如果有序的话就结束循环。这种写法仅仅适用与片段有序整体无需的情况，但是对于前面大部分无须，后面小部分有序的情况并没有显著提高，对于这种情况我们可以采用记录最后的交换位置进行优化。即记录最后的进行位置交换的位置，下一次循环只循环到记录的位置就可以结束。写法如下：

static void bubbleSortOptimize12(int arr[]) {
        int temp = 0;
        boolean flag = false;//用来标记此趟排序是否有位置交换
        int lastPosition = arr.length - 1;
        int tempPos = 0;
        //外部从0--length-1，内部从0到length-1-i,因为内部的比较是比较arr[j]与arr[j+1]的大小
        for (int i = 0; i < arr.length - 1; i++) {
            flag = false;
            for (int j = 0; j < lastPosition; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                    tempPos = j;
                }
            }
            if (!flag) {
                break;
            }
            lastPosition = tempPos;//如果排序没有结束将最后交换的位置设给lastPosition
        }
    }
           

上面的写法已经可以提高很大的效率。还有一种很流行的写法，双向冒泡排序。双向冒泡排序的思想主要就是在一次循环中从前向后排序一次再从后向前排序一次，这样可以对于类似[0,2,1,3,5,8,9,4]的数组排序更为有利，而且可以兼容利于从前排序和利于从后排序的两种数组，利于从前排序的数组类似[0,2,1,3,4,5]，利于从后排序的数组[0,2,3,4,5,1]。

static void bubbleSortOptimize13(int arr[]) {
        int temp = 0;
        boolean flag = false;//用来标记此趟排序是否有位置交换
        int lastPosition = arr.length - 1;//正向
        int firstPosition = 0;//正向
        int tempPos = 0;
        //外部从0--length-1，内部从0到length-1-i,因为内部的比较是比较arr[j]与arr[j+1]的大小
        for (int i = 0; i < arr.length - 1; i++) {
            flag = false;
            for (int j = 0; j < lastPosition; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                    tempPos = j;
                }
            }
            lastPosition = tempPos;//如果排序没有结束将最后交换的位置设给lastPosition
            tempPos = 0;
            if (!flag || firstPosition >= lastPosition) {
                break;
            }
            flag = false;
            for (int j = lastPosition; j > firstPosition; j--) {
                if (arr[j - 1] > arr[j]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    flag = true;
                    tempPos = j;
                }
            }
            firstPosition = tempPos;
            if (!flag || firstPosition >= lastPosition) {
                break;
            }
        }
    }
           

总结：

在数组特别小的时候，双向排序并不一定比优化过后的第三种排序效率更高，但是在数组比较大的时候都要比第三种效率更高，这个界限我测着是50,。