冒泡排序法

重復(fù)地走訪要排序的數(shù)列稍坯，一次比較兩個(gè)元素官辽，如果他們的順序錯(cuò)誤就把他們交換過來蛹磺。走訪數(shù)列的工作是重復(fù)進(jìn)行的，直到?jīng)]有再需要交換的同仆，數(shù)列就會(huì)排序完成萤捆。
** 冒泡排序總和的平均時(shí)間復(fù)雜度為O(n^2)。冒泡排序是一種穩(wěn)定的排序算法俗批。**

• 比較相鄰的元素俗或，如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)岁忘。
• 對(duì)每一對(duì)相鄰元素做同樣的工作辛慰，從開始第一個(gè)到結(jié)尾的最后一對(duì)。在這一點(diǎn)干像，最后的元素應(yīng)該會(huì)是最大的帅腌。
• 針對(duì)所有元素重復(fù)以上的步驟，除了最后一個(gè)麻汰。
• 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟速客，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

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;
                }
            }
        }
    }

優(yōu)化冒泡排序

如果想優(yōu)化排序時(shí)間五鲫，可以提高比較的個(gè)數(shù)溺职，例如2個(gè)改到3個(gè)。這樣就是減少循環(huán)位喂，減少時(shí)間復(fù)雜度浪耘。

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;
                }
            }
        }
    }