從今天開始翎蹈，更新的文章可能在排版上不那么正規(guī)了荤堪。

ok枢赔，先看看冒泡排序吧拥知。

原理很簡單哈低剔，數(shù)組中兩兩比較襟齿，如果你是從小到大排序，就把大的往后移動位隶。

說白了开皿，兩數(shù)個比較赋荆，如果前一個比后一個大，就交換兩個的位置春宣。

整個代碼兩層for循環(huán)嵌套信认。精華就下面這坨均抽。

   // 不要緊張油挥，這個numbers就是一個整數(shù)數(shù)組，里面裝的數(shù)據(jù)是混亂的攘乒，我們準(zhǔn)備把他排序则酝。
   for(int i = 0; i < numbers.length - 1; i++){            //為啥 length - 1闰集，因為-1次循環(huán)可以排完序了，你多循環(huán)一次沒啥用蝠检。 
            for (int j = 0; j < numbers.length - i -1; j++) {   //為啥length - i - 1挚瘟，-1跟上面一樣乘盖，-i下面講
                if(numbers[j] > numbers[j + 1]) {   //這里也不要緊張，通過異或運算（^）交換**整數(shù)**numbers[j]和**整數(shù)**numbers[j + 1]的值锅尘，不信你試試
                    numbers[j] ^= numbers[j+1];
                    numbers[j+1] ^= numbers[j];
                    numbers[j] ^= numbers[j+1];
                }
            }
        }

理解不了就死背代碼吧。

算法里面有個叫穩(wěn)定性的東西：
穩(wěn)定 ：當(dāng)a > b纵揍，就不會交換兩個數(shù)的位置泽谨。
不穩(wěn)定：當(dāng)a > b, 可能發(fā)生兩個數(shù)交換位置特漩。
所以涂身，冒泡是穩(wěn)定的。

但是在時間方面比較慢丁鹉。我測試10000個打亂的int數(shù)從小到大排序五次揣钦，花費時間分別為： 220ms 202ms 234ms 253ms 227ms

整個測試代碼如下：

public static void main(String[] args) {
        int[] a = new int[10000];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int)(Math.random() * 10000);
        }
        //冒泡排序
        bubbleSort(a.clone());       //由于我測試多種排序使用同一初始數(shù)組冯凹，所以克隆一下炒嘲。
    }

    //冒泡排序
    public static void bubbleSort(int[] numbers) {
        long start = System.currentTimeMillis();    //記錄初始時間
        for(int i = 0; i < numbers.length - 1; i++){
            for (int j = 0; j < numbers.length - i -1; j++) {
                if(numbers[j] > numbers[j + 1]) {
                    numbers[j] ^= numbers[j+1];
                    numbers[j+1] ^= numbers[j];
                    numbers[j] ^= numbers[j+1];
                }
            }
        }
        long end = System.currentTimeMillis();   //記錄結(jié)束時間
        System.out.println(Arrays.toString(numbers));
        System.out.println("冒泡排序時間:" + (end - start));
    }

ok， 下面再看看快速排序嚎花。

這個快速排序理論有點復(fù)雜紊选。

看這個圖哈（剛剛盜的）道逗。

image

這個數(shù)組第一個數(shù)是6滓窍， ok吏夯，接下來注意， 從右往左 找到一個比6小的數(shù)裆赵，從左往右找到一個比6大的數(shù)战授，然后交換這個數(shù)的位置桨嫁。如下：

快速排序

快速排序

依次這樣楣导，注意哈肚逸，必須每次都從右邊開始找朦促。知道從兩邊找的時候相遇务冕。

快速排序

然后把最中間這個數(shù)和第一個數(shù)6做交換。

快速排序

快速排序

從中間的6為界限落恼，把整個需要排序的數(shù)組分成兩部分佳谦。左邊為3滋戳， 1奸鸯， 2， 5窗怒， 4扬虚； 右邊是9球恤， 7碎捺， 10收厨， 8优构；

可以看出钦椭，已經(jīng)把大于6和小于6的分開了，接下來嘛侥锦，把這兩部分按之前的辦法繼續(xù)排就行恭垦。

當(dāng)然番挺，代碼上需要使用到遞歸的方法。所以一開始啊就要設(shè)計好一個方法用來遞歸的調(diào)用襟衰。

遞歸方法設(shè)計如下：

