大家好，我是烤鴨：????

???今天分享一下基礎排序算法之基數(shù)排序。

?

1.????基數(shù)排序：

原理：基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort。

將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列。

思路：

基數(shù)排序，即一個數(shù)位一個數(shù)位地進行排序，平常生活中我們經(jīng)常使用的一種算法思想：如要對一個日期進行排序，日期中由年、月、日組成的，對于這個問題，我們經(jīng)常使用的是先比較年份，如果相同再比較月份，如果還相同就比較日。

下面四個數(shù)進行排序：123、312、245、531

???個位?=>??十位?=>??百位

???531??????312??????123

? ?312? ? ??123? ? ??245

???123??????531??????312

???245??????245??????531

代碼實現(xiàn)：

/*** 基數(shù)排序* @param d* @param array* 時間復雜度 O的log2 N* 基數(shù)排序 運用二維數(shù)組來分別比較每一位，個位、十位、百位…* 輸入10個整數(shù)的數(shù)組*/private void radixSort(int d,int[] array){long nowTime = System.nanoTime();int n=1;//代表位數(shù)對應的數(shù)：1,10,100000...int k=0;//保存每一位排序后的結(jié)果用于下一位的排序輸入int[][] bucket=new int[10][array.length];//排序桶用于保存每次排序后的結(jié)果，這一位上排序結(jié)果相同的數(shù)字放在同一個桶里int[] num=new int[array.length];//用于保存每個桶里有多少個數(shù)字 ,最多為輸入數(shù)組長度while(n<=d){for(int e:array) //將數(shù)組array里的每個數(shù)字放在相應的桶里{int digit=(e/n)%10;bucket[digit][num[digit]]=e;num[digit]++;}for(int i=0;i<array.length;i++)//將前一個循環(huán)生成的桶里的數(shù)據(jù)覆蓋到原數(shù)組中用于保存這一位的排序結(jié)果{if(num[i]!=0)//這個桶里有數(shù)據(jù)，從上到下遍歷這個桶并將數(shù)據(jù)保存到原數(shù)組中{for(int j=0;j<num[i];j++){array[k]=bucket[i][j];k++;}}num[i]=0;//將桶里計數(shù)器置0，用于下一次位排序}n*=10;k=0;//將k置0，用于下一輪保存位排序結(jié)果}System.out.println("基數(shù)排序，花費時間(ms):" + ((System.nanoTime() - nowTime) / 1000000.0) + "ms");}

基數(shù)排序是穩(wěn)定算法，效率很高，其復雜度為O(nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)。但它只能用在整數(shù)的排序中，且需要借助一定的輔助空間。

上面的代碼適用有些局限在于對基數(shù)值選取：

int [] x = {25 ,11 ,22 ,34 ,15 ,44 ,76, 66, 100, 8 ,14, 20 ,2, 5 ,1 };

比如這個數(shù)組，基數(shù)應該選3。附上一個選擇基數(shù)值的方法。

/*** 獲取基數(shù)排序中的基數(shù)* @param array* @return*/public int getRadixBasicNumber(int[] array){if(array == null && array.length ==0) {return 0;}int max =0;//1獲取最大的絕對值的數(shù)for(int i =0;i<array.length;i++) {if(Math.abs(max)<Math.abs(array[i])) {max = array[i];}}int times = 0;if(max<0) max = -max;//2求出最大的絕對值的數(shù)，是10的times次冪。while(max >0) {max = max/10;times ++;}return times;}

?

耗時對比：

10W 條隨機 數(shù)據(jù) 運行如圖：

分別對比了基數(shù)排序，直插排序，希爾排序和快速排序。差距很明顯。

50W 條隨機 數(shù)據(jù) 運行如圖：

分別對比了基數(shù)排序，直插排序，希爾排序和快速排序。差距很明顯。

100W 條隨機 數(shù)據(jù) 運行如圖：

分別對比了基數(shù)排序，直插排序，希爾排序和快速排序。差距很明顯。

總結(jié)：

基數(shù)排序

優(yōu)點：效率高。

缺點：占用內(nèi)存大，只能對正整數(shù)排序（采用二維數(shù)組做桶時）

最壞時間復雜度：O(P(N+B))。

平均時間復雜度為：O(P(N+B))。

其中P是排序的趟數(shù)，N是要被排序元素的個數(shù)，B是桶數(shù)。

各種排序方法比較：

?

更多排序算法：

冒泡排序? ?：??https://blog.csdn.net/Angry_Mills/article/details/81057900

插入排序? ?：??https://blog.csdn.net/Angry_Mills/article/details/81208700

快速排序???：??https://blog.csdn.net/Angry_Mills/article/details/83339390

總結(jié)

以上是生活随笔為你收集整理的java 实现 常见排序算法（四）基数排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。