上節(jié)我們學(xué)習(xí)了歸并排序,我們知道了歸并采用的是分治的策略,在分的過程中采用的是遞歸來處理,而治的過程才是我們算法的核心,更多詳解看算法入門教程-歸并排序,這節(jié)我們學(xué)習(xí)另外一種算法:基數(shù)排序,首先我們簡單的介紹下什么是基數(shù)排序?
基數(shù)排序
官方介紹:基數(shù)排序稱為"分配式排序",有稱"桶子法"通過鍵值的各個(gè)位的值,將要排序的元素分配到某些"桶"中來達(dá)到排序的作用.
基數(shù)排序?qū)儆诜€(wěn)定性排序,同樣也是桶排序的擴(kuò)展
基數(shù)排序的思想:將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長度,數(shù)位較短的前面補(bǔ)零,然后從最低位開始,依次進(jìn)行一次排序,這樣從最低位一直到最高位排序完成后,數(shù)列就會(huì)變成一個(gè)有序的數(shù)列.
接下來我們通過圖解的方式來理解上述所描述的過程:
假設(shè)我待排序的數(shù)列為{53,3,542,748,14,214},我們來看具體過程:
- 第一輪的圖解過程:
第一輪排序過程.png
-
第二輪的圖解過程
第二輪排序過程.png -
第三輪圖解過程
第三輪排序結(jié)果圖.png
通過三輪的排序我們最終完成了排序過程,圖中有具體的詳細(xì),這里我簡單的補(bǔ)充說明下為啥什么這樣存放
- 首先圖中0-9代表10個(gè)一位數(shù)組(也就是我們的桶)
- 其中我們?cè)厝〉降膫€(gè)位和十位以及百位等值,對(duì)應(yīng)的就是我們下標(biāo)為0-9的一維數(shù)組
這樣大家可能明白許多了,我們接著通過代碼的方式來實(shí)現(xiàn)
代碼實(shí)現(xiàn)過程
假設(shè)我待排序的列表為:{53,3,542,748,14,214}
- 公用代碼
//基數(shù)排序方法
public static void radixSort(int[] arr){
//首先我們來定義一個(gè)二維數(shù)組來表示10個(gè)桶,其中每個(gè)桶就是一個(gè)一維數(shù)組
//為了防止放入元素的時(shí)候溢出,這里將每個(gè)桶的大小定為arr.length
//基數(shù)排序是經(jīng)典的空間換取時(shí)間的算法
int [][] bucket = new int[10][arr.length];
//為了統(tǒng)計(jì)每個(gè)桶中實(shí)際的元素的個(gè)數(shù),這里定義一個(gè)一維數(shù)組來記錄每次放入元素的個(gè)數(shù)
//如:bucketEleCounts[0]表示記錄的是bucket[0]桶的放入元素的個(gè)數(shù)
int [] bucketEleCounts = new int[10];
- 第一輪排序代碼實(shí)現(xiàn)
//第一輪:針對(duì)每一個(gè)元素的個(gè)位進(jìn)行排序處理
for (int j = 0; j <arr.length ; j++) {
//取出每個(gè)元素的個(gè)位數(shù)
int digitOfElement = arr[j] %10;
//放入到對(duì)應(yīng)的桶中
//說明:
// bucket[digitOfElement]表示第幾個(gè)桶;因?yàn)槲覀冇?jì)算出來的個(gè)位數(shù)也代表它是第幾個(gè)桶
//[bucketEleCounts[digitOfElement]]表示對(duì)應(yīng)桶的元素
bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
// ++ 操作表示如果后面計(jì)算得到個(gè)位數(shù)相同的話,我們需要將它放入已有元素的后面
bucketEleCounts[digitOfElement] ++;
}
//2.按照上述桶的順序,我們將一維數(shù)組的下標(biāo)依次取出該元素放入到原數(shù)組(arr)
//首先定義一個(gè)臨時(shí)索引index
int index = 0;
//遍歷操作
for (int k = 0; k <bucket.length ; k++) {
//如果我們的桶中有數(shù)據(jù),才放入到原數(shù)組中
if (bucketEleCounts[k] !=0){
//循環(huán)該桶,也就是第K個(gè)桶
for (int l = 0; l <bucketEleCounts[k] ; l++) {
//將第k個(gè)桶的第l個(gè)元素放入到原數(shù)組中
arr[index] = bucket[k][l];
index ++;
}
}
//注意:
//第一輪處理完過后,我們需要將每一個(gè)(bucketEleCounts[k]清零,為了后面步驟的需要
bucketEleCounts[k] = 0;
}
System.out.println("第一輪對(duì)個(gè)位的排序處理結(jié)果");
System.out.println(Arrays.toString(arr));
- 來看測試代碼
/**
* 算法學(xué)習(xí)-基數(shù)排序
*/
public class RadixSort {
public static void main(String[] args) {
int [] arr = {53,3,542,748,14,214};
radixSort(arr);
-
測試結(jié)果如圖:
第一輪測試結(jié)果.png 第二輪排序代碼實(shí)現(xiàn)
//第二輪:針對(duì)每一個(gè)元素的個(gè)位進(jìn)行排序處理
for (int j = 0; j <arr.length ; j++) {
//取出每個(gè)元素的十位數(shù)
int digitOfElement = arr[j] /10 %10;
//放入到對(duì)應(yīng)的桶中
//說明:
// bucket[digitOfElement]表示第幾個(gè)桶;因?yàn)槲覀冇?jì)算出來的個(gè)位數(shù)也代表它是第幾個(gè)桶
//[bucketEleCounts[digitOfElement]]表示對(duì)應(yīng)桶的元素
bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
// ++ 操作表示如果后面計(jì)算得到個(gè)位數(shù)相同的話,我們需要將它放入已有元素的后面
bucketEleCounts[digitOfElement] ++;
}
//2.按照上述桶的順序,我們將一維數(shù)組的下標(biāo)依次取出該元素放入到原數(shù)組(arr)
//首先定義一個(gè)臨時(shí)索引index
index = 0;
//遍歷操作
for (int k = 0; k <bucket.length ; k++) {
//如果我們的桶中有數(shù)據(jù),才放入到原數(shù)組中
if (bucketEleCounts[k] !=0){
//循環(huán)該桶,也就是第K個(gè)桶
for (int l = 0; l <bucketEleCounts[k] ; l++) {
//將第k個(gè)桶的第l個(gè)元素放入到原數(shù)組中
arr[index] = bucket[k][l];
index ++;
}
}
//注意:
//第二輪處理完過后,我們需要將每一個(gè)(bucketEleCounts[k]清零,為了后面步驟的需要
bucketEleCounts[k] = 0;
}
System.out.println("第二輪對(duì)個(gè)位的排序處理結(jié)果");
System.out.println(Arrays.toString(arr));
-
直接看測試結(jié)果如圖所示:
第二輪測試結(jié)果圖.png 第三輪排序代碼實(shí)現(xiàn)
//第三輪:針對(duì)每一個(gè)元素的個(gè)位進(jìn)行排序處理
for (int j = 0; j <arr.length ; j++) {
//取出每個(gè)元素的十位數(shù)
int digitOfElement = arr[j] /100 %10;
//放入到對(duì)應(yīng)的桶中
//說明:
// bucket[digitOfElement]表示第幾個(gè)桶;因?yàn)槲覀冇?jì)算出來的個(gè)位數(shù)也代表它是第幾個(gè)桶
//[bucketEleCounts[digitOfElement]]表示對(duì)應(yīng)桶的元素
bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
// ++ 操作表示如果后面計(jì)算得到個(gè)位數(shù)相同的話,我們需要將它放入已有元素的后面
bucketEleCounts[digitOfElement] ++;
}
//2.按照上述桶的順序,我們將一維數(shù)組的下標(biāo)依次取出該元素放入到原數(shù)組(arr)
//首先定義一個(gè)臨時(shí)索引index
index = 0;
//遍歷操作
for (int k = 0; k <bucket.length ; k++) {
//如果我們的桶中有數(shù)據(jù),才放入到原數(shù)組中
if (bucketEleCounts[k] !=0){
//循環(huán)該桶,也就是第K個(gè)桶
for (int l = 0; l <bucketEleCounts[k] ; l++) {
//將第k個(gè)桶的第l個(gè)元素放入到原數(shù)組中
arr[index] = bucket[k][l];
index ++;
}
}
//注意:
//第二輪處理完過后,我們需要將每一個(gè)(bucketEleCounts[k]清零,為了后面步驟的需要
bucketEleCounts[k] = 0;
}
System.out.println("第三輪對(duì)個(gè)位的排序處理結(jié)果");
System.out.println(Arrays.toString(arr));
}
-
測試結(jié)果如下圖所示:
第三輪測試結(jié)果圖.png
通過三輪的處理我們最終完成了排序,我們來整合下代碼
//基數(shù)排序方法
public static void radixSort(int[] arr){
//得到數(shù)組中最大數(shù)的位數(shù)
//定義一個(gè)臨時(shí)變量來存儲(chǔ)我們的最大數(shù)先假設(shè)定義的就是最大的
int max = arr[0]; //假設(shè)第一個(gè)就是最大的
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ù)組
//為了防止放入元素的時(shí)候溢出,這里將每個(gè)桶的大小定為arr.length
//基數(shù)排序是經(jīng)典的空間換取時(shí)間的算法
int [][] bucket = new int[10][arr.length];
//為了統(tǒng)計(jì)每個(gè)桶中實(shí)際的元素的個(gè)數(shù),這里定義一個(gè)一維數(shù)組來記錄每次放入元素的個(gè)數(shù)
//如:bucketEleCounts[0]表示記錄的是bucket[0]桶的放入元素的個(gè)數(shù)
int [] bucketEleCounts = new int[10];
//整合代碼
for (int i = 0, n=1; i < maxLength ; i++, n *=10) {
//每一輪:針對(duì)每一個(gè)元素的對(duì)應(yīng)位進(jìn)行排序處理; 第一輪是個(gè)位,第二輪是十位,第三輪是百位....
for (int j = 0; j <arr.length ; j++) {
//取出每個(gè)元素的對(duì)應(yīng)位的值
int digitOfElement = arr[j] /n %10;
//放入到對(duì)應(yīng)的桶中
//說明:
// bucket[digitOfElement]表示第幾個(gè)桶;因?yàn)槲覀冇?jì)算出來的個(gè)位數(shù)也代表它是第幾個(gè)桶
//[bucketEleCounts[digitOfElement]]表示對(duì)應(yīng)桶的元素
bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
// ++ 操作表示如果后面計(jì)算得到個(gè)位數(shù)相同的話,我們需要將它放入已有元素的后面
bucketEleCounts[digitOfElement] ++;
}
//2.按照上述桶的順序,我們將一維數(shù)組的下標(biāo)依次取出該元素放入到原數(shù)組(arr)
//首先定義一個(gè)臨時(shí)索引index
int index = 0;
//遍歷操作
for (int k = 0; k <bucket.length ; k++) {
//如果我們的桶中有數(shù)據(jù),才放入到原數(shù)組中
if (bucketEleCounts[k] !=0){
//循環(huán)該桶,也就是第K個(gè)桶
for (int l = 0; l <bucketEleCounts[k] ; l++) {
//將第k個(gè)桶的第l個(gè)元素放入到原數(shù)組中
arr[index] = bucket[k][l];
index ++;
}
}
//注意:
//第i+1輪處理完過后,我們需要將每一個(gè)(bucketEleCounts[k]清零,為了后面步驟的需要
bucketEleCounts[k] = 0;
}
System.out.println("第"+(i+1)+"輪對(duì)個(gè)位的排序處理結(jié)果");
System.out.println(Arrays.toString(arr));
}
- 測試一把結(jié)果如圖所示:
整合后的測試結(jié)果圖.png
最后一點(diǎn)我們來測試下基數(shù)排序的執(zhí)行時(shí)間效率:
int [] arr = new int[10000000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random() * 10000000); //隨機(jī)生成[0,100000)的數(shù)
}
Date date1 = new Date();
SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String format = dateFormat.format(date1);
System.out.println("排序前的時(shí)間為:"+format);
//進(jìn)行排序
int [] temp = new int[arr.length];
radixSort(arr);
Date date2 = new Date();
SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String format2 = dateFormat.format(date2);
System.out.println("排序后的時(shí)間為:"+format2);
- 來看測試結(jié)果如圖所示:
時(shí)間測試.png
可以看出10W條數(shù)據(jù)排序是沒有任何壓力的,那么關(guān)于基數(shù)排序的學(xué)習(xí)就到這了...
