本文帶來(lái)八大排序算法之基數(shù)排序。

基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort），它是通過(guò)鍵值的各個(gè)位的值，將要排序的元素分配至某些"桶“中，從而達(dá)到排序的作用。基數(shù)排序是效率高的穩(wěn)定性的排序算法。基數(shù)排序是桶排序的擴(kuò)展。

基數(shù)排序基本思想：

將所有待比較的數(shù)值統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序，這樣從最低位排序一直到最高位排序完成以后，數(shù)位就變成一個(gè)有序序列。見下圖（以數(shù)組{53, 3, 542, 748, 14, 214}進(jìn)行升序排序，共分三大步）：

?

推導(dǎo)過(guò)程代碼如下：

//基數(shù)排序推導(dǎo)public static void radixSort2(int[] arr){//推導(dǎo)過(guò)程：//定義一個(gè)二維數(shù)組，表示10個(gè)桶，每個(gè)桶表示一個(gè)一維數(shù)組//說(shuō)明：//1.二維數(shù)組包含10個(gè)一維數(shù)組//2.為了防止在放入數(shù)的時(shí)候，數(shù)據(jù)溢出，則每個(gè)一維數(shù)組（桶），大小定為arr.length//3.很明顯，基數(shù)排序是使用空間換時(shí)間的經(jīng)典算法int[][] bucket = new int[10][arr.length];//為了記錄每個(gè)桶中，實(shí)際存放了多少個(gè)數(shù)據(jù)，我們定義一個(gè)一維數(shù)組來(lái)記錄各個(gè)桶每次放入的數(shù)據(jù)個(gè)數(shù)//可以這么理解: bucketElementCounts[0] ，記錄的是 bucket[0]桶中放入數(shù)據(jù)的個(gè)數(shù)int[] bucketElementCounts = new int[10];//第1輪（針對(duì)每個(gè)元素的個(gè)位數(shù)進(jìn)行排序處理）for(int j=0; j<arr.length; j++){//得到每個(gè)元素的個(gè)位數(shù)int digitOfElement = arr[j] % 10;//放入到對(duì)應(yīng)的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];bucketElementCounts[digitOfElement]++ ;}//按照這個(gè)桶的順序（一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來(lái)的數(shù)組）int index = 0;//遍歷每一桶，并將桶中的數(shù)據(jù)放入到原來(lái)的數(shù)組for(int k=0; k<bucket.length; k++){//如果桶中有數(shù)據(jù)，我們才放入到原數(shù)組中if(bucketElementCounts[k] != 0){//循環(huán)bucket中第k個(gè)桶（即第k個(gè)一維數(shù)組），放入到數(shù)組中for(int l=0; l<bucketElementCounts[k]; l++){//取出元素放入到arr數(shù)組中arr[index++] = bucket[k][l];}}//第1輪處理后，每個(gè)桶中的數(shù)據(jù)復(fù)制到原始數(shù)組后, 需要將每個(gè)bucketElementCounts[k] = 0bucketElementCounts[k] = 0;}System.out.println("第1輪，對(duì)個(gè)位的排序處理 arr = " + Arrays.toString(arr));/*******************************************************************************///第2輪（針對(duì)每個(gè)元素的十位數(shù)進(jìn)行排序處理）for(int j=0; j<arr.length; j++){//得到每個(gè)元素的十位數(shù)int digitOfElement = arr[j] / 10 % 10;//放入到對(duì)應(yīng)的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];bucketElementCounts[digitOfElement]++ ;}//按照這個(gè)桶的順序（一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來(lái)的數(shù)組）index = 0;//遍歷每一桶，并將桶中的數(shù)據(jù)放入到原來(lái)的數(shù)組for(int k=0; k<bucket.length; k++){//如果桶中有數(shù)據(jù)，我們才放入到原數(shù)組中if(bucketElementCounts[k] != 0){//循環(huán)bucket中第k個(gè)桶（即第k個(gè)一維數(shù)組），放入到數(shù)組中for(int l=0; l<bucketElementCounts[k]; l++){//取出元素放入到arr數(shù)組中arr[index++] = bucket[k][l];}}bucketElementCounts[k] = 0;}System.out.println("第2輪，對(duì)十位的排序處理 arr = " + Arrays.toString(arr));//第3輪（針對(duì)每個(gè)元素的百位數(shù)進(jìn)行排序處理）for(int j=0; j<arr.length; j++){//得到每個(gè)元素的百位數(shù)int digitOfElement = arr[j] / 100 % 10;//放入到對(duì)應(yīng)的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];bucketElementCounts[digitOfElement]++ ;}//按照這個(gè)桶的順序（一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來(lái)的數(shù)組）index = 0;//遍歷每一桶，并將桶中的數(shù)據(jù)放入到原來(lái)的數(shù)組for(int k=0; k<bucket.length; k++){//如果桶中有數(shù)據(jù)，我們才放入到原數(shù)組中if(bucketElementCounts[k] != 0){//循環(huán)bucket中第k個(gè)桶（即第k個(gè)一維數(shù)組），放入到數(shù)組中for(int l=0; l<bucketElementCounts[k]; l++){//取出元素放入到arr數(shù)組中arr[index++] = bucket[k][l];}}bucketElementCounts[k] = 0;}System.out.println("第3輪，對(duì)百位的排序處理 arr = " + Arrays.toString(arr));}

