十大排序算法全面解析-Java實(shí)現(xiàn)

前言

算法就是編程的靈魂，不會算法的程序員只配做碼農(nóng)。之前看到這句話受到一萬點(diǎn)暴擊傷害！同時也激起了自己的斗志，坦白說作為一個程序員，我一直知道算法的重要性，但是在算法這一塊一直做的不夠好，甚至除了大學(xué)學(xué)過這門課程之后就很少去接觸它。因?yàn)橐婚_始我就給算法貼上了難，煩，不怎么用的標(biāo)簽，現(xiàn)在想來其實(shí)都是在逃避問題。所以決定亡羊補(bǔ)牢，從頭開始！

文章首發(fā)于個人博客【http://www.xiongfrblog.cn】

介紹

算法的學(xué)習(xí)也是有著階段性的，從入門到簡單，再到復(fù)雜，再到簡單。最后的簡單是當(dāng)你達(dá)到一定高度之后對于問題能夠準(zhǔn)確的找到最簡單的解答。就如同修仙一樣，真正的高手一招足以擊退萬馬千軍！

算法里邊最常用也是最基本的就是排序算法和查找算法了，本文主要講解算法里邊最經(jīng)典的十大排序算法。在這里我們根據(jù)他們各自的實(shí)現(xiàn)原理以及效率將十大排序算法分為兩大類：

  1. 非線性比較類排序：非線性是指算法的時間復(fù)雜度不能突破(nlogn)，元素之間通過比較大小來決定先后順序。
  2. 線性非比較類排序：算法的時間復(fù)雜度能夠突破(nlogn)，并且不通過比較來對元素排序。

具體分類我們上圖說明：


排序算法分類

算法比較

這里給出算法的時間復(fù)雜度，空間復(fù)雜度以及穩(wěn)定性的對比整理，同樣通過圖片的形式給出：

算法比較

在這里給出相關(guān)指標(biāo)的解釋

時間復(fù)雜度：時間復(fù)雜度本意是預(yù)估算法的執(zhí)行時間，但實(shí)際上一個程序在計(jì)算機(jī)上執(zhí)行的速度是非?？斓模瑫r間幾乎可以忽略不計(jì)了，也就是失去了意義，所以這里意思是算法中執(zhí)行頻度最高的代碼的執(zhí)行的次數(shù)。反應(yīng)當(dāng)n發(fā)生變化時，執(zhí)行次數(shù)的改變呈現(xiàn)一種什么樣的規(guī)律。
空間復(fù)雜度：是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時所需存儲空間的度量，它也是數(shù)據(jù)規(guī)模n的函數(shù)。
穩(wěn)定性：在排序中對于相等的兩個元素a,b。如果排序前a在b的前邊，排序之后a也總是在b的前邊。他們的位置不會因?yàn)榕判蚨淖兎Q之為穩(wěn)定。反之，如果排序后a,b的位置可能會發(fā)生改變，那么就稱之為不穩(wěn)定。

下面就一一對十大算法進(jìn)行詳細(xì)的講解，會給出他們的基本思想，圖片演示，以及帶有詳細(xì)注釋的源碼。（本文所有的排序算法都是升序排序）

1.冒泡排序

1.1 基本思想

冒泡排序可以說是最簡單的排序之一了，也是大部分人最容易想到的排序。即對n個數(shù)進(jìn)行排序，每次都是由前一個數(shù)跟后一個數(shù)比較，每循環(huán)一輪， 就可以將最大的數(shù)移到數(shù)組的最后， 總共循環(huán)n-1輪，完成對數(shù)組排序。

1.2 圖片演示

冒泡排序

1.3 代碼展示

