八大基礎(chǔ)排序總結(jié)

maochunguang 發(fā)布于2019-08-16 11:07 / 1102人閱讀

摘要：不斷執(zhí)行這個(gè)操作代碼實(shí)現(xiàn)快速排序用遞歸比較好寫(xiě)如果不太熟悉遞歸的同學(xué)可到遞歸就這么簡(jiǎn)單。

前言

大概花了一周的時(shí)間把八大基礎(chǔ)排序過(guò)了一遍，這篇博文主要是用來(lái)回顧一下八大基礎(chǔ)排序的要點(diǎn)和一些總結(jié)～

回顧：

冒泡排序就這么簡(jiǎn)單

選擇排序就這么簡(jiǎn)單

插入排序就這么簡(jiǎn)單

快速排序就這么簡(jiǎn)單

歸并排序就這么簡(jiǎn)單

堆排序就這么簡(jiǎn)單

希爾排序就這么簡(jiǎn)單

基數(shù)排序就這么簡(jiǎn)單

總的來(lái)說(shuō)：快速排序是用得比較廣泛的一個(gè)排序，也是經(jīng)常出現(xiàn)的一個(gè)排序，應(yīng)該重點(diǎn)掌握～

二、八大排序總結(jié) 2.1冒泡排序

思路：

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

因?yàn)閭z倆交換，需要n-1趟排序，比如10個(gè)數(shù)，需要9趟排序

代碼實(shí)現(xiàn)要點(diǎn)：

兩個(gè)for循環(huán)，外層循環(huán)控制排序的趟數(shù)，內(nèi)層循環(huán)控制比較的次數(shù)

每趟過(guò)后，比較的次數(shù)都應(yīng)該要減1

優(yōu)化：如果一趟排序后也沒(méi)有交換位置，那么該數(shù)組已有序～


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

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

        //內(nèi)層循環(huán)是當(dāng)前趟數(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;


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

            }
        }
        //如果比較完一趟沒(méi)有發(fā)生置換，那么說(shuō)明已經(jīng)排好序了，不需要再執(zhí)行下去了
        if (isChange == 0) {
            break;
        }
      
    }
    System.out.println("公眾號(hào)Java3y" + arrays);

2.2選擇排序

思路：

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

當(dāng)只有一個(gè)數(shù)時(shí)，則不需要選擇了，因此需要n-1趟排序，比如10個(gè)數(shù)，需要9趟排序

代碼實(shí)現(xiàn)要點(diǎn)：

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

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

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

        //內(nèi)層循環(huán)控制遍歷數(shù)組的個(gè)數(shù)并得到最大數(shù)的角標(biāo)
        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("公眾號(hào)Java3y" + arrays);

2.3插入排序

思路：

將一個(gè)元素插入到已有序的數(shù)組中，在初始時(shí)未知是否存在有序的數(shù)據(jù)，因此將元素第一個(gè)元素看成是有序的

與有序的數(shù)組進(jìn)行比較，比它大則直接放入，比它小則移動(dòng)數(shù)組元素的位置，找到個(gè)合適的位置插入

當(dāng)只有一個(gè)數(shù)時(shí)，則不需要插入了，因此需要n-1趟排序，比如10個(gè)數(shù)，需要9趟排序

