前言

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

回顧：

• 冒泡排序就這么簡單
• 選擇排序就這么簡單
• 插入排序就這么簡單
• 快速排序就這么簡單
• 歸并排序就這么簡單
• 堆排序就這么簡單
• 希爾排序就這么簡單
• 基數(shù)排序就這么簡單

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

二、八大排序總結

2.1冒泡排序

思路：

• 倆倆交換，大的放在后面，第一次排序后最大值已在數(shù)組末尾。
• 因為倆倆交換，需要n-1趟排序，比如10個數(shù)，需要9趟排序

代碼實現(xiàn)要點：

• 兩個for循環(huán)，外層循環(huán)控制排序的趟數(shù)，內層循環(huán)控制比較的次數(shù)
  • 每趟過后，比較的次數(shù)都應該要減1
• 優(yōu)化：如果一趟排序后也沒有交換位置，那么該數(shù)組已有序～

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

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

        //內層循環(huán)是當前趟數(shù)需要比較的次數(shù)
        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;

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

            }
        }
        //如果比較完一趟沒有發(fā)生置換，那么說明已經排好序了，不需要再執(zhí)行下去了
        if (isChange == 0) {
            break;
        }

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

2.2選擇排序

思路：

• 找到數(shù)組中最大的元素，與數(shù)組最后一位元素交換
• 當只有一個數(shù)時，則不需要選擇了，因此需要n-1趟排序，比如10個數(shù)，需要9趟排序

代碼實現(xiàn)要點：

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

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

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

        //內層循環(huán)控制遍歷數(shù)組的個數(shù)并得到最大數(shù)的角標
        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);

2.3插入排序

思路：

• 將一個元素插入到已有序的數(shù)組中，在初始時未知是否存在有序的數(shù)據(jù)，因此將元素第一個元素看成是有序的
• 與有序的數(shù)組進行比較，比它大則直接放入，比它小則移動數(shù)組元素的位置，找到個合適的位置插入
• 當只有一個數(shù)時，則不需要插入了，因此需要n-1趟排序，比如10個數(shù)，需要9趟排序

代碼實現(xiàn)：

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

    //臨時變量
    int temp;

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

        temp = arrays[i];

        //如果前一位(已排序的數(shù)據(jù))比當前數(shù)據(jù)要大，那么就進入循環(huán)比較[參考第二趟排序]
        while (i >= 1 && arrays[i - 1] > temp) {

            //往后退一個位置，讓當前數(shù)據(jù)與之前前位進行比較
            arrays[i] = arrays[i - 1];

            //不斷往前，直到退出循環(huán)
            i--;

        }

        //退出了循環(huán)說明找到了合適的位置了，將當前數(shù)據(jù)插入合適的位置中
        arrays[i] = temp;

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

2.4快速排序

思路：

• 在數(shù)組中找一個元素(節(jié)點)，比它小的放在節(jié)點的左邊，比它大的放在節(jié)點右邊。一趟下來，比節(jié)點小的在左邊，比節(jié)點大的在右邊。
• 不斷執(zhí)行這個操作....

代碼實現(xiàn)：

• 快速排序用遞歸比較好寫【如果不太熟悉遞歸的同學可到：遞歸就這么簡單】。支點取中間，使用L和R表示數(shù)組的最小和最大位置
  • 不斷進行比較，直到找到比支點小(大)的數(shù)，隨后交換，不斷減小范圍～
• 遞歸L到支點前一個元素(j)(執(zhí)行相同的操作,同上)
• 遞歸支點后一個元素(i)到R元素(執(zhí)行相同的操作,同上)

/**
 * 快速排序
 *
 * @param arr
 * @param L   指向數(shù)組第一個元素
 * @param R   指向數(shù)組最后一個元素
 */
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) {

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

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

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

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

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

2.5歸并排序

思路：

• 將兩個已排好序的數(shù)組合并成一個有序的數(shù)組。
  • 將元素分隔開來，看成是有序的數(shù)組，進行比較合并
  • 不斷拆分和合并，直到只有一個元素

代碼實現(xiàn)：

• 在第一趟排序時實質是兩個元素(看成是兩個已有序的數(shù)組)來進行合并，不斷執(zhí)行這樣的操作，最終數(shù)組有序
• 拆分左邊，右邊，合并...

    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      指向數(shù)組第一個元素
     * @param R      指向數(shù)組最后一個元素
     */
    public static void mergeSort(int[] arrays, int L, int R) {

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

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

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

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

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

        }
    }

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

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

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

        //往這兩個數(shù)組填充數(shù)據(jù)
        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數(shù)組的第一個元素
        int  k = L;

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

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

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

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

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

            k++;
            j++;
        }
    }

2.6堆排序

思路：

• 堆排序使用到了完全二叉樹的一個特性【不了解二叉樹的同學可到：二叉樹就這么簡單學習一波】，根節(jié)點比左孩子和右孩子都要大，完成一次建堆的操作實質上是比較根節(jié)點和左孩子、右孩子的大小，大的交換到根節(jié)點上，直至最大的節(jié)點在樹頂
• 隨后與數(shù)組最后一位元素進行交換
• ......

代碼實現(xiàn)：

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

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

}

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

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

}

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

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

        //把當前父節(jié)點位置看成是最大的
        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;

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

2.7希爾排序

思路：

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

代碼思路：

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

   /**
     * 希爾排序
     *
     * @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;
            }
        }

    }

2.8基數(shù)排序

思路：

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

代碼實現(xiàn)：

• 先找到數(shù)組的最大值，然后根據(jù)最大值/10來作為循環(huán)的條件(只要>0，那么就說明還有位數(shù))
• 將個位、十位、...分配到桶子上，每分配一次就回收一次

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

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

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

            //獲取每一位數(shù)字(個、十、百、千位...分配到桶子里)
            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++) {

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

                    }

                }

            }

        }
    }

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

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

        //如果該數(shù)組只有一個數(shù)，那么最大的就是該數(shù)組第一個值了
        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;
            }
        }
    }

三、總結

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

image

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

我也將代碼(包括分解過程)上傳到了GitHub上了，算法和數(shù)據(jù)結構的代碼我都往上面放了，歡迎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