排序方法的時間複雜度：穩定排序算法有哪些

基數排序（Radix Sort）：是一種非比較型的整數排序算法。

基數排序的基本原理是，按照整數的每個位數分組。在分組過程中，對於不足位的數據用0補位。

基數排序按照對位數分組的順序的不同，可以分為LSD基數排序和MSD基數排序。

LSD基數排序，是按照從低位到高位的順序進行分組排序。例如：1,2,3,4,5,6,7,8,9,10第一次分組後為 10,1,2,3,4,5,6,7,8,9。

MSD基數排序，是按照從高位到低位的順序進行分組排序。例如：1,2,3,4,5,6,7,8,9,10 第一次分組以後為 1,10,2,3,4,5,6,7,8,9。

上述兩種方式不僅僅是對位數分組順序不同，其實現原理也是不同的。這裡我們只先介紹LSD基數排序。

首先我們看LSD基數排序是如何進行的

對於序列中的每個整數的每一位都可以看成是一個桶，而該位上的數字就可以認為是這個桶的鍵值。這句話應該怎麼理解呢，我們來看這樣的一個序列

170, 45, 75, 90, 802, 2, 24, 66

這是一個整數序列，我們知道，對於每個整數的每一位上的值肯定是介於0和9之間的。因此，要想對這個序列進行LSD排序，那就必須有10個桶。這10個桶的索引分別就是0——9這十個數。對於LSD基數排序來說，每一次分組過程就是將相應的整數放進相應的桶中。

拿第一次分組來說吧，對於每個整數要按照個位上的數進行分組。那麼我們看170，其個位為0，所以說170應該放進0這個桶中。然後以此類推 45放在5這個桶中。

所以上述序列的第一次分組後，各個整數所在的桶如下

0: 170, 090
1: 空
2: 802, 002
3: 空
4: 024
5: 045, 075
6: 066
7–9: 空

然後再將這些數依次收集起來，第一次分組再組合以後的序列為

170, 90, 802, 2, 24, 45, 75, 66

接着就是針對十位上的數進行分組入桶，入桶的情況如下

0: 802, 002
1: 空
2: 024
3: 空
4: 045
5: 空
6: 066
7: 170, 075
8: 空
9: 090

再次整理起來以後為下面的序列

802, 2, 24, 45, 66, 170, 75, 90

最後再次進行第三次（百位上的數）分組入桶

0: 002, 024, 045, 066, 075, 090
1: 170
2–7: 空
8: 802
9: 空

整理起來以後，我們發現整個序列已經是有序的了

2, 24, 45, 66, 75, 90, 170, 802

整個LSD基數排序的過程就是這樣的，當然不同的程序可以構造不同的存放數據的桶的形式。但是其原理是相同的。

LSD基數排序是一個快速的穩定排序算法。其時間複雜度可以表示為O(Kn)。其中n就是待排序序列的元素個數，K是數字的位數。對於這個K我們應該怎樣理解這個需要為大家說明一下。有時候K可以看做是一個常數——對於上述例子，其中K就是3。因為在上面的例子中最大的數是802，該數有3位。因此，在這種情況下，基數排序要比任何比較型的排序算法的效率要高。因為在比較型的排序算法中，最優的排序算法的時間複雜度也是O（nlogn）。

但是在一般情況下，K並不能再被認為是個常數。那K應該是什麼呢。這裡我們以十進制的數為例。整數序列中的每個數是以10為底的數。不妨我們用b記為底數，即b=10。那如果整個整數序列中的最大數是N。那這就很容易看出，K= logbN。所以在一般情況下，基數排序的時間複雜度可以看做是O（n logbN）。在N非常大的情況下是不是基數排序的效率要低於比最優的比較型的排序算法（最優的比較型的排序算法的時間複雜度是O（nlogn））。現在讓我們假設N <= nc ，這裡c是一個常數。這種情況下基數排序的時間複雜度就變成了O（n logbn）。但是即使這樣，也不能比複雜度是O（nlogn）的比較型排序算法更快。那如果我們使b的值變大呢？如果我們使得b的值為n的話，這樣基數排序的時間複雜度是不是就變成了線性的了，即O（n）。也就是說，如果待排序的序列的數是以n為底的話，那序列中的數可以是1到nc 之間的數。其時間複雜度就是線性的。

