摘要：下面會介紹的一種排序算法快速排序甚至被譽為世紀科學和工程領域的十大算法之一。我們將討論比較排序算法的理論基礎并中借若干排序算法和優先隊列的應用。為了展示初級排序算法性質的價值，我們來看一下基于插入排序的快速的排序算法希爾排序。

　　排序就是將一組對象按照某種邏輯順序重新排列的過程。比如信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計算時代早期，大家普遍認為30%的計算周期都用在了排序上，今天這個比例可能降低了，大概是因為現在的排序算法更加高效。現在這個時代數據可以說是無處不在，而整理數據的第一步往往就是進行排序。所有的計算機系統都實現了各種排序算法以供系統和用戶使用。
　　即使你只是使用標準庫中的排序函數，學習排序算法仍然有很大的實際意義：

排序算法往往是我們解決其他問題的第一步

排序算法有助于我們理解其他算法

算法在公司面試中占有很大比例，排序算法作為其中的重要組成部分，我們理所當然要學好了。

　　另外，更重的是下面介紹的這些算法都很經典，優雅而且高效，學習其中的精髓對自己提高自己的編程能力也有很大的幫助。
　　排序在商業數據處理和現代科學計算中有很重要的地位，它能夠應用于事務處理,組合優化，天體物理學，分子動力學，語言學，基因組學，天氣預報和很多其他領域。下面會介紹的一種排序算法（快速排序）甚至被譽為20世紀科學和工程領域的十大算法之一。后面我們會依次學習幾種經典的排序算法，并高效地實現“優先隊列”這種基礎數據類型。我們將討論比較排序算法的理論基礎并中借若干排序算法和優先隊列的應用。

　 這是比較簡單的一種的排序算法，應該是我們大學最先接觸到的一個排序算法了。很簡單的一種排序算法，大學里好像也是每次必考的吧！