public static void bubbleSort(int[] arr) {
        if(arr==null)
            return;
        int len=arr.length;
        //i控制循環(huán)次數(shù)，長度為len的數(shù)組只需要循環(huán)len-1次，i的起始值為0所以i<len-1
        for(int i=0;i<len-1;i++) {
            //j控制比較次數(shù)，第i次循環(huán)內(nèi)需要比較len-i次
            //但是由于是由arr[j]跟arr[j+1]進(jìn)行比較，所以為了保證arr[j+1]不越界，j<len-i-1
            for(int j=0;j<len-i-1;j++) {
                //如果前一個數(shù)比后一個數(shù)大，則交換位置將大的數(shù)往后放。
                if(arr[j]>arr[j+1]) {
                    int temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                }
            }
        }
    }

2.選擇排序

2.1 基本思想

選擇排序可以說是冒泡排序的改良版，不再是前一個數(shù)跟后一個數(shù)相比較， 而是在每一次循環(huán)內(nèi)都由一個數(shù)去跟 所有的數(shù)都比較一次，每次比較都選取相對較小的那個數(shù)來進(jìn)行下一次的比較，并不斷更新較小數(shù)的下標(biāo) 這樣在一次循環(huán)結(jié)束時就能得到最小數(shù)的下標(biāo)，再通過一次交換將最小的數(shù)放在最前面，通過n-1次循環(huán)之后完成排序。 這樣相對于冒泡排序來說，比較的次數(shù)并沒有改變，但是數(shù)據(jù)交換的次數(shù)大大減少。

2.2 圖片演示

選擇排序

2.3 代碼展示

public static void selectSort(int[] arr) {
        if(arr==null)
            return;
        int len=arr.length;
        //i控制循環(huán)次數(shù)，長度為len的數(shù)組只需要循環(huán)len-1次，i的起始值為0所以i<len-1
        for(int i=0;i<len-1;i++) {
            //minIndex 用來保存每次比較后較小數(shù)的下標(biāo)。
            int minIndex=i;
            //j控制比較次數(shù)，因?yàn)槊看窝h(huán)結(jié)束之后最小的數(shù)都已經(jīng)放在了最前面，
            //所以下一次循環(huán)的時候就可以跳過這個數(shù)，所以j的初始值為i+1而不需要每次循環(huán)都從0開始，并且j<len即可
            for(int j=i+1;j<len;j++) {
                //每比較一次都需要將較小數(shù)的下標(biāo)記錄下來
                if(arr[minIndex]>arr[j]) {
                    minIndex=j;
                }
            }
            //當(dāng)完成一次循環(huán)時，就需要將本次循環(huán)選取的最小數(shù)移動到本次循環(huán)開始的位置。
            if(minIndex!=i) {
                int temp=arr[i];
                arr[i]=arr[minIndex];
                arr[minIndex]=temp;
            }
            //打印每次循環(huán)結(jié)束之后數(shù)組的排序狀態(tài)（方便理解）
            System.out.println("第"+(i+1)+"次循環(huán)之后效果："+Arrays.toString(arr));
        }
    }

3.插入排序

3.1 基本思想

插入排序的思想打牌的人肯定很容易理解，就是見縫插針。 首先就默認(rèn)數(shù)組中的第一個數(shù)的位置是正確的，即已經(jīng)排序。 然后取下一個數(shù)，與已經(jīng)排序的數(shù)按從后向前的順序依次比較， 如果該數(shù)比當(dāng)前位置排好序的數(shù)小，則將排好序的數(shù)的位置向后移一位。 重復(fù)上一步驟，直到找到合適的位置。 找到位置后就結(jié)束比較的循環(huán)，將該數(shù)放到相應(yīng)的位置。

3.2 圖片演示

插入排序

3.3 代碼展示

