基數排序（Radix sort）是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。

一、算法基本思想

（1）基本思想

基數排序是基于桶排序來實現。通過鍵值的部分信息，將要排序的元素分配至某些“桶”中，以此達到排序的作用。

基數排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

（2）運行過程

基數排序算法（LSD）的運行過程如下：

1、根據待排序整數序列的進制d（十進制為10，十六進制為16...）設置d個桶，編號分別為0，1，...，d-1； 2、各個記錄按照其關鍵字最低位的值的大小放入到相應的桶中； 3、按照桶編號從小到大的順序收集各個桶中的數據，對于同一桶中的數據按照先后次序收集，先進桶先收集； 4、按照關鍵字的次低位，重復上述步驟...（沒有高位的數據則高位補0 ）按增量序列個數k，對序列進行k 趟排序；? 3）每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

（3）示例

二、算法實現（核心代碼）

Java實現：

public class RadixSort {public static void sort(int[] number, int d) //d表示最大的數有多少位{intk = 0;intn = 1;intm = 1; //控制鍵值排序依據在哪一位int[][]temp = newint[10][number.length]; //數組的第一維表示可能的余數0-9int[]order = newint[10]; //數組orderp[i]用來表示該位是i的數的個數while(m <= d){for(inti = 0; i < number.length; i++){intlsd = ((number[i] / n) % 10);temp[lsd][order[lsd]] = number[i];order[lsd]++;}for(inti = 0; i < 10; i++){if(order[i] != 0)for(intj = 0; j < order[i]; j++){number[k] = temp[i][j];k++;}order[i] = 0;}n *= 10;k = 0;m++;}}public static void main(String[] args){int[]data ={73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};RadixSort.sort(data, 3);for(inti = 0; i < data.length; i++){System.out.print(data[i] + "");}} }

三、性能（算法時間、空間復雜度、穩定性）分析

基數排序的時間復雜度是O(2*k*n)，其中n是排序元素個數，k是數字位數；空間復雜度采用數組是O(n*d)，采用鏈表是O(d+n)，d是進制（關鍵字的取值范圍）；是穩定的排序算法。

總結

以上是生活随笔為你收集整理的经典排序算法（10）——基数排序算法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。