代碼實(shí)現(xiàn)：

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


    public static void sort(int[] arrays) {
        

        //臨時(shí)變量
        int temp;


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

            temp = arrays[i];

            //如果前一位(已排序的數(shù)據(jù))比當(dāng)前數(shù)據(jù)要大，那么就進(jìn)入循環(huán)比較[參考第二趟排序]

            int j = i - 1;

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

                //往后退一個(gè)位置，讓當(dāng)前數(shù)據(jù)與之前前位進(jìn)行比較
                arrays[j + 1] = arrays[j];

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

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

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

2.4快速排序

思路：

在數(shù)組中找一個(gè)元素(節(jié)點(diǎn))，比它小的放在節(jié)點(diǎn)的左邊，比它大的放在節(jié)點(diǎn)右邊。一趟下來(lái)，比節(jié)點(diǎn)小的在左邊，比節(jié)點(diǎn)大的在右邊。

不斷執(zhí)行這個(gè)操作....

代碼實(shí)現(xiàn)：

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

不斷進(jìn)行比較，直到找到比支點(diǎn)小(大)的數(shù)，隨后交換，不斷減小范圍～

遞歸L到支點(diǎn)前一個(gè)元素(j)(執(zhí)行相同的操作,同上)

遞歸支點(diǎn)后一個(gè)元素(i)到R元素(執(zhí)行相同的操作,同上)


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

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

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

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

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

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


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

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

2.5歸并排序

思路：

將兩個(gè)已排好序的數(shù)組合并成一個(gè)有序的數(shù)組。

將元素分隔開(kāi)來(lái)，看成是有序的數(shù)組，進(jìn)行比較合并

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

代碼實(shí)現(xiàn)：

在第一趟排序時(shí)實(shí)質(zhì)是兩個(gè)元素(看成是兩個(gè)已有序的數(shù)組)來(lái)進(jìn)行合并，不斷執(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("公眾號(hào)：Java3y" + arrays);


    }

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

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

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

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

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

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

        }
    }


    /**
     * 合并數(shù)組
     *
     * @param arrays
     * @param L      指向數(shù)組第一個(gè)元素
     * @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];

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


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

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

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

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

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

            k++;
            j++;
        }
    }

2.6堆排序

思路：

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

隨后與數(shù)組最后一位元素進(jìn)行交換

......

代碼實(shí)現(xiàn)：

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


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++) {

        //每完成一次建堆就可以排除一個(gè)元素了
        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("公眾號(hào)：Java3y" + arrays);


}

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

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

}


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

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

        //把當(dāng)前父節(jié)點(diǎn)位置看成是最大的
        int max = currentRootNode;

        if (left < size) {
            //如果比當(dāng)前根元素要大，記錄它的位置
            if (arrays[max] < arrays[left]) {
                max = left;
            }
        }
        if (right < size) {
            //如果比當(dāng)前根元素要大，記錄它的位置
            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希爾排序

思路：

希爾排序?qū)嵸|(zhì)上就是插入排序的增強(qiáng)版，希爾排序?qū)?shù)組分隔成n組來(lái)進(jìn)行插入排序，直至該數(shù)組宏觀上有序，最后再進(jìn)行插入排序時(shí)就不用移動(dòng)那么多次位置了～

代碼思路：

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

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


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

            //從增量那組開(kāi)始進(jìn)行插入排序，直至完畢
            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ù)字切割成個(gè)、十、百、千位放入到不同的桶子里，放一次就按桶子順序回收一次，直至最大位數(shù)的數(shù)字放完～那么該數(shù)組就有序了

代碼實(shí)現(xiàn)：

先找到數(shù)組的最大值，然后根據(jù)最大值/10來(lái)作為循環(huán)的條件(只要>0，那么就說(shuō)明還有位數(shù))

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


    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("公眾號(hào)：Java3y" + arrays);

    }

    public static void radixSort(int[] arrays) {

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

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

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

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

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

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

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

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

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

                    }
                    
                }
                
            }

        }
    }


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

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

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

三、總結(jié)

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

要是對(duì)某個(gè)排序不太理解的同學(xué)最好是到我寫(xiě)的單個(gè)文章中進(jìn)行查閱，因?yàn)橛蟹纸獾牟襟E～

我也將代碼(包括分解過(guò)程)上傳到了GitHub上了，算法和數(shù)據(jù)結(jié)構(gòu)的代碼我都往上面放了，歡迎star～后序還會(huì)寫(xiě)棧、隊(duì)列相關(guān)的博文，敬請(qǐng)期待...

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

休閑時(shí)間：

你在生活中用過(guò)最高級(jí)的算法知識(shí)是什么？，回答的挺多關(guān)于排序的，挺有趣的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

如果文章有錯(cuò)的地方歡迎指正，大家互相交流。習(xí)慣在微信看技術(shù)文章，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號(hào):Java3y

云服務(wù)器 GPU云服務(wù)器排序算法總結(jié) 云主機(jī)的八大優(yōu)勢(shì) 云主機(jī)八大產(chǎn)品優(yōu)勢(shì) php的八大數(shù)據(jù)類型

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/71019.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

maochunguang

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

Java基礎(chǔ)語(yǔ)法筆記

閱讀 1261·2021-09-04 16:41
AHJCDN：免備案CDN，無(wú)視DDOS/CC攻擊的CDN，香港/美國(guó)GIA高速節(jié)點(diǎn)，提供免費(fèi)套餐

閱讀 2423·2021-09-02 10:18
Yoshino: 一個(gè)基于React的可定制化的PC組件庫(kù)

閱讀 927·2019-08-29 16:40
html&css面試筆記

閱讀 2623·2019-08-29 16:14
Visual Studio Code 裝飾器提示“experimentalDecorators”的解

閱讀 914·2019-08-26 13:41
使用node打造自己的命令行工具方法教程

閱讀 1308·2019-08-26 12:24
今天，我明白了JS事件循環(huán)機(jī)制

閱讀 739·2019-08-26 10:24
JavaScript 中的 forEach 源碼

閱讀 2879·2019-08-23 17:54

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

八大基礎(chǔ)排序總結(jié)

相關(guān)文章

**糊涂算法之「八大排序」總結(jié)——用兩萬(wàn)字，8張動(dòng)圖，450行代碼跨過(guò)排序這道坎（建議收藏）**

**【數(shù)據(jù)結(jié)構(gòu)初階】第九篇——八大經(jīng)典排序算法總結(jié)（圖解+動(dòng)圖演示+代碼實(shí)現(xiàn)+八大排序比較）**

后端知識(shí)- 收藏集 - 掘金

后端知識(shí)- 收藏集 - 掘金

發(fā)表評(píng)論

0條評(píng)論

maochunguang

男|高級(jí)講師

TA的文章

Java基礎(chǔ)語(yǔ)法筆記

AHJCDN：免備案CDN，無(wú)視DDOS/CC攻擊的CDN，香港/美國(guó)GIA高速節(jié)點(diǎn)，提供免費(fèi)套餐

Yoshino: 一個(gè)基于React的可定制化的PC組件庫(kù)

html&css面試筆記

Visual Studio Code 裝飾器提示“experimentalDecorators”的解

使用node打造自己的命令行工具方法教程

今天，我明白了JS事件循環(huán)機(jī)制

JavaScript 中的 forEach 源碼

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

八大基礎(chǔ)排序總結(jié)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！