public static void insertSort(int[] arr) {
        if(arr==null)
            return;
        int len=arr.length;
        //i控制循環(huán)次數(shù)，因?yàn)橐呀?jīng)默認(rèn)第一個數(shù)的位置是正確的，所以i的起始值為1，i<len，循環(huán)len-1次
        for(int i=1;i<len;i++) {
            int j=i;//變量j用來記錄即將要排序的數(shù)的位置即目標(biāo)數(shù)的原位置
            int target=arr[j];//target用來記錄即將要排序的那個數(shù)的值即目標(biāo)值
            //while循環(huán)用來為目標(biāo)值在已經(jīng)排好序的數(shù)中找到合適的位置，
            //因?yàn)槭菑暮笙蚯氨容^，并且是與j-1位置的數(shù)比較，所以j>0
            while(j>0 && target<arr[j-1]) {
                //當(dāng)目標(biāo)數(shù)的值比它當(dāng)前位置的前一個數(shù)的值小時，將前一個數(shù)的位置向后移一位。
                //并且j--使得目標(biāo)數(shù)繼續(xù)與下一個元素比較
                arr[j]=arr[j-1];
                j--;
            }
            //更目標(biāo)數(shù)的位置。
            arr[j]=target;
            //打印每次循環(huán)結(jié)束之后數(shù)組的排序狀態(tài)（方便理解）
            System.out.println("第"+(i)+"次循環(huán)之后效果："+Arrays.toString(arr));
        }
    }

4.希爾排序

4.1 基本思想

希爾排序也稱為"縮小增量排序"，原理是先將需要排的數(shù)組分成多個子序列，這樣每個子序列的元素個數(shù)就很少，再分別對每個對子序列進(jìn)行插入排序。在該數(shù)組基本有序后 再進(jìn)行一次直接插入排序就能完成對整個數(shù)組的排序。所以，要采用跳躍分割的策略。這里引入“增量”的概念，將相距某個增量的記錄兩兩組合成一個子序列，然后對每個子序列進(jìn)行直接插入排序， 這樣得到的結(jié)果才會使基本有序（即小的在前邊，大的在后邊，不大不小的在中間）。希爾排序就是 直接插入排序的升級版。

4.2 圖片演示

希爾排序

4.3 代碼展示

public static void shellSort(int[] arr) {
        if(arr==null)
            return;
        int len=arr.length;//數(shù)組的長度
        int k=len/2;//初始的增量為數(shù)組長度的一半
        //while循環(huán)控制按增量的值來劃不同分子序列，每完成一次增量就減少為原來的一半
        //增量的最小值為1，即最后一次對整個數(shù)組做直接插入排序
        while(k>0) {
            //里邊其實(shí)就是升級版的直接插入排序了，是對每一個子序列進(jìn)行直接插入排序，
            //所以直接將直接插入排序中的‘1’變?yōu)椤甼’就可以了。
            for(int i=k;i<len;i++) {
                int j=i;
                int target=arr[i];
                while(j>=k && target<arr[j-k]) {
                    arr[j]=arr[j-k];
                    j-=k;
                }
                arr[j]=target;
            }
            //不同增量排序后的結(jié)果
            System.out.println("增量為"+k+"排序之后："+Arrays.toString(arr));
            k/=2;
        }
    }

5.歸并排序

5.1 基本思想

總體概括就是從上到下遞歸拆分，然后從下到上逐步合并。

遞歸拆分：先把待排序數(shù)組分為左右兩個子序列，再分別將左右兩個子序列拆分為四個子子序列，以此類推直到最小的子序列元素的個數(shù)為兩個或者一個為止。

逐步合并（一定要注意是從下到上層級合并，可以理解為遞歸的層級返回）：將最底層的最左邊的一個子序列排序，然后將從左到右第二個子序列進(jìn)行排序，再將這兩個排好序的子序列合并并排序，然后將最底層從左到右第三個子序列進(jìn)行排序..... 合并完成之后記憶完成了對數(shù)組的排序操作

5.2 圖片演示

歸并排序

