今天開始復(fù)習(xí)一下排序，其實(shí)這個(gè)最近都有再撿起來(lái)練，畢竟太久遠(yuǎn)拿起來(lái)還挺不容易的。
簡(jiǎn)單說(shuō)一下——自己復(fù)習(xí)排序的時(shí)候理解是這樣的：基本的排序分為三類：交換排序、選擇排序、插入排序。用一張圖表示一下：

基本的排序

不得不說(shuō)，我畫的圖簡(jiǎn)直太丑了......
將就看一下吧，大概是這樣的。前面的話有點(diǎn)多了，直接進(jìn)入今天的正題——交換排序。

冒泡排序：BubbleSort

冒泡排序應(yīng)該是最簡(jiǎn)單的了吧？額，至少我個(gè)人覺得應(yīng)該是最好理解的一種排序。
百度百科的原理：

1.比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2.對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3.針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4.持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

說(shuō)起原理來(lái)感覺好難懂是吧？？？
其實(shí)可以簡(jiǎn)單去思考：為啥叫冒泡排序呢？
不知道有沒有注意過水里的氣泡，大的氣泡會(huì)浮到上面去。冒泡排序也是：每一輪的排序,在這一輪中參與比較的元素中最大的數(shù)將會(huì)浮到最后。
時(shí)間復(fù)雜度之類的分析，我寫在了備注中~~~
So,直接上代碼：
請(qǐng)注意第二層for循環(huán)，循環(huán)次數(shù)會(huì)越來(lái)越小，簡(jiǎn)單思考一下就會(huì)發(fā)現(xiàn)：畢竟每輪過后相對(duì)來(lái)說(shuō)最大的數(shù)都會(huì)排到應(yīng)該在的地方去，所以如果再多比較那幾次也沒啥意義~

/**
 * Created by AceCream on 2017/3/19.
 * 冒泡排序BubbleSort（屬于交換排序）
 * 時(shí)間復(fù)雜度： 平均：O(n^2)   最佳：O(n)   最壞：O(n^2)
 * 空間復(fù)雜度： O(1)
 * 穩(wěn)定性： 穩(wěn)定
 */
public class BubbleSort {

    public static void bubbleSort(int[] values){
        for (int i=0;i<values.length;i++){
            for (int j=i;j<values.length;j++){
                if (values[i]>values[j]){
                    int temp = values[i];
                    values[i] = values[j];
                    values[j] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int value[] = {1,7,5,8,3};
        bubbleSort(value);
        for (int result : value) {
            System.out.print(result+" ");
        }

    }
}

快速排序：Quicksort

為啥叫快速排序？因?yàn)樗葎e的排序快啊！當(dāng)然這是一般情況下，也就是平均情況下，快速排序的時(shí)間復(fù)雜度是O(nlogn)，這速度真的不要太快！
?。?！但是?。。?br> “快速排序是最快的排序”，這句話是正確的嗎？？？
答案是：“不準(zhǔn)確！”
因?yàn)榘凑掌骄俣葋?lái)說(shuō)，它確實(shí)很快，但是如果“樞紐元”為最大或者最小數(shù)字，那這個(gè)時(shí)候簡(jiǎn)直就是災(zāi)難！對(duì)！災(zāi)難！它就直接成為了——冒泡排序（Ps：冒泡：“靠！這個(gè)鍋，我不背！”）
具體這個(gè)“樞紐元”是啥？還是從快速排序的原理說(shuō)起來(lái)：

快排原理

原理：

• 確定一個(gè)基準(zhǔn)值
• 一次循環(huán)：從后往前比較，用基準(zhǔn)值和最后一個(gè)值比較，
• 如果比基準(zhǔn)值小的交換位置，如果沒有繼續(xù)比較下一個(gè)，
• 直到找到第一個(gè)比基準(zhǔn)值小的值才交換。
• 找到這個(gè)值之后，又從前往后開始比較，如果有比基準(zhǔn)值大的，交換位置，
• 如果沒有繼續(xù)比較下一個(gè)，直到找到第一個(gè)比基準(zhǔn)值大的值才交換。
• 直到從前往后的比較索引>從后往前比較的索引，結(jié)束第一次循環(huán)。
• 此時(shí)，對(duì)于基準(zhǔn)值來(lái)說(shuō)，左右兩邊就是有序的了。
• 接著分別比較左右兩邊的序列，重復(fù)上述的循環(huán)。

行了，看了原理，我相信基本上都懵逼了，我當(dāng)初也是被快排折磨是不行，找了大量的文檔，沒看懂。后來(lái)自己每一步都在紙上寫一遍，終于發(fā)現(xiàn)了其精髓所在！
簡(jiǎn)單來(lái)說(shuō)，快速排序其實(shí)是冒泡排序的加強(qiáng)版！從成熟體化身為完全體！至于究極體，還得在其基礎(chǔ)上繼續(xù)優(yōu)化~~
我們第一次循環(huán)中，確定的這個(gè)“基準(zhǔn)值”，就是上文所述的“樞紐元”。
借用一下百科的圖片：

快速排序