//且看瀑晒，這里傳入了三個參數(shù)赶熟，第一個參數(shù)a 表示要排序的整個的數(shù)組映砖，start表示從這個數(shù)組的排序起始位置邑退，end則表示這個數(shù)組的排序結(jié)束位置。
private static void quickSort(int[] a, int start, int end){
        if(end < start)     //結(jié)束位置大于起始位置蜈七，表示排完了飒硅，方法直接結(jié)束三娩。
            return ;
        int key = a[start];     //記錄需要排序的的哥元素妹懒，比如之前我們說的6
        int i = start;          //記錄排序起始位置和結(jié)束位置
        int j = end;
       //這個循環(huán)就是循環(huán)從右開始找比第一個數(shù)小的和從左開始找比第一個數(shù)大的做交換
        while(i < j) {
            //先從右找（必須）小于key的值眨唬，找到了就跳出循環(huán)
            while(a[j] >= key && i < j){
                j--;
            }
           // 再從左找大于key的值匾竿，找到就跳出循環(huán)
            while(a[i] <= key && i < j){
                i++;
            }
            // 從右找的滿足條件的下標(biāo)**大于**從左找到滿足條件的下標(biāo)岭妖，就交換兩個數(shù)的值
            if(i < j) {
                a[i] ^= a[j];
                a[j] ^= a[i];
                a[i] ^= a[j];
            }
        }
        //交換最中間的數(shù)和第一個被選擇的數(shù)
        a[start] = a[i];
        a[i] = key;
        //遞歸分出來的左部分
        quickSort(a, start, i - 1);
        //遞歸分出來的右部分
        quickSort(a, i + 1, end);
       //中間那個數(shù)就不參與排序了笛坦。
    }

我測試五組數(shù)據(jù)版扩，花費時間如下：6ms礁芦，4ms悼尾，0ms闺魏，5ms析桥，5ms

測試代碼如下：

  public static void main(String[] args) {
        int[] a = new int[10000];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int)(Math.random() * 10000);
        }
        System.out.println(Arrays.toString(a));
        //快速排序
        quickSort(a.clone());
    }

    //快速排序
    private static void quickSort(int[] numbers){
        long start = System.currentTimeMillis();
        quickSort(numbers, 0, numbers.length - 1);
        long end = System.currentTimeMillis();
        System.out.println(Arrays.toString(numbers));
        System.out.println("快速排序時間:" + (end - start));
    }

    //被遞歸的方法
    private static void quickSort(int[] a, int start, int end){
        if(end < start)
            return ;
        int key = a[start];
        int i = start;
        int j = end;
        while(i < j) {
            while(a[j] >= key && i < j){
                j--;
            }
            while(a[i] <= key && i < j){
                i++;
            }
            if(i < j) {
                a[i] ^= a[j];
                a[j] ^= a[i];
                a[i] ^= a[j];
            }
        }
        a[start] = a[i];
        a[i] = key;
        quickSort(a, start, i - 1);
        quickSort(a, i + 1, end);
    }

但你應(yīng)該可以看出泡仗，快速排序不是穩(wěn)定的娩怎，并且算法上復(fù)雜一點截亦。

接下來look下插入排序崩瓤。

原理呢，也很簡單，首先把需要排序的數(shù)組看成一個有序表和一個無序表肾扰。比如：

數(shù)組a = {10集晚，2区匣，8，6欺旧，13蛤签，57震肮，22戳晌，19，4}

先把10這一個元素看成是有序表疫向，2到后邊的4堪稱無序表鸿捧。

我們每次從無序表中取一個元素放到有序表去排序匙奴，知道排完泼菌。

核心代碼如下：

       //從第二個開始排啦租，所以i = 1,注意這里**不能length - 1**
       for (int i = 1; i < a.length; i++) {
            //從右向左去比較篷角，如果小于前面的就交換恳蹲，類似冒泡排序哈
            for(int j = i - 1; j >= 0; j--) {
                if(a[j] > a[j + 1]) {
                    a[j] ^= a[j+1];
                    a[j+1] ^= a[j];
                    a[j] ^= a[j+1];
                }
            }
        }

測試五組數(shù)據(jù)嘉蕾，花費時間如下： 180ms错忱， 185ms，165ms儿普，181ms箕肃，168ms

效率比冒泡快一點勺像。同時它是穩(wěn)定的吟宦。

繼續(xù)殃姓。looklook歸并排序。

歸并排序基于分治法 篷牌。別問我枷颊，我也不知道啥是分治法夭苗。

原理就是一直劃分一直劃分题造，劃分出很多個小序列猾瘸，各自排序牵触，然后再合并排序荒吏。

舉個栗子

原數(shù)組 ： 6 3 5 8 1 7 2 4