　　比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。針對所有的元素重復以上的步驟，除了最后一個。持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
代碼實現：

    public static void bubbleSort(int[] numbers) {
        int temp = 0;
        int size = numbers.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - 1 - i; j++) {
                 // 交換兩數位置
                if (numbers[j] > numbers[j + 1])
                {
                    temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
    }

　 選擇排序市一中很容易理解和實現的簡單排序算法。學習它之前首先要知道它的兩個很鮮明的特點。

運行時間和輸入無關。為了找出最小的元素而掃描一遍數組并不能為下一遍掃描提供任何實質性幫助的信息。因此使用這種排序的我們會驚訝的發現，一個已經有序的數組或者數組內元素全部相等的數組和一個元素隨機排列的數組所用的排序時間竟然一樣長！而其他算法會更善于利用輸入的初始狀態，選擇排序則不然。

數據移動是最少的選擇排序的交換次數和數組大小關系是線性關系。看下面的原理時可以很容易明白這一點。

　　在要排序的一組數中，選出最小的一個數與第一個位置的數交換；然后在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最后一個數比較為止。類似下圖：

代碼實現：

    public static void selectSort(int[] numbers) {
        // 數組長度
        int size = numbers.length; 
        // 中間變量
        int temp = 0; 

        for (int i = 0; i < size; i++) {
            // 待確定的位置
            int k = i; 
            // 選擇出應該在第i個位置的數
            for (int j = size - 1; j > i; j--) {
                if (numbers[j] < numbers[k]) {
                    k = j;
                }
            }
            // 交換兩個數
            temp = numbers[i];
            numbers[i] = numbers[k];
            numbers[k] = temp;
        }
    }

　　通常人們整理橋牌的方法是一張一張的來，將每一張牌插入到其他已經有序牌中的適當位置。在計算機的實現中，為了給要插入的元素騰出空間，我們需要將其余所有元素在插入之前都向右移動以為。這種算法就叫插入排序。
　**　與選擇排序一樣，當前索引左邊的所有元素都是有序的，但他們的最終位置還不確定為了給更小的元素騰出空間，他們可能會被移動。但是當索引到達數組的右端時，數組排序就完成了。
　　和選擇排序不同的是，插入排序所需的時間取決于輸入中元素的初始順序。也就是說對一個接近有序或有序的數組進行排序會比隨機順序或是逆序的數組進行排序要快的多。**

　　每步將一個待排序的記錄，按其順序碼大小插入到前面已經排序的字序列的合適位置（從后向前找到合適位置后），直到全部插入排序完為止。類似下圖：
　　

    /**
     * 插入排序
     * 
     * 從第一個元素開始，該元素可以認為已經被排序 取出下一個元素，在已經排序的元素序列中從后向前掃描
     * 如果該元素（已排序）大于新元素，將該元素移到下一位置 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置 將新元素插入到該位置中 重復步驟2
     * 
     * @param numbers
     *            待排序數組
     */
    public static void insertSort(int[] numbers) {
        int size = numbers.length;
        int temp = 0;
        int j = 0;

        for (int i = 0; i < size; i++) {
            temp = numbers[i];
            // 假如temp比前面的值小，則將前面的值后移
            for (j = i; j > 0 && temp < numbers[j - 1]; j--) {
                numbers[j] = numbers[j - 1];
            }
            numbers[j] = temp;
        }
    }

　　這個排序咋一看名字感覺很高大上，這是以D.L.shell名字命名的排序算法。
　　為了展示初級排序算法性質的價值，我們來看一下基于插入排序的快速的排序算法——希爾排序。對于大規模亂序的數組插入排序很慢，因為它只會交換相鄰的元素，因此元素只能一點一點地從數組的一端移動到另一端。如果最小的元素剛好在數組的盡頭的話，那么要將它移動到正確的位置要N-1次移動。希爾排序為了加快速度簡單地改進了插入排序，交換不相鄰的元素以對數組的局部進行排序，并最終用插入排序將局部有序的數組排序。

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

 /**
     * 希爾排序的原理:根據需求，如果你想要結果從大到小排列，它會首先將數組進行分組，然后將較大值移到前面，較小值
     * 移到后面，最后將整個數組進行插入排序，這樣比起一開始就用插入排序減少了數據交換和移動的次數，可以說希爾排序是加強 版的插入排序 拿數組5, 2,
     * 8, 9, 1, 3，4來說，數組長度為7，當increment為3時，數組分為兩個序列
     * 5，2，8和9，1，3，4，第一次排序，9和5比較，1和2比較，3和8比較，4和比其下標值小increment的數組值相比較
     * 此例子是按照從大到小排列，所以大的會排在前面，第一次排序后數組為9, 2, 8, 5, 1, 3，4
     * 第一次后increment的值變為3/2=1,此時對數組進行插入排序， 實現數組從大到小排
     */

    public static void shellSort(int[] data) {
        int j = 0;
        int temp = 0;
        // 每次將步長縮短為原來的一半
        for (int increment = data.length / 2; increment > 0; increment /= 2) {
            for (int i = increment; i < data.length; i++) {
                temp = data[i];
                for (j = i; j >= increment; j -= increment) {
                   // 如想從小到大排只需修改這里
                    if (temp > data[j - increment])
                    {
                        data[j] = data[j - increment];
                    } else {
                        break;
                    }

                }
                data[j] = temp;
            }

        }
    }

　　歸并即將兩個有序的數組歸并并成一個更大的有序數組。人們很快根據這個思路發明了一種簡單的遞歸排序算法：歸并排序。要將一個數組排序，可以先（遞歸地）將它分成兩半分別排序，然后將結果歸并起來。歸并排序最吸引人的性質是它能保證任意長度為N的數組排序所需時間和NlogN成正比；它的主要缺點也顯而易見就是它所需的額外空間和N成正比。簡單的歸并排序如下圖：

　　歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
　　合并方法：
　　設r[i…n]由兩個有序子表r[i…m]和r[m+1…n]組成，兩個子表長度分別為n-i +1、n-m。

1、j=m+1；k=i；i=i; //置兩個子表的起始下標及輔助數組的起始下標
2、若i>m 或j>n，轉⑷ //其中一個子表已合并完，比較選取結束
3、//選取r[i]和r[j]較小的存入輔助數組rf
        如果r[i]
3,實現代碼
/**
     * 歸并排序 簡介:將兩個（或兩個以上）有序表合并成一個新的有序表
     * 即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列 時間復雜度為O(nlogn) 穩定排序方式
     * 
     * @param nums
     *            待排序數組
     * @return 輸出有序數組
     */

    public static int[] mergeSort(int[] nums, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左邊
            mergeSort(nums, low, mid);
            // 右邊
            mergeSort(nums, mid + 1, high);
            // 左右歸并
            merge(nums, low, mid, high);
        }
        return nums;
    }

    /**
     * 將數組中low到high位置的數進行排序
     * 
     * @param nums
     *            待排序數組
     * @param low
     *            待排的開始位置
     * @param mid
     *            待排中間位置
     * @param high
     *            待排結束位置
     */
    public static void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指針
        int j = mid + 1;// 右指針
        int k = 0;

        // 把較小的數先移到新數組中
        while (i <= mid && j <= high) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        // 把左邊剩余的數移入數組
        while (i <= mid) {
            temp[k++] = nums[i++];
        }

        // 把右邊邊剩余的數移入數組
        while (j <= high) {
            temp[k++] = nums[j++];
        }

        // 把新數組中的數覆蓋nums數組
        for (int k2 = 0; k2 < temp.length; k2++) {
            nums[k2 + low] = temp[k2];
        }
    }
