摘要：不斷執行這個操作代碼實現快速排序用遞歸比較好寫如果不太熟悉遞歸的同學可到遞歸就這么簡單。

大概花了一周的時間把八大基礎排序過了一遍，這篇博文主要是用來回顧一下八大基礎排序的要點和一些總結～

回顧：

冒泡排序就這么簡單

選擇排序就這么簡單

插入排序就這么簡單

快速排序就這么簡單

歸并排序就這么簡單

堆排序就這么簡單

希爾排序就這么簡單

基數排序就這么簡單

總的來說：快速排序是用得比較廣泛的一個排序，也是經常出現的一個排序，應該重點掌握～

思路：

倆倆交換，大的放在后面，第一次排序后最大值已在數組末尾。

因為倆倆交換，需要n-1趟排序，比如10個數，需要9趟排序

代碼實現要點：

兩個for循環，外層循環控制排序的趟數，內層循環控制比較的次數

每趟過后，比較的次數都應該要減1

優化：如果一趟排序后也沒有交換位置，那么該數組已有序～

    //外層循環是排序的趟數
    for (int i = 0; i < arrays.length -1 ; i++) {

        //每比較一趟就重新初始化為0
        isChange = 0;

        //內層循環是當前趟數需要比較的次數
        for (int j = 0; j < arrays.length - i - 1; j++) {

            //前一位與后一位與前一位比較，如果前一位比后一位要大，那么交換
            if (arrays[j] > arrays[j + 1]) {
                temp = arrays[j];
                arrays[j] = arrays[j + 1];
                arrays[j + 1] = temp;


                //如果進到這里面了，說明發生置換了
                isChange = 1;

            }
        }
        //如果比較完一趟沒有發生置換，那么說明已經排好序了，不需要再執行下去了
        if (isChange == 0) {
            break;
        }
      
    }
    System.out.println("公眾號Java3y" + arrays);

思路：

找到數組中最大的元素，與數組最后一位元素交換

當只有一個數時，則不需要選擇了，因此需要n-1趟排序，比如10個數，需要9趟排序

代碼實現要點：

兩個for循環，外層循環控制排序的趟數，內層循環找到當前趟數的最大值，隨后與當前趟數組最后的一位元素交換

    //外層循環控制需要排序的趟數
    for (int i = 0; i < arrays.length - 1; i++) {

        //新的趟數、將角標重新賦值為0
        pos = 0;

        //內層循環控制遍歷數組的個數并得到最大數的角標
        for (int j = 0; j < arrays.length - i; j++) {

            if (arrays[j] > arrays[pos]) {
                pos = j;
            }

        }
        //交換
        temp = arrays[pos];
        arrays[pos] = arrays[arrays.length - 1 - i];
        arrays[arrays.length - 1 - i] = temp;


    }

    System.out.println("公眾號Java3y" + arrays);

思路：

將一個元素插入到已有序的數組中，在初始時未知是否存在有序的數據，因此將元素第一個元素看成是有序的

與有序的數組進行比較，比它大則直接放入，比它小則移動數組元素的位置，找到個合適的位置插入

當只有一個數時，則不需要插入了，因此需要n-1趟排序，比如10個數，需要9趟排序

代碼實現：

一個for循環內嵌一個while循環實現，外層for循環控制需要排序的趟數，while循環找到合適的插入位置(并且插入的位置不能小于0)

    public static void sort(int[] arrays) {
        

        //臨時變量
        int temp;


        //外層循環控制需要排序的趟數(從1開始因為將第0位看成了有序數據)
        for (int i = 1; i < arrays.length; i++) {

            temp = arrays[i];

            //如果前一位(已排序的數據)比當前數據要大，那么就進入循環比較[參考第二趟排序]

            int j = i - 1;

            while (j >= 0 && arrays[j] > temp) {

                //往后退一個位置，讓當前數據與之前前位進行比較
                arrays[j + 1] = arrays[j];

                //不斷往前，直到退出循環
                j--;

            }
            //退出了循環說明找到了合適的位置了，將當前數據插入合適的位置中
            arrays[j + 1] = temp;

        }
        System.out.println("公眾號Java3y" + arrays);
    }

思路：

在數組中找一個元素(節點)，比它小的放在節點的左邊，比它大的放在節點右邊。一趟下來，比節點小的在左邊，比節點大的在右邊。

不斷執行這個操作....

代碼實現：

快速排序用遞歸比較好寫【如果不太熟悉遞歸的同學可到：遞歸就這么簡單】。支點取中間，使用L和R表示數組的最小和最大位置

不斷進行比較，直到找到比支點小(大)的數，隨后交換，不斷減小范圍～

遞歸L到支點前一個元素(j)(執行相同的操作,同上)

遞歸支點后一個元素(i)到R元素(執行相同的操作,同上)

/**
 * 快速排序
 *
 * @param arr
 * @param L   指向數組第一個元素
 * @param R   指向數組最后一個元素
 */