5.3 代碼展示

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr= {3,8,6,2,1,8};
        mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 遞歸拆分
     * @param arr 待拆分?jǐn)?shù)組
     * @param left 待拆分?jǐn)?shù)組最小下標(biāo)
     * @param right 待拆分?jǐn)?shù)組最大下標(biāo)
     */
    public static void mergeSort(int[] arr,int left,int right) {
        int mid=(left+right)/2; //中間下標(biāo)
        if(left<right) {
            mergeSort(arr,left,mid);//遞歸拆分左邊
            mergeSort(arr,mid+1,right);//遞歸拆分右邊
            sort(arr,left,mid,right);//合并左右
        }
    }
    
    /**
     * 合并兩個有序子序列
     * @param arr 待合并數(shù)組
     * @param left 待合并數(shù)組最小下標(biāo)
     * @param mid 待合并數(shù)組中間下標(biāo)
     * @param right 待合并數(shù)組最大下標(biāo)
     */
    public static void sort(int[] arr,int left,int mid,int right) {
        int[] temp=new int[right-left+1]; //臨時數(shù)組，用來保存每次合并年之后的結(jié)果
        int i=left;
        int j=mid+1;
        int k=0;//臨時數(shù)組的初始下標(biāo)
        //這個while循環(huán)能夠初步篩選出待合并的了兩個子序列中的較小數(shù)
        while(i<=mid && j<=right) {
            if(arr[i]<=arr[j]) {
                temp[k++]=arr[i++];
            }else {
                temp[k++]=arr[j++];
            }
        }
        //將左邊序列中剩余的數(shù)放入臨時數(shù)組
        while(i<=mid) {
            temp[k++]=arr[i++];
        }
        //將右邊序列中剩余的數(shù)放入臨時數(shù)組
        while(j<=right) {
            temp[k++]=arr[j++];
        }
        //將臨時數(shù)組中的元素位置對應(yīng)到真真實(shí)的數(shù)組中
        for(int m=0;m<temp.length;m++) {
            arr[m+left]=temp[m];
        }
    }

6.快速排序

6.1 基本思想

快速排序也采用了分治的策略，這里引入了‘基準(zhǔn)數(shù)’的概念。

  1. 找一個基準(zhǔn)數(shù)（一般將待排序的數(shù)組的第一個數(shù)作為基準(zhǔn)數(shù)）
  2. 對數(shù)組進(jìn)行分區(qū)，將小于等于基準(zhǔn)數(shù)的全部放在左邊，大于基準(zhǔn)數(shù)的全部放在右邊。
  3. 重復(fù)1，2步驟，分別對左右兩個子分區(qū)進(jìn)行分區(qū)，一直到各分區(qū)只有一個數(shù)為止。

6.2 圖片演示

快速排序

6.3 代碼展示

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr= {72,6,57,88,60,42,83,73,48,85};
        quickSort(arr,0,9);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 分區(qū)過程
     * @param arr 待分區(qū)數(shù)組
     * @param left 待分區(qū)數(shù)組最小下標(biāo)
     * @param right 待分區(qū)數(shù)組最大下標(biāo)
     */
    public static void quickSort(int[] arr,int left,int right) {
        if(left<right) {
            int temp=qSort(arr,left,right);
            quickSort(arr,left,temp-1);
            quickSort(arr,temp+1,right);
        }
    }
    /**
     * 排序過程
     * @param arr 待排序數(shù)組
     * @param left 待排序數(shù)組最小下標(biāo)
     * @param right 待排序數(shù)組最大下標(biāo)
     * @return 排好序之后基準(zhǔn)數(shù)的位置下標(biāo)，方便下次的分區(qū)
     */
    public static int qSort(int[] arr,int left,int right) {
        int temp=arr[left];//定義基準(zhǔn)數(shù)，默認(rèn)為數(shù)組的第一個元素
        while(left<right) {//循環(huán)執(zhí)行的條件
            //因?yàn)槟J(rèn)的基準(zhǔn)數(shù)是在最左邊，所以首先從右邊開始比較進(jìn)入while循環(huán)的判斷條件
            //如果當(dāng)前arr[right]比基準(zhǔn)數(shù)大，則直接將右指針左移一位，當(dāng)然還要保證left<right
            while(left<right && arr[right]>temp) {
                right--;
            }
            //跳出循環(huán)說明當(dāng)前的arr[right]比基準(zhǔn)數(shù)要小，那么直接將當(dāng)前數(shù)移動到基準(zhǔn)數(shù)所在的位置，并且左指針向右移一位（left++）
            //這時當(dāng)前數(shù)（arr[right]）所在的位置空出，需要從左邊找一個比基準(zhǔn)數(shù)大的數(shù)來填充。
            if(left<right) {
                arr[left++]=arr[right];
            }
            //下面的步驟是為了在左邊找到比基準(zhǔn)數(shù)大的數(shù)填充到right的位置。
            //因?yàn)楝F(xiàn)在需要填充的位置在右邊，所以左邊的指針移動，如果arr[left]小于或者等于基準(zhǔn)數(shù)，則直接將左指針右移一位
            while(left<right && arr[left]<=temp) {
                left++;
            }
            //跳出上一個循環(huán)說明當(dāng)前的arr[left]的值大于基準(zhǔn)數(shù)，需要將該值填充到右邊空出的位置，然后當(dāng)前位置空出。
            if(left<right) {
                arr[right--]=arr[left];
            }
        }
        //當(dāng)循環(huán)結(jié)束說明左指針和右指針已經(jīng)相遇。并且相遇的位置是一個空出的位置，
        //這時候?qū)⒒鶞?zhǔn)數(shù)填入該位置，并返回該位置的下標(biāo)，為分區(qū)做準(zhǔn)備。
        arr[left]=temp;
        return left;
    }

