前言

首先這里列出的大家熟知的排序算法：冒泡排序、插入排序、歸并排序、堆排序、快速排序等。對(duì)于能在O(n lgn)時(shí)間內(nèi)進(jìn)行排序的算法，歸并排序和堆排序達(dá)到了最壞的情況下的上界；快速排序在平均情況下達(dá)到了該上界。

這些算法都有一個(gè)共同點(diǎn)：在排序的最終結(jié)果中，各元素的次序依賴于它們之間的比較。我們稱這類排序算法為比較排序。

比較排序在排序的排序過程可以抽象成一棵決策樹。在最壞的情況下，任何比較排序算法都需要做Ω（n lgn）次比較。

線性時(shí)間排序

下面介紹兩種線性時(shí)間排序的算法：計(jì)數(shù)排序、基數(shù)排序。

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

計(jì)數(shù)排序假設(shè)n個(gè)輸入的元素中每一個(gè)都是在[0，k]區(qū)間內(nèi)的一個(gè)整數(shù)，其中k為某個(gè)整數(shù)。當(dāng)k=O(n)時(shí)，排序的運(yùn)行時(shí)間為θ(n)。

計(jì)數(shù)排序執(zhí)行過程：

1. 開辟計(jì)數(shù)數(shù)組空間，并遍歷待排序數(shù)組對(duì)帶排序數(shù)組進(jìn)行計(jì)數(shù)賦值；
2. 對(duì)計(jì)數(shù)數(shù)組進(jìn)行疊加操作，得到元素所在的最后的位置；
3. 遍歷待排序數(shù)組，根據(jù)得出的計(jì)數(shù)數(shù)組完成輸出數(shù)組的賦值；

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

計(jì)數(shù)排序Java 代碼：

    /**
     * 
     * @param a 數(shù)組
     * @param k 范圍;例如 k equals 5 ,range is [0,4]
     */
    public void countingSort(int[] a,int[] b,int k) {
        
        if(k<0||(a==null||a.length<1)) return;
        int[] c=new int[k];
        
        //counting
        for(int j=0;j<a.length;j++) {
            c[a[j]]+=1;
        }
        
        //convert
        for(int i=1;i<k;i++) {
            c[i]=c[i]+c[i-1];
        }
        
        for(int j=(a.length-1);j>=0;j--) {
            b[c[a[j]]-1]=a[j];
            c[a[j]]-=1;
        }
        
    }

測(cè)試代碼：

    public static void main(String[] args) {
        //假設(shè)a數(shù)組中的數(shù)都是[0,10)之間的數(shù)
        int[] a= {4,6,3,3,2,2,9,0,1,4,4,8,7,7};
        //排序數(shù)組
        int[] b=new int[a.length];
        new RadixSort().countingSort(a, b, 10);
        for(int i=0;i<b.length;i++) {
            System.out.println(i+" is "+b[i]);
        }
    }

測(cè)試結(jié)果：

0 is 0
1 is 1
2 is 2
3 is 2
4 is 3
5 is 3
6 is 4
7 is 4
8 is 4
9 is 6
10 is 7
11 is 7
12 is 8
13 is 9

基數(shù)排序

基數(shù)排序是先按最低有效位進(jìn)行排序解決排序問題，算法用到了穩(wěn)定排序算法-計(jì)數(shù)排序。
基數(shù)排序的偽代碼很簡(jiǎn)單：

RADIX_SORT(A,d)
  for i =1 to d
    use a stable sort to sort array A on digit i;

基數(shù)排序排序過程

基數(shù)排序Java 代碼：

    /**
     * 10的次方數(shù)的結(jié)果值
     * @param d 次方數(shù)
     * @return 10的n次方的結(jié)果
     */
    private int tenPow(int d) {
        int result=1;
        for(int i=0;i<d;i++) {
            result*=10;
        }
        return result;
    }

    /**
     * 為計(jì)數(shù)排序優(yōu)化的計(jì)數(shù)排序
     * @param a 待排序數(shù)組
     * @param b 輸出的數(shù)組
     * @param k 范圍;例如 k equals 5 ,range is [0,9]
     */
    public void countingSort4Radix(int[] a,int[] b,int k) {
        
        
        if(k<0||(a==null||a.length<1)) return;
        
        int[] temps=new int[a.length];
        for(int x=0;x<temps.length;x++) {//copying
            temps[x]=b[x];
        }

        int[] c=new int[k];
        
        //counting
        for(int j=0;j<a.length;j++) {
            c[a[j]]+=1;
        }
        
        //convert
        for(int i=1;i<k;i++) {
            c[i]=c[i]+c[i-1];
        }
        
        for(int j=(a.length-1);j>=0;j--) {
            b[c[a[j]]-1]=temps[j];
            c[a[j]]-=1;
        }
        
    }
    

    /**
     * 基數(shù)排序
     * @param a 待排序數(shù)組
     * @param d 位數(shù) 如：834102 d eauals 6
     */
    public void radixSort(int[] a,int d) {
        
        //存放相應(yīng)位數(shù)據(jù)的臨時(shí)數(shù)組
        int[] digitsTemp=new int[a.length];
        
        for(int j=0;j<d;j++) {
            
            //1.為相應(yīng)位賦值
            for(int i=0;i<digitsTemp.length;i++) {
                digitsTemp[i]=(a[i]/tenPow(j))%10;
                System.out.println((j+1)+"位："+"digitsTemp["+i+"] is "+ digitsTemp[i]);
            }
            
            //2.使用穩(wěn)定的計(jì)數(shù)排序算法進(jìn)行從低位到高位的按位排序
            countingSort4Radix(digitsTemp, a, 10);
            
            for(int x=0;x<a.length;x++) {
                System.out.println(" radixing->"+x+" is "+a[x]);
            }

        }
        
    }
    

