基數排序是非比較排序算法,算法的時間複雜度是o(n). 相比于快速排序的o(nlgn),從表面上看具有不小的優勢.但事實上可能有些出入,因為基數排序的n可能具有比較大的系數k.是以在具體的應用中,應首先對這個排序函數的效率進行評估。
基數排序不僅僅隻用在數字的排序上，由于關鍵字的不同，可以選擇不同的排序方式。要想采用基數排序，我們需要至少兩種關鍵字，而且要依照關鍵字的優先級從低到高的順序進行操作。
在數字問題上，要得到一個數列排序: 42 58 5 32，這樣的數字，我們可以通過個位與十位來進行排序，分為兩個桶子，分别為0~9的個位和0~9的十位。 具體的排序過程(紅色字型表示正在排序的數位)如下：
第一次排序(個位):
桶的編号：0 1 2 3 4 5 6 7 8 9
個數： 0 0 2 0 0 1 0 0 1 0
收集桶：42 32 5 58
第二次排序(十位):
個數： 1 0 0 1 1 0 0 0 0 0
收集桶：5 32 42 58
還可以用在其他問題上，例如，我們要把52張四種花色的撲克牌進行依次從小到大的排序，其中黑桃<紅桃<方片<梅花。
這個問題的話，關鍵字為0~k和花色，而且花色的優先級大于數字，是以我們要先選擇數字0~k先做一次排序，也就是分13個桶，分為标記為0~k，這樣每個桶内就存在不同的四張花色的牌，這樣我們收集起來了，然後我們再分4個桶，标記為不同的花色，然後把13個标記為數字的桶中的撲克牌依次放進這些桶内，最終我們可以不通過比較數字的大小和花色，就可以得到排序的結果了。
基數排序