7.堆排序

7.1 基本思想

在此之前要先說一下堆的概念，堆是一種特殊的完全二叉樹，分為大頂堆和小頂堆。

大頂堆：每個結(jié)點(diǎn)的值都大于它的左右子結(jié)點(diǎn)的值，升序排序用大頂堆。

小頂堆：每個結(jié)點(diǎn)的值都小于它的左右子結(jié)點(diǎn)的值，降序排序用小頂堆。

所以，需要先將待排序數(shù)組構(gòu)造成大頂堆的格式，這時候該堆的頂結(jié)點(diǎn)就是最大的數(shù)，將其與堆的最后一個結(jié)點(diǎn)的元素交換。再將剩余的樹重新調(diào)整成堆，再次首節(jié)點(diǎn)與尾結(jié)點(diǎn)交換，重復(fù)執(zhí)行直到只剩下最后一個結(jié)點(diǎn)完成排序。

7.2 圖片演示

堆排序

7.3 代碼展示

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr= {72,6,57,88,60,42,83,73,48,85};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        if(arr==null) {
            return;
        }
        int len=arr.length;
        //初始化大頂堆（從最后一個非葉節(jié)點(diǎn)開始，從左到右，由下到上）
        for(int i=len/2-1;i>=0;i--) {
            adjustHeap(arr,i,len);
        }
        //將頂節(jié)點(diǎn)和最后一個節(jié)點(diǎn)互換位置，再將剩下的堆進(jìn)行調(diào)整
        for(int j=len-1;j>0;j--) {
            swap(arr,0,j);
            adjustHeap(arr,0,j);
        }
    }
    
    /**
     * 整理樹讓其變成堆
     * @param arr 待整理的數(shù)組
     * @param i 開始的結(jié)點(diǎn)
     * @param j 數(shù)組的長度
     */
    public static void adjustHeap(int[] arr,int i,int j) {
        int temp=arr[i];//定義一個變量保存開始的結(jié)點(diǎn)
        //k就是該結(jié)點(diǎn)的左子結(jié)點(diǎn)下標(biāo)
        for(int k=2*i+1;k<j;k=2*k+1) {
            //比較左右兩個子結(jié)點(diǎn)的大小，k始終記錄兩者中較大值的下標(biāo)
            if(k+1<j && arr[k]<arr[k+1]) {
                k++;
            }
            //經(jīng)子結(jié)點(diǎn)中的較大值和當(dāng)前的結(jié)點(diǎn)比較，比較結(jié)果的較大值放在當(dāng)前結(jié)點(diǎn)位置
            if(arr[k]>temp) {
                arr[i]=arr[k];
                i=k;
            }else{//說明已經(jīng)是大頂堆
                break;
            }
        }
        arr[i]=temp;
    }
    
    /**
     * 交換數(shù)據(jù)
     * @param arr 
     * @param num1
     * @param num2
     */
    public static void swap(int[] arr, int num1,int num2) {
        int temp=arr[num1];
        arr[num1]=arr[num2];
        arr[num2]=temp;
    }

