面試中常用的幾個基本算法整理記錄（二）

無意中看到了面試中的 10 大排序算法總結原文地址
記錄一下搅吁，方便查找吭练。

查找和排序算法是算法的入門知識诫龙，其經(jīng)典思想可以用于很多算法當中。因為其實現(xiàn)代碼較短鲫咽，應用較常見签赃。所以在面試中經(jīng)常會問到排序算法及其相關的問題。但萬變不離其宗分尸，只要熟悉了思想锦聊，靈活運用也不是難事。一般在面試中最陈嵘埽考的是快速排序和歸并排序尖昏，并且經(jīng)常有面試官要求現(xiàn)場寫出這兩種排序的代碼。對這兩種排序的代碼一定要信手拈來才行。還有插入排序、冒泡排序、堆排序、基數(shù)排序、桶排序等。面試官對于這些排序可能會要求比較各自的優(yōu)劣、各種算法的思想及其使用場景。還有要會分析算法的時間和空間復雜度。通常查找和排序算法的考察是面試的開始，如果這些問題回答不好，估計面試官都沒有繼續(xù)面試下去的興趣都沒了咱筛。所以想開個好頭就要把常見的排序算法思想及其特點要熟練掌握饲趋，有必要時要熟練寫出代碼龄砰。

接下來我們就分析一下常見的排序算法及其使用場景圃泡。限于篇幅风秤，某些算法的詳細演示和圖示請自行尋找詳細的參考。

冒泡排序

冒泡排序是最簡單的排序之一了，其大體思想就是通過與相鄰元素的比較和交換來把小的數(shù)交換到最前面。這個過程類似于水泡向上升一樣友题，因此而得名咆爽。舉個栗子梁棠，對5,3,8,6,4這個無序序列進行冒泡排序。首先從后向前冒泡凫海，4和6比較啰脚，把4交換到前面匀们，序列變成5,3,8,4,6。同理4和8交換露氮，變成5,3,4,8,6,3和4無需交換祖灰。5和3交換，變成3,5,4,8,6,3.這樣一次冒泡就完了沦辙，把最小的數(shù)3排到最前面了夫植。對剩下的序列依次冒泡就會得到一個有序序列。冒泡排序的時間復雜度為O(n^2)。

實現(xiàn)代碼：