第一次劃分： 6 3 5 8 | 1 7 2 4

第二次劃分： 6 3 | 5 8 | 1 7 | 2 4

第三次劃分： 6 | 3 | 5 | 8 | 1 | 7 | 2 | 4

劃分到第三次發(fā)現(xiàn)所有的小序列都是有序的了绰更。接下來慢慢合并小序列儡湾。

第一次合并： 3 6 | 5 | 8 | 1 | 7 | 2 | 4 //這里只把第一個和第二個排了序徐钠。

第二次合并： 3 6 | 5 8 | 1 | 7 | 2 | 4 //只把第三個和第四個排了序尝丐。

第三次合并： 3 5 6 8 | 1 | 7 | 2 | 4 //前面四個排序完成，后面四個亦是如此

我們細說下第三次合并是什么回事远荠。

在第二次合并的時候譬淳，3和6是一組邻梆，5和8是一組浦妄，首先去第一組的第一個和第二組的第一個比較將最小的結(jié)果放在新的數(shù)組中校辩，這里最小的就是3宜咒，放到新數(shù)組的的第一個，接下來比較第一組的第二個和第二組的第一個比較把鉴，也就是6和5比較故黑，最小的是5，把5放到新數(shù)組的第二個位置庭砍，再把第一組的第二個和第二組的第二個比較场晶，依次進行直到合并完成。

直接分析代碼吧怠缸。

//這個方法需要傳三個參數(shù)诗轻，a為需要排序的數(shù)組，start是需要排序的初始位置扳炬，end是需要排序的終止位置吏颖。
private static void mergeSort(int[] a, int start, int end){
        //先判斷是否有需要排序的元素
        if(start == end)
            return;
        //找到整個區(qū)間的最中間的下標(biāo)值。
        int middle = start + ((end - start) >> 1);
        //對劃分的左部分遞歸
        mergeSort(a, start, middle);
        //對劃分的右部分遞歸
        mergeSort(a, middle+1, end);
        //真正在排序的方法
        merge(a, start, middle, end);
    }

    //這個方法在執(zhí)行排序功能 恨樟，middle為start和end最中間的下標(biāo)值
    private static void merge(int[] a, int start, int middle, int end) {
        //初始化一個用于存放排序后元素的數(shù)組
        int[] temp = new int[end - start + 1];
        int i = 0;
        //左部分第一個值的下標(biāo)
        int p1 = start;
        //右部分第一個值的下標(biāo)
        int p2 = middle + 1;
        //當(dāng)p1和p2在有效范圍內(nèi)半醉，選擇最小的值放在新數(shù)組中
        while (p1 <= middle && p2 <= end) {
            temp[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];
        }
        //下面兩個while循環(huán)只會執(zhí)行一個（左部分和右部分只有一個會剩下元素）
        //這個循環(huán)將左部分剩下的元素加入新數(shù)組
        while (p1 <= middle)
            temp[i++] = a[p1++];
       //這個循環(huán)將右部分剩下的元素加入新數(shù)組
        while (p2 <= end)
            temp[i++] = a[p2++];

        //將新數(shù)組中排好序的數(shù)組復(fù)制到原數(shù)組
        for (i = 0; i < temp.length; i++)
            a[start +i] = temp[i];
    }

老規(guī)矩，測試五組數(shù)據(jù)劝术；時間如下：5ms 5ms 5ms 5ms 5ms

歸并排序在數(shù)據(jù)量很大時缩多，效率高于快速排序。歸并排序是穩(wěn)定的养晋。歸并排序會產(chǎn)生輔助數(shù)組衬吆，會消耗更多內(nèi)存。

jdk為我們提供兩個方法用于排序匙握，一個是Arrays下的sort方法咆槽，另一個是Collections下的sort方法（灰常好使）。

Arrasy.sort()方法支持傳入int[]圈纺，byte[]秦忿，short[]，long[]蛾娶，float[]灯谣，double[]，char[]蛔琅，Object[]胎许，T；Collections.sort只能傳入List<T>罗售；

這里我們重點說Arrays.sort()辜窑。

點進去發(fā)現(xiàn)如下：

   public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

繼續(xù)往里面進。

稍有點長寨躁，怕嚇著各位穆碎，先不粘貼源碼。且聽我分析职恳。

先看第一步

       //right - left代表整個數(shù)組的長度 所禀，QUICKSORT_THRESHOLD 為一個int值 286
      if (right - left < QUICKSORT_THRESHOLD) {
            sort(a, left, right, true);
            return;
        }