實(shí)現(xiàn)代碼：

import java.util.Arrays;public class RadixSort {public static void main(String[] args){int[] arr = {53, 3, 542, 748, 14, 214};radixSort(arr);}public static void radixSort(int[] arr){//根據(jù)radixSort2()推導(dǎo)過(guò)程//1.得到數(shù)組中最大的數(shù)的位數(shù)int max = arr[0]; //假設(shè)第一個(gè)數(shù)就是最大的數(shù);for(int i=1; i<arr.length; i++){if(arr[i] > max){max = arr[i];}}//得到最大數(shù)是幾位數(shù)int maxLength = (max + "").length();//定義一個(gè)二維數(shù)組，表示10個(gè)桶，每個(gè)桶表示一個(gè)一維數(shù)組//說(shuō)明：//1.二維數(shù)組包含10個(gè)一維數(shù)組//2.為了防止在放入數(shù)的時(shí)候，數(shù)據(jù)溢出，則每個(gè)一維數(shù)組（桶），大小定為arr.length//3.很明顯，基數(shù)排序是使用空間換時(shí)間的經(jīng)典算法int[][] bucket = new int[10][arr.length];//為了記錄每個(gè)桶中，實(shí)際存放了多少個(gè)數(shù)據(jù)，我們定義一個(gè)一維數(shù)組來(lái)記錄各個(gè)桶每次放入的數(shù)據(jù)個(gè)數(shù)//可以這么理解: bucketElementCounts[0] ，記錄的是 bucket[0]桶中放入數(shù)據(jù)的個(gè)數(shù)int[] bucketElementCounts = new int[10];//使用循環(huán)for(int i=0, n=1; i<maxLength; i++, n*=10){//第一次是個(gè)位，第二次是十位，以此類推for(int j=0; j<arr.length; j++){//得到每個(gè)元素對(duì)應(yīng)位的值int digitOfElement = arr[j] / n % 10;//放入到對(duì)應(yīng)的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];bucketElementCounts[digitOfElement]++ ;}//按照這個(gè)桶的順序（一維數(shù)組的下標(biāo)依次取出數(shù)據(jù)，放入原來(lái)的數(shù)組）int index = 0;//遍歷每一桶，并將桶中的數(shù)據(jù)放入到原來(lái)的數(shù)組for(int k=0; k<bucket.length; k++){//如果桶中有數(shù)據(jù)，我們才放入到原數(shù)組中if(bucketElementCounts[k] != 0){//循環(huán)bucket中第k個(gè)桶（即第k個(gè)一維數(shù)組），放入到數(shù)組中for(int l=0; l<bucketElementCounts[k]; l++){//取出元素放入到arr數(shù)組中arr[index++] = bucket[k][l];}}//第i+1輪處理后，每個(gè)桶中的數(shù)據(jù)復(fù)制到原始數(shù)組后, 需要將每個(gè)bucketElementCounts[k] = 0bucketElementCounts[k] = 0;}System.out.println("第"+(i+1)+"輪， arr = " + Arrays.toString(arr));}}}

基數(shù)排序說(shuō)明：

1.基數(shù)排序是對(duì)桶排序的擴(kuò)展，速度很快；

2.基數(shù)排序是經(jīng)典的“空間換時(shí)間”的方式，占用內(nèi)存很大，當(dāng)對(duì)海量數(shù)據(jù)排序時(shí)，容易造成OutOfMemoryError；

3.基數(shù)排序是穩(wěn)定的。（假定在待排序的記錄序列中，存在多個(gè)具有相同關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i] = r[j] 且 r[i]在r[j] 之前，而在排序后的序列中，r[i]仍在r[j] 之前，則稱這種算法是穩(wěn)定的，否則成為不穩(wěn)定的）；

4.有負(fù)數(shù)的數(shù)組，我們一般不使用基數(shù)排序。

總結(jié)

以上是生活随笔為你收集整理的Java实现基数排序及其推导过程 Radix Sort的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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