// @Description:冒泡排序算法實現(xiàn)
public class BubbleSort {

public static void bubbleSort(int[] arr) {
    if(arr == null || arr.length == 0)
        return ;
    for(int i=0; i<arr.length-1; i++) {
        for(int j=arr.length-1; j>i; j--) {
            if(arr[j] < arr[j-1]) {
                swap(arr, j-1, j);
            }
        }
    }
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

}
選擇排序

選擇排序的思想其實和冒泡排序有點類似详民，都是在一次排序后把最小的元素放到最前面延欠。但是過程不同，冒泡排序是通過相鄰的比較和交換沈跨。而選擇排序是通過對整體的選擇由捎。舉個栗子，對5,3,8,6,4這個無序序列進行簡單選擇排序饿凛，首先要選擇5以外的最小數(shù)來和5交換狞玛，也就是選擇3和5交換，一次排序后就變成了3,5,8,6,4.對剩下的序列一次進行選擇和交換涧窒，最終就會得到一個有序序列心肪。其實選擇排序可以看成冒泡排序的優(yōu)化，因為其目的相同纠吴，只是選擇排序只有在確定了最小數(shù)的前提下才進行交換硬鞍，大大減少了交換的次數(shù)。選擇排序的時間復雜度為O(n^2)

實現(xiàn)代碼：

// Description:簡單選擇排序算法的實現(xiàn)
public class SelectSort {

public static void selectSort(int[] arr) {
    if(arr == null || arr.length == 0)
        return ;
    int minIndex = 0;
    for(int i=0; i<arr.length-1; i++) { //只需要比較n-1次
        minIndex = i;
        for(int j=i+1; j<arr.length; j++) { //從i+1開始比較戴已，因為minIndex默認為i了固该，i就沒必要比了。
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        if(minIndex != i) { //如果minIndex不為i糖儡，說明找到了更小的值伐坏，交換之。
            swap(arr, i, minIndex);
        }
    }

}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

}
插入排序

插入排序不是通過交換位置而是通過比較找到合適的位置插入元素來達到排序的目的的握联。相信大家都有過打撲克牌的經(jīng)歷桦沉，特別是牌數(shù)較大的。在分牌時可能要整理自己的牌拴疤，牌多的時候怎么整理呢永部？就是拿到一張牌，找到一個合適的位置插入呐矾。這個原理其實和插入排序是一樣的苔埋。舉個栗子，對5,3,8,6,4這個無序序列進行簡單插入排序蜒犯，首先假設第一個數(shù)的位置時正確的组橄，想一下在拿到第一張牌的時候，沒必要整理罚随。然后3要插到5前面玉工，把5后移一位，變成3,5,8,6,4.想一下整理牌的時候應該也是這樣吧淘菩。然后8不用動遵班，6插在8前面屠升，8后移一位，4插在5前面狭郑，從5開始都向后移一位腹暖。注意在插入一個數(shù)的時候要保證這個數(shù)前面的數(shù)已經(jīng)有序。簡單插入排序的時間復雜度也是O(n^2)翰萨。

實現(xiàn)代碼：

// Description:<p>簡單插入排序算法實現(xiàn)
public class InsertSort {

public static void insertSort(int[] arr) {
    if(arr == null || arr.length == 0)
        return ;

    for(int i=1; i<arr.length; i++) { //假設第一個數(shù)位置時正確的脏答；要往后移，必須要假設第一個亩鬼。

        int j = i;
        int target = arr[i]; //待插入的

        //后移
        while(j > 0 && target < arr[j-1]) {
            arr[j] = arr[j-1];
            j --;
        }

        //插入 
        arr[j] = target;
    }

}

}
快速排序

快速排序一聽名字就覺得很高端殖告，在實際應用當中快速排序確實也是表現(xiàn)最好的排序算法。冒泡排序雖然高端雳锋，但其實其思想是來自冒泡排序黄绩，冒泡排序是通過相鄰元素的比較和交換把最小的冒泡到最頂端，而快速排序是比較和交換小數(shù)和大數(shù)魄缚，這樣一來不僅把小數(shù)冒泡到上面同時也把大數(shù)沉到下面宝与。

舉個栗子：對5,3,8,6,4這個無序序列進行快速排序焚廊，思路是右指針找比基準數(shù)小的冶匹，左指針找比基準數(shù)大的，交換之咆瘟。

5,3,8,6,4 用5作為比較的基準嚼隘，最終會把5小的移動到5的左邊，比5大的移動到5的右邊袒餐。

5,3,8,6,4 首先設置i,j兩個指針分別指向兩端飞蛹，j指針先掃描（思考一下為什么？）4比5小停止灸眼。然后i掃描卧檐，8比5大停止。交換i,j位置焰宣。

5,3,4,6,8 然后j指針再掃描霉囚，這時j掃描4時兩指針相遇。停止匕积。然后交換4和基準數(shù)盈罐。

4,3,5,6,8 一次劃分后達到了左邊比5小，右邊比5大的目的闪唆。之后對左右子序列遞歸排序盅粪，最終得到有序序列。

上面留下來了一個問題為什么一定要j指針先動呢悄蕾？首先這也不是絕對的票顾，這取決于基準數(shù)的位置，因為在最后兩個指針相遇的時候，要交換基準數(shù)到相遇的位置奠骄。一般選取第一個數(shù)作為基準數(shù)霸旗，那么就是在左邊，所以最后相遇的數(shù)要和基準數(shù)交換戚揭，那么相遇的數(shù)一定要比基準數(shù)小诱告。所以j指針先移動才能先找到比基準數(shù)小的數(shù)。

快速排序是不穩(wěn)定的民晒，其時間平均時間復雜度是O(nlgn)精居。

實現(xiàn)代碼：

// Description:<p>實現(xiàn)快速排序算法</p>
public class QuickSort {
//一次劃分
public static int partition(int[] arr, int left, int right) {
int pivotKey = arr[left];
int pivotPointer = left;

    while(left < right) {
        while(left < right && arr[right] >= pivotKey)
            right --;
        while(left < right && arr[left] <= pivotKey)
            left ++;
        swap(arr, left, right); //把大的交換到右邊，把小的交換到左邊潜必。
    }
    swap(arr, pivotPointer, left); //最后把pivot交換到中間
    return left;
}

public static void quickSort(int[] arr, int left, int right) {
    if(left >= right)
        return ;
    int pivotPos = partition(arr, left, right);
    quickSort(arr, left, pivotPos-1);
    quickSort(arr, pivotPos+1, right);
}

public static void sort(int[] arr) {
    if(arr == null || arr.length == 0)
        return ;
    quickSort(arr, 0, arr.length-1);
}

public static void swap(int[] arr, int left, int right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

}
其實上面的代碼還可以再優(yōu)化靴姿，上面代碼中基準數(shù)已經(jīng)在pivotKey中保存了，所以不需要每次交換都設置一個temp變量磁滚，在交換左右指針的時候只需要先后覆蓋就可以了佛吓。這樣既能減少空間的使用還能降低賦值運算的次數(shù)。優(yōu)化代碼如下：

// Description:<p>實現(xiàn)快速排序算法</p>
public class QuickSort {

/**
 * 劃分
 * @param arr
 * @param left
 * @param right
 * @return
 */
public static int partition(int[] arr, int left, int right) {
    int pivotKey = arr[left];

    while(left < right) {
        while(left < right && arr[right] >= pivotKey)
            right --;
        arr[left] = arr[right]; //把小的移動到左邊
        while(left < right && arr[left] <= pivotKey)
            left ++;
        arr[right] = arr[left]; //把大的移動到右邊
    }
    arr[left] = pivotKey; //最后把pivot賦值到中間
    return left;
}

/**
 * 遞歸劃分子序列
 * @param arr
 * @param left
 * @param right
 */
public static void quickSort(int[] arr, int left, int right) {
    if(left >= right)
        return ;
    int pivotPos = partition(arr, left, right);
    quickSort(arr, left, pivotPos-1);
    quickSort(arr, pivotPos+1, right);
}

public static void sort(int[] arr) {
    if(arr == null || arr.length == 0)
        return ;
    quickSort(arr, 0, arr.length-1);
}

}
總結快速排序的思想：冒泡+二分+遞歸分治垂攘，慢慢體會维雇。。晒他。

堆排序

堆排序是借助堆來實現(xiàn)的選擇排序吱型，思想同簡單的選擇排序，以下以大頂堆為例陨仅。注意：如果想升序排序就使用大頂堆津滞，反之使用小頂堆。原因是堆頂元素需要交換到序列尾部灼伤。

首先触徐，實現(xiàn)堆排序需要解決兩個問題：

1. 如何由一個無序序列鍵成一個堆？

2. 如何在輸出堆頂元素之后狐赡，調(diào)整剩余元素成為一個新的堆撞鹉？

第一個問題，可以直接使用線性數(shù)組來表示一個堆猾警，由初始的無序序列建成一個堆就需要自底向上從第一個非葉元素開始挨個調(diào)整成一個堆孔祸。

第二個問題，怎么調(diào)整成堆发皿？首先是將堆頂元素和最后一個元素交換崔慧。然后比較當前堆頂元素的左右孩子節(jié)點，因為除了當前的堆頂元素穴墅，左右孩子堆均滿足條件惶室，這時需要選擇當前堆頂元素與左右孩子節(jié)點的較大者（大頂堆）交換温自，直至葉子節(jié)點。我們稱這個自堆頂自葉子的調(diào)整成為篩選皇钞。

從一個無序序列建堆的過程就是一個反復篩選的過程悼泌。若將此序列看成是一個完全二叉樹，則最后一個非終端節(jié)點是n/2取底個元素夹界，由此篩選即可馆里。舉個栗子：

49,38,65,97,76,13,27,49序列的堆排序建初始堆和調(diào)整的過程如下：

實現(xiàn)代碼：

// Description:<p>堆排序算法的實現(xiàn)，以大頂堆為例可柿。</p>
public class HeapSort {

/**
 * 堆篩選鸠踪，除了start之外，start~end均滿足大頂堆的定義复斥。
 * 調(diào)整之后start~end稱為一個大頂堆营密。
 * @param arr 待調(diào)整數(shù)組
 * @param start 起始指針
 * @param end 結束指針
 */
public static void heapAdjust(int[] arr, int start, int end) {
    int temp = arr[start];

    for(int i=2*start+1; i<=end; i*=2) {
        //左右孩子的節(jié)點分別為2*i+1,2*i+2

        //選擇出左右孩子較小的下標
        if(i < end && arr[i] < arr[i+1]) {
            i ++; 
        }
        if(temp >= arr[i]) {
            break; //已經(jīng)為大頂堆，=保持穩(wěn)定性目锭。
        }
        arr[start] = arr[i]; //將子節(jié)點上移
        start = i; //下一輪篩選
    }

    arr[start] = temp; //插入正確的位置
}

public static void heapSort(int[] arr) {
    if(arr == null || arr.length == 0)
        return ;

    //建立大頂堆
    for(int i=arr.length/2; i>=0; i--) {
        heapAdjust(arr, i, arr.length-1);
    }

    for(int i=arr.length-1; i>=0; i--) {
        swap(arr, 0, i);
        heapAdjust(arr, 0, i-1);
    }

}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

}
希爾排序

希爾排序是插入排序的一種高效率的實現(xiàn)评汰，也叫縮小增量排序。簡單的插入排序中痢虹，如果待排序列是正序時被去，時間復雜度是O(n)，如果序列是基本有序的世分，使用直接插入排序效率就非常高编振。希爾排序就利用了這個特點〕袈瘢基本思想是：先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄基本有序時再對全體記錄進行一次直接插入排序臀玄。

舉個栗子：

從上述排序過程可見瓢阴，希爾排序的特點是，子序列的構成不是簡單的逐段分割健无，而是將某個相隔某個增量的記錄組成一個子序列荣恐。如上面的例子，第一堂排序時的增量為5累贤，第二趟排序的增量為3叠穆。由于前兩趟的插入排序中記錄的關鍵字是和同一子序列中的前一個記錄的關鍵字進行比較，因此關鍵字較小的記錄就不是一步一步地向前挪動臼膏，而是跳躍式地往前移硼被，從而使得進行最后一趟排序時，整個序列已經(jīng)做到基本有序渗磅，只要作記錄的少量比較和移動即可嚷硫。因此希爾排序的效率要比直接插入排序高。

希爾排序的分析是復雜的，時間復雜度是所取增量的函數(shù)济欢，這涉及一些數(shù)學上的難題噪矛。但是在大量實驗的基礎上推出當n在某個范圍內(nèi)時，時間復雜度可以達到O(n^1.3)起暮。

實現(xiàn)代碼：

// Description:<p>希爾排序算法實現(xiàn)</p>
public class ShellSort {

/**
 * 希爾排序的一趟插入
 * @param arr 待排數(shù)組
 * @param d 增量
 */
public static void shellInsert(int[] arr, int d) {
    for(int i=d; i<arr.length; i++) {
        int j = i - d;
        int temp = arr[i];    //記錄要插入的數(shù)據(jù)  
        while (j>=0 && arr[j]>temp) {  //從后向前卖氨，找到比其小的數(shù)的位置   
            arr[j+d] = arr[j];    //向后挪動  
            j -= d;  
        }  

        if (j != i - d)    //存在比其小的數(shù) 
            arr[j+d] = temp;

    }
}

public static void shellSort(int[] arr) {
    if(arr == null || arr.length == 0)
        return ;
    int d = arr.length / 2;
    while(d >= 1) {
        shellInsert(arr, d);
        d /= 2;
    }
}

}
歸并排序

歸并排序是另一種不同的排序方法，因為歸并排序使用了遞歸分治的思想负懦，所以理解起來比較容易双泪。其基本思想是，先遞歸劃分子問題密似，然后合并結果焙矛。把待排序列看成由兩個有序的子序列，然后合并兩個子序列残腌，然后把子序列看成由兩個有序序列村斟。。抛猫。蟆盹。。倒著來看闺金，其實就是先兩兩合并逾滥，然后四四合并。败匹。寨昙。最終形成有序序列∠颇叮空間復雜度為O(n)舔哪，時間復雜度為O(nlogn)。

舉個栗子：

實現(xiàn)代碼：
// Description:<p>歸并排序算法的實現(xiàn)</p>
public class MergeSort {

public static void mergeSort(int[] arr) {
    mSort(arr, 0, arr.length-1);
}

/**
 * 遞歸分治
 * @param arr 待排數(shù)組
 * @param left 左指針
 * @param right 右指針
 */
public static void mSort(int[] arr, int left, int right) {
    if(left >= right)
        return ;
    int mid = (left + right) / 2;

    mSort(arr, left, mid); //遞歸排序左邊
    mSort(arr, mid+1, right); //遞歸排序右邊
    merge(arr, left, mid, right); //合并
}

/**
 * 合并兩個有序數(shù)組
 * @param arr 待合并數(shù)組
 * @param left 左指針
 * @param mid 中間指針
 * @param right 右指針
 */
public static void merge(int[] arr, int left, int mid, int right) {
    //[left, mid] [mid+1, right]
    int[] temp = new int[right - left + 1]; //中間數(shù)組

    int i = left;
    int j = mid + 1;
    int k = 0;
    while(i <= mid && j <= right) {
        if(arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
        }
    }

    while(i <= mid) {
        temp[k++] = arr[i++];
    }

    while(j <= right) {
        temp[k++] = arr[j++];
    }

    for(int p=0; p<temp.length; p++) {
        arr[left + p] = temp[p];
    }

}

}
計數(shù)排序

如果在面試中有面試官要求你寫一個O(n)時間復雜度的排序算法槽棍，你千萬不要立刻說：這不可能捉蚤！雖然前面基于比較的排序的下限是O(nlogn)。但是確實也有線性時間復雜度的排序炼七，只不過有前提條件缆巧，就是待排序的數(shù)要滿足一定的范圍的整數(shù)，而且計數(shù)排序需要比較多的輔助空間豌拙。其基本思想是陕悬，用待排序的數(shù)作為計數(shù)數(shù)組的下標，統(tǒng)計每個數(shù)字的個數(shù)姆蘸。然后依次輸出即可得到有序序列墩莫。

實現(xiàn)代碼：

// Description:<p>計數(shù)排序算法實現(xiàn)</p>
public class CountSort {

public static void countSort(int[] arr) {
    if(arr == null || arr.length == 0)
        return ;

    int max = max(arr);

    int[] count = new int[max+1];
    Arrays.fill(count, 0);

    for(int i=0; i<arr.length; i++) {
        count[arr[i]] ++;
    }

    int k = 0;
    for(int i=0; i<=max; i++) {
        for(int j=0; j<count[i]; j++) {
            arr[k++] = i;
        }
    }

}

public static int max(int[] arr) {
    int max = Integer.MIN_VALUE;
    for(int ele : arr) {
        if(ele > max)
            max = ele;
    }

    return max;
}

}
桶排序

桶排序算是計數(shù)排序的一種改進和推廣芙委，但是網(wǎng)上有許多資料把計數(shù)排序和桶排序混為一談。其實桶排序要比計數(shù)排序復雜許多狂秦。

對桶排序的分析和解釋借鑒這位兄弟的文章（有改動）：http://hxraid.iteye.com/blog/647759

桶排序的基本思想：

假設有一組長度為N的待排關鍵字序列K[1....n]灌侣。首先將這個序列劃分成M個的子區(qū)間(桶) 。然后基于某種映射函數(shù) 裂问，將待排序列的關鍵字k映射到第i個桶中(即桶數(shù)組B的下標 i) 侧啼，那么該關鍵字k就作為B[i]中的元素(每個桶B[i]都是一組大小為N/M的序列)。接著對每個桶B[i]中的所有元素進行比較排序(可以使用快排)堪簿。然后依次枚舉輸出B[0]….B[M]中的全部內(nèi)容即是一個有序序列痊乾。bindex=f(key) 其中，bindex 為桶數(shù)組B的下標(即第bindex個桶), k為待排序列的關鍵字椭更。桶排序之所以能夠高效哪审，其關鍵在于這個映射函數(shù)，它必須做到：如果關鍵字k1<k2虑瀑，那么f(k1)<=f(k2)湿滓。也就是說B(i)中的最小數(shù)據(jù)都要大于B(i-1)中最大數(shù)據(jù)。很顯然舌狗，映射函數(shù)的確定與數(shù)據(jù)本身的特點有很大的關系叽奥。

舉個栗子：

假如待排序列K= {49、 38 痛侍、 35朝氓、 97 、 76主届、 73 赵哲、 27、 49 }岂膳。這些數(shù)據(jù)全部在1—100之間誓竿。因此我們定制10個桶，然后確定映射函數(shù)f(k)=k/10谈截。則第一個關鍵字49將定位到第4個桶中(49/10=4)。依次將所有關鍵字全部堆入桶中涧偷，并在每個非空的桶中進行快速排序后得到如圖所示簸喂。只要順序輸出每個B[i]中的數(shù)據(jù)就可以得到有序序列了。

桶排序分析：

桶排序利用函數(shù)的映射關系燎潮，減少了幾乎所有的比較工作喻鳄。實際上，桶排序的f(k)值的計算确封，其作用就相當于快排中劃分除呵，希爾排序中的子序列再菊，歸并排序中的子問題，已經(jīng)把大量數(shù)據(jù)分割成了基本有序的數(shù)據(jù)塊(桶)颜曾。然后只需要對桶中的少量數(shù)據(jù)做先進的比較排序即可纠拔。

對N個關鍵字進行桶排序的時間復雜度分為兩個部分：

(1) 循環(huán)計算每個關鍵字的桶映射函數(shù)，這個時間復雜度是O(N)泛豪。

(2) 利用先進的比較排序算法對每個桶內(nèi)的所有數(shù)據(jù)進行排序稠诲，其時間復雜度為 ∑ O(Ni*logNi) 。其中Ni 為第i個桶的數(shù)據(jù)量诡曙。

很顯然臀叙，第(2)部分是桶排序性能好壞的決定因素。盡量減少桶內(nèi)數(shù)據(jù)的數(shù)量是提高效率的唯一辦法(因為基于比較排序的最好平均時間復雜度只能達到O(N*logN)了)价卤。因此劝萤，我們需要盡量做到下面兩點：

(1) 映射函數(shù)f(k)能夠?qū)個數(shù)據(jù)平均的分配到M個桶中，這樣每個桶就有[N/M]個數(shù)據(jù)量慎璧。

(2) 盡量的增大桶的數(shù)量床嫌。極限情況下每個桶只能得到一個數(shù)據(jù)，這樣就完全避開了桶內(nèi)數(shù)據(jù)的“比較”排序操作炸卑。當然既鞠，做到這一點很不容易，數(shù)據(jù)量巨大的情況下盖文，f(k)函數(shù)會使得桶集合的數(shù)量巨大嘱蛋，空間浪費嚴重。這就是一個時間代價和空間代價的權衡問題了五续。

對于N個待排數(shù)據(jù)洒敏，M個桶，平均每個桶[N/M]個數(shù)據(jù)的桶排序平均時間復雜度為：

O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-N*logM)

當N=M時疙驾，即極限情況下每個桶只有一個數(shù)據(jù)時凶伙。桶排序的最好效率能夠達到O(N)。

總結： 桶排序的平均時間復雜度為線性的O(N+C)它碎，其中C=N*(logN-logM)函荣。如果相對于同樣的N，桶數(shù)量M越大扳肛，其效率越高傻挂，最好的時間復雜度達到O(N)。 當然桶排序的空間復雜度 為O(N+M)挖息，如果輸入數(shù)據(jù)非常龐大金拒，而桶的數(shù)量也非常多，則空間代價無疑是昂貴的套腹。此外绪抛，桶排序是穩(wěn)定的资铡。

實現(xiàn)代碼：

// Description:<p>桶排序算法實現(xiàn)</p>
public class BucketSort {

public static void bucketSort(int[] arr) {
    if(arr == null && arr.length == 0)
        return ;

    int bucketNums = 10; //這里默認為10，規(guī)定待排數(shù)[0,100)
    List<List<Integer>> buckets = new ArrayList<List<Integer>>(); //桶的索引

    for(int i=0; i<10; i++) {
        buckets.add(new LinkedList<Integer>()); //用鏈表比較合適
    }

    //劃分桶
    for(int i=0; i<arr.length; i++) {
        buckets.get(f(arr[i])).add(arr[i]);
    }

    //對每個桶進行排序
    for(int i=0; i<buckets.size(); i++) {
        if(!buckets.get(i).isEmpty()) {
            Collections.sort(buckets.get(i)); //對每個桶進行快排
        }
    }

    //還原排好序的數(shù)組
    int k = 0;
    for(List<Integer> bucket : buckets) {
        for(int ele : bucket) {
            arr[k++] = ele;
        }
    }
}

/**
 * 映射函數(shù)
 * @param x
 * @return
 */
public static int f(int x) {
    return x / 10;
}

}
基數(shù)排序

基數(shù)排序又是一種和前面排序方式不同的排序方式幢码，基數(shù)排序不需要進行記錄關鍵字之間的比較笤休。基數(shù)排序是一種借助多關鍵字排序思想對單邏輯關鍵字進行排序的方法蛤育。所謂的多關鍵字排序就是有多個優(yōu)先級不同的關鍵字宛官。比如說成績的排序，如果兩個人總分相同瓦糕，則語文高的排在前面底洗，語文成績也相同則數(shù)學高的排在前面。咕娄。亥揖。如果對數(shù)字進行排序，那么個位圣勒、十位费变、百位就是不同優(yōu)先級的關鍵字，如果要進行升序排序圣贸，那么個位挚歧、十位、百位優(yōu)先級一次增加吁峻』海基數(shù)排序是通過多次的收分配和收集來實現(xiàn)的，關鍵字優(yōu)先級低的先進行分配和收集用含。

舉個栗子：

實現(xiàn)代碼：

/**
*@Description:<p>基數(shù)排序算法實現(xiàn)</p>
*@author 王旭
*@time 2016-3-4 下午8:29:52
*/
public class RadixSort {

public static void radixSort(int[] arr) {
    if(arr == null && arr.length == 0)
        return ;

    int maxBit = getMaxBit(arr);

    for(int i=1; i<=maxBit; i++) {

        List<List<Integer>> buf = distribute(arr, i); //分配
        collecte(arr, buf); //收集
    }

}

/**
 * 分配
 * @param arr 待分配數(shù)組
 * @param iBit 要分配第幾位
 * @return
 */
public static List<List<Integer>> distribute(int[] arr, int iBit) {
    List<List<Integer>> buf = new ArrayList<List<Integer>>();
    for(int j=0; j<10; j++) {
        buf.add(new LinkedList<Integer>());
    }
    for(int i=0; i<arr.length; i++) {
        buf.get(getNBit(arr[i], iBit)).add(arr[i]);
    }
    return buf;
}

/**
 * 收集
 * @param arr 把分配的數(shù)據(jù)收集到arr中
 * @param buf 
 */
public static void collecte(int[] arr, List<List<Integer>> buf) {
    int k = 0;
    for(List<Integer> bucket : buf) {
        for(int ele : bucket) {
            arr[k++] = ele;
        }
    }

}

/**
 * 獲取最大位數(shù)
 * @param x
 * @return
 */
public static int getMaxBit(int[] arr) {
    int max = Integer.MIN_VALUE;
    for(int ele : arr) {
        int len = (ele+"").length();
        if(len > max)
            max = len;
    }
    return max;
}

/**
 * 獲取x的第n位矮慕，如果沒有則為0.
 * @param x
 * @param n
 * @return
 */
public static int getNBit(int x, int n) {

    String sx = x + "";
    if(sx.length() < n)
        return 0;
    else
        return sx.charAt(sx.length()-n) - '0';
}

}
總結

在前面的介紹和分析中我們提到了冒泡排序、選擇排序啄骇、插入排序三種簡單的排序及其變種快速排序痴鳄、堆排序、希爾排序三種比較高效的排序缸夹。后面我們又分析了基于分治遞歸思想的歸并排序還有計數(shù)排序痪寻、桶排序、基數(shù)排序三種線性排序虽惭。我們可以知道排序算法要么簡單有效槽华，要么是利用簡單排序的特點加以改進，要么是以空間換取時間在特定情況下的高效排序趟妥。但是這些排序方法都不是固定不變的，需要結合具體的需求和場景來選擇甚至組合使用佣蓉。才能達到高效穩(wěn)定的目的披摄。沒有最好的排序亲雪，只有最適合的排序。

下面就總結一下排序算法的各自的使用場景和適用場合疚膊。

1. 從平均時間來看义辕，快速排序是效率最高的，但快速排序在最壞情況下的時間性能不如堆排序和歸并排序寓盗。而后者相比較的結果是灌砖，在n較大時歸并排序使用時間較少，但使用輔助空間較多傀蚌。

2. 上面說的簡單排序包括除希爾排序之外的所有冒泡排序基显、插入排序、簡單選擇排序善炫。其中直接插入排序最簡單撩幽，但序列基本有序或者n較小時，直接插入排序是好的方法箩艺，因此常將它和其他的排序方法窜醉，如快速排序、歸并排序等結合在一起使用艺谆。

3. 基數(shù)排序的時間復雜度也可以寫成O(d*n)榨惰。因此它最使用于n值很大而關鍵字較小的的序列。若關鍵字也很大静汤，而序列中大多數(shù)記錄的最高關鍵字均不同琅催，則亦可先按最高關鍵字不同，將序列分成若干小的子序列撒妈，而后進行直接插入排序恢暖。

4. 從方法的穩(wěn)定性來比較，基數(shù)排序是穩(wěn)定的內(nèi)排方法狰右，所有時間復雜度為O(n*2)的簡單排序也是穩(wěn)定的杰捂。但是快速排序、堆排序棋蚌、希爾排序等時間性能較好的排序方法都是不穩(wěn)定的嫁佳。穩(wěn)定性需要根據(jù)具體需求選擇。

5. 上面的算法實現(xiàn)大多數(shù)是使用線性存儲結構谷暮，像插入排序這種算法用鏈表實現(xiàn)更好蒿往，省去了移動元素的時間。具體的存儲結構在具體的實現(xiàn)版本中也是不同的湿弦。

附：基于比較排序算法時間下限為O(nlogn)的證明：

基于比較排序下限的證明是通過決策樹證明的瓤漏，決策樹的高度Ω（nlgn），這樣就得出了比較排序的下限。

首先要引入決策樹蔬充。 首先決策樹是一顆二叉樹蝶俱，每個節(jié)點表示元素之間一組可能的排序，它予以京進行的比較相一致饥漫，比較的結果是樹的邊榨呆。 先來說明一些二叉樹的性質(zhì)，令T是深度為d的二叉樹庸队，則T最多有2^片樹葉积蜻。 具有L片樹葉的二叉樹的深度至少是logL。 所以彻消，對n個元素排序的決策樹必然有n!片樹葉（因為n個數(shù)有n!種不同的大小關系）竿拆，所以決策樹的深度至少是log(n!)，即至少需要log(n!)次比較证膨。 而 log(n!)=logn+log(n-1)+log(n-2)+…+log2+log1 >=logn+log(n-1)+log(n-2)+…+log(n/2) >=(n/2)log(n/2) >=(n/2)logn-n/2 =O(nlogn) 所以只用到比較的排序算法最低時間復雜度是O(nlogn)如输。