好了，對於基數排序的效率問題，我們就先討論到這裡。接下來就該進入我們的核心問題——LSD基數排序代碼的實現。

/**
 * 找到序列中最大位數
 */
function FindMaxBit($arr){
    /*
     * 首先查找序列中最大的數
     */
    $p = $arr[0];
    for($i=1;$i<count($arr);$i++){
        if($arr[$i]>=$p){
            $p = $arr[$i];
        }
    }
    //得到最大的數以後，計算出該數據有多少位
    $d = 1;
    while(floor($p/10)>0){
        $d++;
        $p = floor($p/10);
    }
    return $d;
}
function LSD_RadixSort(&$arr){
    //得到序列中最大位數
    $d = FindMaxBit($arr);
    $bucket = array();
    //初始化隊列
    for($i=0;$i<10;$i++){
        $bucket[$i]=array('num'=>0,'val'=>array());
    }
    /*
     * 開始進行分配
     */
    $radix = 1;
    for($i=1;$i<=$d;$i++){
        for($j=0;$j<count($arr);$j++){
            $k = floor($arr[$j]/$radix)%10;
            $bucket[$k]['num']++;
            array_push($bucket[$k]['val'],$arr[$j]);
        }
        $arr = array();
        foreach ($bucket as $key => $val) {
            for ($j = 0; $j < $val['num']; $j ++) {
                $arr[] = $val['val'][$j];
            }
        }
        for($l=0;$l<10;$l++){
            $bucket[$l]=array('num'=>0,'val'=>array());
        }
        $radix *= 10;
    }
}
$arr = array(
    15,77,23,43,90,87,68,32,11,22,33,99,88,66,44,113,
    224,765,980,159,456,7,998,451,96,0,673,82,91,100
);
LSD_RadixSort($arr,0,count($arr)-1);
print_r($arr);

在上面的代碼中，我是將實際的數據直接存放在桶中了。然後將桶中的數據按照順序覆蓋掉原隊列中的數據。然後再次將被覆蓋後的隊列進行分組，依次進行下去。

當然還有一種方式就是，申請一個和原序列相同大小的隊列（不妨成為臨時隊列），然後再申請一個用於作桶的數組。桶中只是存放原序列中的數在臨時隊列中的位置，然後將原序列中的數按照桶中的順序放入臨時隊列中。然後將臨時隊列整個賦值給原序列。

二者雖然實現方式不同，但是其空間複雜度是相同的。下面我們看後者應該如何用代碼實現。

function LSD_RadixSort(&$arr){
    //得到序列中最大位數
    $d = FindMaxBit($arr);
    $bucket = array();
    $temp = array();
    //初始化隊列
    for($i=0;$i<10;$i++){
        $bucket[$i] = 0;
    }
    /*
     * 開始進行分配
     */
    $radix = 1;
    for($i=1;$i<=$d;$i++){
        for($j=0;$j<count($arr);$j++){
            $k = floor($arr[$j]/$radix)%10;
            $bucket[$k]++;
        }
        //在桶中調整原序列在臨時隊列中的位置
        for($j=1;$j<10;$j++){
            $bucket[$j] += $bucket[$j-1];
        }
        for($j=count($arr)-1;$j>=0;$j--){
            $k = floor($arr[$j]/$radix)%10;
            $temp[--$bucket[$k]] = $arr[$j];
        }
        /*
         * 將臨時隊列賦值給原序列
         */
        for($j=0;$j<count($temp);$j++){
            $arr[$j] = $temp[$j];
        }
        for($j=0;$j<10;$j++){
            $bucket[$j] = 0;
        }
        $radix *= 10;
    }
}

上述就是對基數排序中LSD方式的基本介紹。