public static void quickSort(int[] arr, int L, int R) {
    int i = L;
    int j = R;

    //支點
    int pivot = arr[(L + R) / 2];

    //左右兩端進行掃描，只要兩端還沒有交替，就一直掃描
    while (i <= j) {

        //尋找直到比支點大的數
        while (pivot > arr[i])
            i++;

        //尋找直到比支點小的數
        while (pivot < arr[j])
            j--;

        //此時已經分別找到了比支點小的數(右邊)、比支點大的數(左邊)，它們進行交換
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    //上面一個while保證了第一趟排序支點的左邊比支點小，支點的右邊比支點大了。


    //“左邊”再做排序，直到左邊剩下一個數(遞歸出口)
    if (L < j)
        quickSort(arr, L, j);

    //“右邊”再做排序，直到右邊剩下一個數(遞歸出口)
    if (i < R)
        quickSort(arr, i, R);
}

思路：

將兩個已排好序的數組合并成一個有序的數組。

將元素分隔開來，看成是有序的數組，進行比較合并

不斷拆分和合并，直到只有一個元素

代碼實現：

在第一趟排序時實質是兩個元素(看成是兩個已有序的數組)來進行合并，不斷執行這樣的操作，最終數組有序

拆分左邊，右邊，合并...

    public static void main(String[] args) {
        int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};
        mergeSort(arrays, 0, arrays.length - 1);

        System.out.println("公眾號：Java3y" + arrays);


    }

    /**
     * 歸并排序
     *
     * @param arrays
     * @param L      指向數組第一個元素
     * @param R      指向數組最后一個元素
     */
    public static void mergeSort(int[] arrays, int L, int R) {

        //如果只有一個元素，那就不用排序了
        if (L == R) {
            return;
        } else {

            //取中間的數，進行拆分
            int M = (L + R) / 2;

            //左邊的數不斷進行拆分
            mergeSort(arrays, L, M);

            //右邊的數不斷進行拆分
            mergeSort(arrays, M + 1, R);

            //合并
            merge(arrays, L, M + 1, R);

        }
    }


    /**
     * 合并數組
     *
     * @param arrays
     * @param L      指向數組第一個元素
     * @param M      指向數組分隔的元素
     * @param R      指向數組最后的元素
     */
    public static void merge(int[] arrays, int L, int M, int R) {

        //左邊的數組的大小
        int[] leftArray = new int[M - L];

        //右邊的數組大小
        int[] rightArray = new int[R - M + 1];

        //往這兩個數組填充數據
        for (int i = L; i < M; i++) {
            leftArray[i - L] = arrays[i];
        }
        for (int i = M; i <= R; i++) {
            rightArray[i - M] = arrays[i];
        }


        int i = 0, j = 0;
        // arrays數組的第一個元素
        int  k = L;


        //比較這兩個數組的值，哪個小，就往數組上放
        while (i < leftArray.length && j < rightArray.length) {

            //誰比較小，誰將元素放入大數組中,移動指針，繼續比較下一個
            if (leftArray[i] < rightArray[j]) {
                arrays[k] = leftArray[i];

                i++;
                k++;
            } else {
                arrays[k] = rightArray[j];
                j++;
                k++;
            }
        }

        //如果左邊的數組還沒比較完，右邊的數都已經完了，那么將左邊的數抄到大數組中(剩下的都是大數字)
        while (i < leftArray.length) {
            arrays[k] = leftArray[i];

            i++;
            k++;
        }
        //如果右邊的數組還沒比較完，左邊的數都已經完了，那么將右邊的數抄到大數組中(剩下的都是大數字)
        while (j < rightArray.length) {
            arrays[k] = rightArray[j];

            k++;
            j++;
        }
    }

思路：

堆排序使用到了完全二叉樹的一個特性【不了解二叉樹的同學可到：二叉樹就這么簡單學習一波】，根節點比左孩子和右孩子都要大，完成一次建堆的操作實質上是比較根節點和左孩子、右孩子的大小，大的交換到根節點上，直至最大的節點在樹頂

隨后與數組最后一位元素進行交換

......

代碼實現：

只要左子樹或右子樹大于當前根節點，則替換。替換后會導致下面的子樹發生了變化，因此同樣需要進行比較，直至各個節點實現父>子這么一個條件

public static void main(String[] args) {

    int[] arrays = {6, 3, 8, 7, 5, 1, 2, 23, 4321, 432, 3,2,34234,2134,1234,5,132423, 234, 4, 2, 4, 1, 5, 2, 5};

    for (int i = 0; i < arrays.length; i++) {

        //每完成一次建堆就可以排除一個元素了
        maxHeapify(arrays, arrays.length - i);

        //交換
        int temp = arrays[0];
        arrays[0] = arrays[(arrays.length - 1) - i];
        arrays[(arrays.length - 1) - i] = temp;

    }

    System.out.println("公眾號：Java3y" + arrays);


}

/**
 * 完成一次建堆，最大值在堆的頂部(根節點)
 */
public static void maxHeapify(int[] arrays, int size) {

    for (int i = size - 1; i >= 0; i--) {
        heapify(arrays, i, size);
    }

}


/**
 * 建堆
 *
 * @param arrays          看作是完全二叉樹
 * @param currentRootNode 當前父節點位置
 * @param size            節點總數
 */