8.計(jì)數(shù)排序

8.1 基本思想

計(jì)數(shù)排序采用了一種全新的思路，不再是通過比較來排序，而是將待排序數(shù)組中的最大值+1作為一個臨時數(shù)組的長度，然后用臨時數(shù)組記錄待排序數(shù)組中每個元素出現(xiàn)的次數(shù)。最后再遍歷臨時數(shù)組，因?yàn)槭巧颍詮那暗胶蟊闅v，將臨時數(shù)組中值>0的數(shù)的下標(biāo)循環(huán)取出，依次放入待排序數(shù)組中，即可完成排序。計(jì)數(shù)排序的效率很高，但是實(shí)在犧牲內(nèi)存的前提下，并且有著限制，那就是待排序數(shù)組的值必須 限制在一個確定的范圍。

8.2 圖片演示

計(jì)數(shù)排序

8.3 代碼展示

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr= {72,6,57,88,60,42,83,73,48,85};
        countSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void countSort(int[] arr) {
        if(arr==null)
            return;
        int len=arr.length;
        //保存待排序數(shù)組中的最大值，目的是確定臨時數(shù)組的長度（必須）
        int maxNum=arr[0];
        //保存待排序數(shù)組中的最小值，目的是確定最終遍歷臨時數(shù)組時下標(biāo)的初始值（非必需，只是這樣可以加快速度，減少循環(huán)次數(shù)）
        int minNum=arr[0];
        //for循環(huán)就是為了找到待排序數(shù)組的最大值和最小值
        for(int i=1;i<len;i++) {
            maxNum=maxNum>arr[i]?maxNum:arr[i];
            minNum=minNum<arr[i]?minNum:arr[i];
        }
        //創(chuàng)建一個臨時數(shù)組
        int[] temp=new int[maxNum+1];
        //for循環(huán)是為了記錄待排序數(shù)組中每個元素出現(xiàn)的次數(shù)，并將該次數(shù)保存到臨時數(shù)組中
        for(int i=0;i<len;i++) {
            temp[arr[i]]++;
        }
        //k=0用來記錄待排序數(shù)組的下標(biāo)
        int k=0;
        //遍歷臨時數(shù)組，重新為待排序數(shù)組賦值。
        for(int i=minNum;i<temp.length;i++) {
            while(temp[i]>0) {
                arr[k++]=i;
                temp[i]--;
            }
        }
    }

9.桶排序

9.1 基本思想

桶排序其實(shí)就是計(jì)數(shù)排序的強(qiáng)化版，需要利用一個映射函數(shù)首先定義有限個數(shù)個桶，然后將待排序數(shù)組內(nèi)的元素按照函數(shù)映射的關(guān)系分別放入不同的桶里邊，現(xiàn)在不同的桶里邊的數(shù)據(jù)已經(jīng)做了區(qū)分，比如A桶里的數(shù)要么全部大于B桶，要么全部小于B桶里的數(shù)。但是A，B桶各自里邊的數(shù)還是亂序的。所以要借助其他排序方式（快速，插入，歸并）分別對每一個元素個數(shù)大于一的桶里邊的數(shù)據(jù)進(jìn)行排序。最后再將桶里邊的元素按照順序依次放入待排序數(shù)組中即可。

9.2 圖片演示

桶排序