測(cè)試代碼：

    public static void main(String[] args) {

        int[] x= {834102,634101,834112,512311};
        new RadixSort().radixSort(x, 6);
        
        System.out.println("-------基數(shù)排序的結(jié)果-------");

        for(int i=0;i<x.length;i++) {
            System.out.println(i+" is "+x[i]);
        }
    }

測(cè)試結(jié)果：

1位：digitsTemp[0] is 2
1位：digitsTemp[1] is 1
1位：digitsTemp[2] is 2
1位：digitsTemp[3] is 1
 radixing->0 is 634101
 radixing->1 is 512311
 radixing->2 is 834102
 radixing->3 is 834112
2位：digitsTemp[0] is 0
2位：digitsTemp[1] is 1
2位：digitsTemp[2] is 0
2位：digitsTemp[3] is 1
 radixing->0 is 634101
 radixing->1 is 834102
 radixing->2 is 512311
 radixing->3 is 834112
3位：digitsTemp[0] is 1
3位：digitsTemp[1] is 1
3位：digitsTemp[2] is 3
3位：digitsTemp[3] is 1
 radixing->0 is 634101
 radixing->1 is 834102
 radixing->2 is 834112
 radixing->3 is 512311
4位：digitsTemp[0] is 4
4位：digitsTemp[1] is 4
4位：digitsTemp[2] is 4
4位：digitsTemp[3] is 2
 radixing->0 is 512311
 radixing->1 is 634101
 radixing->2 is 834102
 radixing->3 is 834112
5位：digitsTemp[0] is 1
5位：digitsTemp[1] is 3
5位：digitsTemp[2] is 3
5位：digitsTemp[3] is 3
 radixing->0 is 512311
 radixing->1 is 634101
 radixing->2 is 834102
 radixing->3 is 834112
6位：digitsTemp[0] is 5
6位：digitsTemp[1] is 6
6位：digitsTemp[2] is 8
6位：digitsTemp[3] is 8
 radixing->0 is 512311
 radixing->1 is 634101
 radixing->2 is 834102
 radixing->3 is 834112

-------基數(shù)排序的結(jié)果-------
0 is 512311
1 is 634101
2 is 834102
3 is 834112

總結(jié)

1. 計(jì)數(shù)排序 適用于k比較小的場(chǎng)景下，比如“某大型企業(yè)有兩萬名員工，希望根據(jù)年齡為員工們排序，并計(jì)算平均年齡？”，這個(gè)問題在不使用數(shù)據(jù)庫(kù)和磁盤相關(guān)算法（B樹）的前提下，計(jì)數(shù)排序是較優(yōu)的解決方案。
2. 基數(shù)排序是一種原地排序算法，不需要額外的空間進(jìn)行輔助；但是我的代碼中計(jì)數(shù)排序是還是開辟了空間，這是一個(gè)值得優(yōu)化的點(diǎn)。

以上，謝謝閱讀，希望你有所收獲！

算法導(dǎo)論公開課筆記（一）算法分析與設(shè)計(jì)
算法導(dǎo)論公開課筆記（二）快速排序和隨機(jī)化算法
算法導(dǎo)論公開課筆記（三）線性時(shí)間排序
算法導(dǎo)論公開課筆記（四）順序統(tǒng)計(jì)、中值
動(dòng)態(tài)規(guī)劃算法

竟然有人，為這個(gè)文章贊賞了￥2.0，雖然寫博客的目的不是為了掙錢，但是也好開心?。。?br> 謝謝匿名的大神的鼓勵(lì)，事事順利！