這個(gè)圖挺好，但是“初始”和“一次劃分”中間省略了很多步，我來(lái)補(bǔ)充一下：想象一下挖坑~
1.首先把第一個(gè)值，也就是49作為key值，取出來(lái)存坑里
2.從右邊開始向左邊，依次和key值比較，一旦發(fā)現(xiàn)比它小的了也就是27，就把27挖出來(lái)，填在它曾經(jīng)的坑里(第一個(gè)位置)。這時(shí)候變成了這個(gè)樣子：

27，38，65，97，76，13，27，49

3.那么這時(shí)候，出現(xiàn)了倆27，這第二個(gè)27，人已經(jīng)走了，但是它的坑還在，很尷尬，咋辦？我們繼續(xù)走下一步，從左邊開始比較(注意！就不要從第一個(gè)開始了，已經(jīng)比較完了，就從38開始吧)，比較誰(shuí)？還是依次與key(49)比較，直到發(fā)現(xiàn)比key大的數(shù)，也就是65，這時(shí)候就把65，放到剛剛那個(gè)尷尬的坑里，把“坑里的值”更新掉~于是變成了這樣：

27，38，65，97，76，13，65，49

然后把最開始挖出來(lái)的那個(gè)49填坑里

27，38，49，97，76，13，65，49

但是這樣就結(jié)束第一此劃分了嗎？并沒有，因?yàn)閺膕tart開始的left值和end開始的right值，還沒有碰到一起(left<right),所以繼續(xù)走，重復(fù)剛才的動(dòng)作，直到他們相遇，這個(gè)時(shí)候：49左邊的數(shù)都小于49，右邊的數(shù)都大于或等于49。也就完成了第一次劃分。
這之后我們看一下上面的圖，以49為中心，分成了兩個(gè)部分，這里就體現(xiàn)了“分治”的思想。將一個(gè)問題，分解成兩個(gè)小的部分，分別做相同的操作。將兩個(gè)部分做同樣的操作，你想到了什么方式？對(duì)！遞歸！快速排序，體現(xiàn)了算法的兩大思想：遞歸和分治。所以快速排序才這么重要。
這里多說(shuō)一句，前面說(shuō)過如果這個(gè)"樞紐元"選的不好，那就很尷尬了，比如說(shuō)，這組數(shù)，我第一個(gè)值如果不是49而是13呢？那第一次劃分后，13放在了最左邊，我們?cè)倏吹诙€(gè)值，如果第二個(gè)值是27呢？以此類推，如果我的這串?dāng)?shù)字剛開始就比較有序，那么快排反而成為了冒泡??！時(shí)間復(fù)雜度變?yōu)榱薔(n^2)，所以說(shuō)，快速排序并不穩(wěn)定。
但是！我們不能因?yàn)檫@個(gè)就否定它，畢竟在大量的測(cè)試中，快速排序的速度是要優(yōu)與堆排序和shell排序的。

是不是聽起來(lái)很暈。自己動(dòng)手（請(qǐng)?jiān)诩埳希懸槐榱鞒唐鋵?shí)就懂得了~~

接下來(lái)，直接手敲代碼：

/**
 * Created by AceCream on 2017/3/19.
 * 快速排序QuickSort （屬于交換排序）
 * 原理：
 * 一次循環(huán)：從后往前比較，用基準(zhǔn)值和最后一個(gè)值比較，
 * 如果比基準(zhǔn)值小的交換位置，如果沒有繼續(xù)比較下一個(gè)，
 * 直到找到第一個(gè)比基準(zhǔn)值小的值才交換。
 * 找到這個(gè)值之后，又從前往后開始比較，如果有比基準(zhǔn)值大的，交換位置，
 * 如果沒有繼續(xù)比較下一個(gè)，直到找到第一個(gè)比基準(zhǔn)值大的值才交換。
 * 直到從前往后的比較索引>從后往前比較的索引，結(jié)束第一次循環(huán)。
 * 此時(shí)，對(duì)于基準(zhǔn)值來(lái)說(shuō)，左右兩邊就是有序的了。
 * 接著分別比較左右兩邊的序列，重復(fù)上述的循環(huán)。
 *
 * 時(shí)間復(fù)雜度： 平均：O(nlog2n)   最佳：O(nlog2n)   最壞：O(n^2)
 * 空間復(fù)雜度： O(1)
 * 穩(wěn)定性： 不穩(wěn)定
 *
 */
public class QuickSort {

    private static void quickSort(int[] value, int start, int end) {
        int left = start;
        int right = end;
        int key = value[start];
        while (left<right){
            while (left<right&&value[right]>=key){
                right--;
            }
            if (left<right){
                value[left] = value[right];
                left++;
            }

            while (left<right&&value[left]<key){
                left++;
            }
            if (left<right){
                value[right] = value[left];
                right--;
            }

            value[left] = key;

            if (left>start) quickSort(value,start,left-1);
            if (right<end) quickSort(value,right+1,end);
        }
    }

    public static void main(String[] args) {
        int[] value = {49,38,65,97,76,13,27,49};
        int start = 0;
        int end = value.length-1;
        quickSort(value,start,end);

        //打印出來(lái)
        for (int result : value) {
            System.out.print(result+" ");
        }
    }
}