就是說當(dāng)需要排序的數(shù)組長度小于286就調(diào)用sort這個方法。

我們這里先往下看大于286的情況,等下后邊再看sort這個方法放钦。

       // Check if the array is nearly sorted
        for (int k = left; k < right; run[count] = k) {
            if (a[k] < a[k + 1]) { // ascending
                while (++k <= right && a[k - 1] <= a[k]);
            } else if (a[k] > a[k + 1]) { // descending
                while (++k <= right && a[k - 1] >= a[k]);
                for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                    int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                }
            } else { // equal
                for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                    if (--m == 0) {
                        sort(a, left, right, true);
                        return;
                    }
                }
            }

            //MAX_RUN_COUNT = 67
            if (++count == MAX_RUN_COUNT) {
                sort(a, left, right, true);
                return;
            }
        }

這段代碼在判斷數(shù)組是否具備結(jié)構(gòu)色徘，實際邏輯是分組排序，每降序為一個組操禀，像1,9,8,7,6,8褂策。9到6是降序，為一個組，然后把降序的一組排成升序：1,6,7,8,9,8斤寂。然后最后的8后面繼續(xù)往后面找蔑水。。扬蕊。

每遇到這樣一個降序組，++count丹擎，當(dāng)count大于MAX_RUN_COUNT（67）尾抑，被判斷為這個數(shù)組不具備結(jié)構(gòu)（也就是這數(shù)據(jù)時而升時而降），和之前小于286一樣蒂培，調(diào)用了sort方法再愈。

這里我們先繼續(xù)看小于67的情況。

// Check special cases
        // Implementation note: variable "right" is increased by 1.
        if (run[count] == right++) { // The last run contains one element
            run[++count] = right;
        } else if (count == 1) { // The array is already sorted
            return;
        }

        // Determine alternation base for merge
        byte odd = 0;
        for (int n = 1; (n <<= 1) < count; odd ^= 1);

        // Use or create temporary array b for merging
        int[] b;                 // temp array; alternates with a
        int ao, bo;              // array offsets from 'left'
        int blen = right - left; // space needed for b
        if (work == null || workLen < blen || workBase + blen > work.length) {
            work = new int[blen];
            workBase = 0;
        }
        if (odd == 0) {
            System.arraycopy(a, left, work, workBase, blen);
            b = a;
            bo = 0;
            a = work;
            ao = workBase - left;
        } else {
            b = work;
            ao = 0;
            bo = workBase - left;
        }

        // Merging
        for (int last; count > 1; count = last) {
            for (int k = (last = 0) + 2; k <= count; k += 2) {
                int hi = run[k], mi = run[k - 1];
                for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                    if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                        b[i + bo] = a[p++ + ao];
                    } else {
                        b[i + bo] = a[q++ + ao];
                    }
                }
                run[++last] = hi;
            }
            if ((count & 1) != 0) {
                for (int i = right, lo = run[count - 1]; --i >= lo;
                    b[i + bo] = a[i + ao]
                );
                run[++last] = right;
            }
            int[] t = a; a = b; b = t;
            int o = ao; ao = bo; bo = o;
        }

大概通過注釋能看出來是進行了歸并排序护戳。此處理解的比較模糊翎冲，后邊有時間進行補全。

下面看看sort方法：

int length = right - left + 1;

        // 先判斷數(shù)組的長度是否小于INSERTION_SORT_THRESHOLD = 47
        if (length < INSERTION_SORT_THRESHOLD) {
            if (leftmost) {        //leftmost這個參數(shù)前面?zhèn)鬟M入就為true
                //這里執(zhí)行了插入排序
                for (int i = left, j = i; i < right; j = ++i) {
                    int ai = a[i + 1];
                    while (ai < a[j]) {
                        a[j + 1] = a[j];
                        if (j-- == left) {
                            break;
                        }
                    }
                    a[j + 1] = ai;
                }
            } 

數(shù)組長度大于47時代碼有點多媳荒，不粘貼抗悍，大致說下；

大于47時采用快速排序的方法：
1.從數(shù)列中挑出五個元素钳枕，稱為 “基準(zhǔn)”（pivot）缴渊；
2.重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面鱼炒，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）衔沼。在這個分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置昔瞧。這個稱為分區(qū)（partition）操作指蚁；
3.遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

Arrays.sort（）這個static方法針對 數(shù)組的特性采用了不同的排序方法自晰。所以使用這個方法排序效率上可能會比我們自己去寫排序算法高一點凝化。