9.3 代碼展示

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr= {72,6,57,88,60,42,83,73,48,85};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void bucketSort(int[] arr) {
        if(arr==null)
            return;
        int len=arr.length;
        //定義桶的個數(shù)，這里k的值要視情況而定，這里我們假設(shè)待排序數(shù)組里的數(shù)都是[0,100)之間的。
        int k=10;
        //用嵌套集合來模擬桶，外層集合表示桶，內(nèi)層集合表示桶里邊裝的元素。
        List<List<Integer>> bucket=new ArrayList<>();
        //for循環(huán)初始化外層集合即初始化桶
        for(int i=0;i<k;i++){
            bucket.add(new ArrayList<>());
        }
        //循環(huán)是為了將待排序數(shù)組中的元素通過映射函數(shù)分別放入不同的桶里邊
        for(int i=0;i<len;i++) {
            bucket.get(mapping(arr[i])).add(arr[i]);
        }
        //這個循環(huán)是為了將所有的元素個數(shù)大于1的桶里邊的數(shù)據(jù)進(jìn)行排序。
        for(int i=0;i<k;i++) {
            if(bucket.size()>1) {
                //因?yàn)檫@里是用集合來模擬的桶所以用java寫好的對集合排序的方法。
                //其實(shí)應(yīng)該自己寫一個方法來排序的。
                Collections.sort(bucket.get(i));
            }
             
        }
        //將排好序的數(shù)重新放入待排序數(shù)組中
        int m=0;
        for(List<Integer> list:bucket) {
            if(list.size()>0) {
                for(Integer a:list) {
                    arr[m++]=a;
                }
            }
        }
    }
    /**
     * 映射函數(shù)
     * @param num
     * @return 
     */
    public static int mapping(int num) {
        return num/10;
    }

10.基數(shù)排序

10.1基本思想

就是將待排序數(shù)據(jù)拆分成多個關(guān)鍵字進(jìn)行排序，也就是說，基數(shù)排序的實(shí)質(zhì)是多關(guān)鍵字排序。多關(guān)鍵字排序的思路是將待排數(shù)據(jù)里德排序關(guān)鍵字拆分成多個排序關(guān)鍵字； 第1個排序關(guān)鍵字，第2個排序關(guān)鍵字，第3個排序關(guān)鍵字......然后，根據(jù)子關(guān)鍵字對待排序數(shù)據(jù)進(jìn)行排序。

10.2 圖片演示

基數(shù)排序

10.3 代碼展示

public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr= {720,6,57,88,60,42,83,73,48,85};
        redixSort(arr,10,3);
        System.out.println(Arrays.toString(arr));
    }

    public static void redixSort(int[] arr, int radix, int d) {  
        // 緩存數(shù)組  
        int[] tmp = new int[arr.length];  
        // buckets用于記錄待排序元素的信息  
        // buckets數(shù)組定義了max-min個桶  
        int[] buckets = new int[radix];  
  
        for (int i = 0, rate = 1; i < d; i++) {  
  
            // 重置count數(shù)組，開始統(tǒng)計(jì)下一個關(guān)鍵字  
            Arrays.fill(buckets, 0);  
            // 將data中的元素完全復(fù)制到tmp數(shù)組中  
            System.arraycopy(arr, 0, tmp, 0, arr.length);  
  
            // 計(jì)算每個待排序數(shù)據(jù)的子關(guān)鍵字  
            for (int j = 0; j < arr.length; j++) {  
                int subKey = (tmp[j] / rate) % radix;  
                buckets[subKey]++;  
            }  
  
            for (int j = 1; j < radix; j++) {  
                buckets[j] = buckets[j] + buckets[j - 1];  
            }  
  
            // 按子關(guān)鍵字對指定的數(shù)據(jù)進(jìn)行排序  
            for (int m = arr.length - 1; m >= 0; m--) {  
                int subKey = (tmp[m] / rate) % radix;  
                arr[--buckets[subKey]] = tmp[m];  
            }  
            rate *= radix;  
        }  
    }

參考資料

  1. https://www.cnblogs.com/onepixel/articles/7674659.html
  2. https://blog.csdn.net/apei830/article/details/6596104
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容