第三章——進階之快速排序
前言：
　　快速排序可能是應用最廣泛的排序算法了。快速排序流行的原因主要因為它實現簡單，適用于不同的輸入數據且在一般應用中比其他排序算法都要快得多。快速排序引人注目的特點包括它是原地排序（只需要一個很小的輔助棧），且將長度為N的數組排序所需要的時間和NlgN成正比。我們之前提到的幾種排序算法都無法將這兩個優點結合起來。另外，快速排序的內循環比大多數排序算法都要短小，這意味著它無論是理論上還是實際中都要更快。它的主要缺點是非常脆弱，在實現時要非常小心才能避免低劣的性能。已經有無數例子顯示許多錯誤都能致使它在實際應用中的性能只有平方級別。不過還好，我們由這些缺點和教訓中大大改進了快速排序算法，使它的應用更加廣泛。
1，介紹
　　快速排序是一種分治的排序算法。它將一個數組分成兩個字數組，將兩部分獨立地排序。快速排序和歸并排序是互補的：歸并排序將數組分成兩個字數組分別排序，并將有序的字數組歸并以將整個數組排序；而快速排序將數組排序的方式則是當兩個字數組都有序時整個數組也就自然有序了。在第一種情況中，遞歸調用發生在處理整個數組之前；在第二種情況中，遞歸調用發生在處理整個數組之后。在歸并排序中，一個數組被等分為兩半；快速排序中，切分的位置取決于數組的內容。快速排序的過程大致如下：

2，原理
快速排序的基本思想：
　　通過一趟排序將待排序記錄分割成獨立的兩部分，一部分全小于選取的參考值，另一部分全大于選取的參考值。這樣分別對兩部分排序之后順序就可以排好了。
例子：
（a）一趟排序的過程：

（b）排序的全過程：

3,實現代碼
    /**
     * 查找出中軸（默認是最低位low）的在numbers數組排序后所在位置
     * 
     * @param numbers 帶查找數組
     * @param low 開始位置
     * @param high 結束位置
     * @return 中軸所在位置
     */
    public static int getMiddle(int[] numbers, int low, int high) {
        // 數組的第一個作為中軸
        int temp = numbers[low]; 
        while (low < high) {
            while (low < high && numbers[high] > temp) {
                high--;
            }
            // 比中軸小的記錄移到低端
            numbers[low] = numbers[high];
            while (low < high && numbers[low] < temp) {
                low++;
            }
            // 比中軸大的記錄移到高端
            numbers[high] = numbers[low]; 
        }
        numbers[low] = temp; // 中軸記錄到尾
        return low; // 返回中軸的位置
    }

    /**
     * 
     * @param numbers 帶排序數組
     * @param low 開始位置
     * @param high 結束位置
     */
    public static void quick(int[] numbers, int low, int high) {
        if (low < high) {
            int middle = getMiddle(numbers, low, high); // 將numbers數組進行一分為二
            quick(numbers, low, middle - 1); // 對低字段表進行遞歸排序
            quick(numbers, middle + 1, high); // 對高字段表進行遞歸排序
        }

    }

    /**
     * 快速排序
     * 快速排序提供方法調用
     * @param numbers 帶排序數組
     */
    public static void quickSort(int[] numbers) {
        // 查看數組是否為空
        if (numbers.length > 0) 
        {
            quick(numbers, 0, numbers.length - 1);
        }
    }

4，改進方法
我們只介紹一種常用的，具體代碼就不貼出了。想去的可以去https://algs4.cs.princeton.ed...　這個網站找。
三向切分快速排序  ：
　　核心思想就是將待排序的數據分為三部分,左邊都小于比較值,右邊都大于比較值,中間的數和比較值相等.三向切分快速排序的特性就是遇到和比較值相同時,不進行數據交換,  這樣對于有大量重復數據的排序時,三向切分快速排序算法就會優于普通快速排序算法,但由于它整體判斷代碼比普通快速排序多一點,所以對于常見的大量非重復數據,它并不能比普通快速排序多大多的優勢 。
歡迎關注我的微信公眾號（分享各種Java學習資源，面試題，以及企業級Java實戰項目回復關鍵字免費領取）：