冒泡排序

冒泡排序法

重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复进行的，直到没有再需要交换的，数列就会排序完成。
** 冒泡排序总和的平均时间复杂度为O(n^2)。冒泡排序是一种稳定的排序算法。**

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

private void bubbleSort(int [] array) {
        for (int j = 0; j < array.length - 1; j++) {
            for (int i = 0;i < array.length -1 -j ;i++) {
                int first = array[i];
                int second = array[1+i];
                if (first > second) {
                    array[i] = second;
                    array[i+1] = first;
                }
            }
        }
    }

优化冒泡排序

如果想优化排序时间，可以提高比较的个数，例如2个改到3个。这样就是减少循环，减少时间复杂度。

private void quickBubbleSort(int [] array) {
        for (int j = 0;j < array.length - 1;j=j+2) {
            for (int i = 1; i < array.length -1 -j; i++) {
                int before = array[i - 1];
                int me = array[i];
                int after = array[i + 1];
                int max = after;
                int index = 2;
                if (max < me) {
                    max = me;
                    index = 1;
                }
                if (max < before) {
                    max = before;
                    index = 0;
                }
                array[i + 1] = max;
                switch(index) {
                    case 0:
                        if (me > after) {
                            array[i -1] = after;
                        } else {
                            array[i - 1] = me;
                            array[i] = after;
                        }
                        break;
                    case 1:
                        if (before < after) {
                            array[i - 1] = before;
                            array[i] = after;
                        } else {
                            array[i - 1] = after;
                            array[i] = before;
                        }
                        break;
                    case 2:
                        if (before > me) {
                            array[i -1] = me;
                            array[i] = before;
                        }
                        break;
                }
            }
        }
    }