一、思想
基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，其時間復雜度為O (nlog(m))，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的穩定性排序法，
二、圖解程序
三、核心代碼
/**
* 基數排序
* 構造一個桶，每個數按位數分別放入桶中，放完后，從桶中取出資料放入陣列
*/
public static void barrelSort(int[] arr) {
int[][] barrel = new int[10][arr.length];//考慮最壞的情況
//為了保證回收的時候知道每個桶中放了多少個資料
int[] barreCount = new int[10];
//按位數確定回圈次數，所以需要提前知道最大數長度
int leght = (getMax(arr) + "").length();
for (int i = 0, m = 1; i < leght; i++, m *= 10) {
//每次回圈，按當前位的數子放入桶中
for (int j = 0; j < arr.length; j++) {
int temp = (arr[j] / m) % 10;//當前位數的數字
barrel[temp][barreCount[temp]++] = arr[j];
}
//從桶中一次取出資料放回原陣列
int indexBarre = 0;//當前陣列索引
for (int j = 0; j < 10; j++) {
if (barreCount[j] != 0) {
for (int n = 0; n < barreCount[j]; n++) {
arr[indexBarre++] = barrel[j][n];
}
}
barreCount[j] = 0;
}
}
}
public static int getMax(int[] arr) {
int max = arr[0];
for (int i = 0; i < arr.length; i++) if (max < arr[i]) max = arr[i];
return max;
}
四、速度測驗
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/245309.html
標籤：AI
上一篇：阿里云邊緣計算又獲獎啦！