public static void heapify(int[] arrays, int currentRootNode, int size) {

    if (currentRootNode < size) {
        //左子樹和右字數的位置
        int left = 2 * currentRootNode + 1;
        int right = 2 * currentRootNode + 2;

        //把當前父節點位置看成是最大的
        int max = currentRootNode;

        if (left < size) {
            //如果比當前根元素要大，記錄它的位置
            if (arrays[max] < arrays[left]) {
                max = left;
            }
        }
        if (right < size) {
            //如果比當前根元素要大，記錄它的位置
            if (arrays[max] < arrays[right]) {
                max = right;
            }
        }
        //如果最大的不是根元素位置，那么就交換
        if (max != currentRootNode) {
            int temp = arrays[max];
            arrays[max] = arrays[currentRootNode];
            arrays[currentRootNode] = temp;

            //繼續比較，直到完成一次建堆
            heapify(arrays, max, size);
        }
    }
}

思路：

希爾排序實質上就是插入排序的增強版，希爾排序將數組分隔成n組來進行插入排序，直至該數組宏觀上有序，最后再進行插入排序時就不用移動那么多次位置了～

代碼思路：

希爾增量一般是gap = gap / 2，只是比普通版插入排序多了這么一個for循環罷了，難度并不大

   /**
     * 希爾排序
     *
     * @param arrays
     */
    public static void shellSort(int[] arrays) {


        //增量每次都/2
        for (int step = arrays.length / 2; step > 0; step /= 2) {

            //從增量那組開始進行插入排序，直至完畢
            for (int i = step; i < arrays.length; i++) {

                int j = i;
                int temp = arrays[j];

                // j - step 就是代表與它同組隔壁的元素
                while (j - step >= 0 && arrays[j - step] > temp) {
                    arrays[j] = arrays[j - step];
                    j = j - step;
                }
                arrays[j] = temp;
            }
        }


    }

思路：

基數排序(桶排序)：將數字切割成個、十、百、千位放入到不同的桶子里，放一次就按桶子順序回收一次，直至最大位數的數字放完～那么該數組就有序了

代碼實現：

先找到數組的最大值，然后根據最大值/10來作為循環的條件(只要>0，那么就說明還有位數)

將個位、十位、...分配到桶子上，每分配一次就回收一次

    public static void main(String[] args) {

        int[] arrays = {6, 4322, 432, 344, 55, 234, 45, 243, 5, 2, 4, 5, 6, 7, 3245, 345, 345, 234, 68, 65};

        radixSort(arrays);

        System.out.println("公眾號：Java3y" + arrays);

    }

    public static void radixSort(int[] arrays) {

        int max = findMax(arrays, 0, arrays.length - 1);

        //需要遍歷的次數由數組最大值的位數來決定
        for (int i = 1; max / i > 0; i = i * 10) {

            int[][] buckets = new int[arrays.length][10];

            //獲取每一位數字(個、十、百、千位...分配到桶子里)
            for (int j = 0; j < arrays.length; j++) {

                int num = (arrays[j] / i) % 10;

                //將其放入桶子里
                buckets[j][num] = arrays[j];
            }

            //回收桶子里的元素
            int k = 0;

            //有10個桶子
            for (int j = 0; j < 10; j++) {
                //對每個桶子里的元素進行回收
                for (int l = 0; l < arrays.length ; l++) {

                    //如果桶子里面有元素就回收(數據初始化會為0)
                    if (buckets[l][j] != 0) {
                        arrays[k++] = buckets[l][j];

                    }
                    
                }
                
            }

        }
    }


    /**
     * 遞歸，找出數組最大的值
     *
     * @param arrays 數組
     * @param L      左邊界，第一個數
     * @param R      右邊界，數組的長度
     * @return
     */

    public static int findMax(int[] arrays, int L, int R) {

        //如果該數組只有一個數，那么最大的就是該數組第一個值了
        if (L == R) {
            return arrays[L];
        } else {

            int a = arrays[L];
            int b = findMax(arrays, L + 1, R);//找出整體的最大值

            if (a > b) {
                return a;
            } else {
                return b;
            }
        }
    }

對于排序的時間復雜度和穩定性網上的圖也很多很多，我就隨便找一張了(侵刪)

要是對某個排序不太理解的同學最好是到我寫的單個文章中進行查閱，因為有分解的步驟～

我也將代碼(包括分解過程)上傳到了GitHub上了，算法和數據結構的代碼我都往上面放了，歡迎star～后序還會寫棧、隊列相關的博文，敬請期待...

GitHub地址：https://github.com/ZhongFuCheng3y/JavaArithmetic

休閑時間：

你在生活中用過最高級的算法知識是什么？，回答的挺多關于排序的，挺有趣的https://www.zhihu.com/question/67860343

參考資料：

http://www.cnblogs.com/hapjin/p/5517682.html

http://www.cnblogs.com/skywang12345/p/3603935.html

http://blog.chinaunix.net/uid-21457204-id-3060260.html

如果文章有錯的地方歡迎指正，大家互相交流。習慣在微信看技術文章，想要獲取更多的Java資源的同學，可以關注微信公眾號:Java3y