今天沒事看了一下基數排序，說實話，我最不擅長的就是排序了，最近準備多刷一些排序題，練習一下；
首先啥是基數排序呢？來一個比較專業的說法，看看就行了：
基數排序（radix sort）屬于“分配式排序”，又稱桶子法，bucket或bin sort，將要排序的各各位的值分配至某些桶中，達到排序的目的；基數排序是穩定性的排序，是桶排序的擴展....
反正就是一句話，就是將要排序的每個數的每一位進行一個排序，首先每個數的各位進行排序，然后十位進行排序，百位進行排序，依次類推
舉個簡單的例子，13，5，112，46,這四個數要進行排序的話，為了好看一些將位數比較少的添0，也就是變成013，005，112，046；然后我們準備10個桶，也就是一個大小為10的陣列（為什么要是10呢？廢話，每一位上的數字最大就是9啊！），下圖所示，對個位數分別分配到對應的桶中
第二次排序：經過第一次排序的陣列，再根據十位分配到各個桶
第三次排序，根據第二次排序后各個數的百位再分配到各個桶
然后結果就出來了，很神奇......妙啊妙啊！真的很有意思，嘿嘿
下面我們使用java代碼來簡單實作一下，首先問一下，任意給定一個int型別的整數，怎么獲取它的位數呢？很簡單，如下圖所示：
然后再問一下，怎么獲取一個整數的每一位上的數字呢？也很簡單，下圖所示：會依次輸出4，3，2，1
ok，知道了這個時候我們就可以開始寫代碼了，寫代碼之前一定要思考一下怎么寫，最好使用中文把思路寫一下，無檔案，不寫代碼！這里使用陣列實作：
首先，我們肯定要將一個陣列中的最大數字給找出來，因為這個最大數字的位數決定了我們需要進行排序的次數；
然后，由于是有十個桶，而每個桶里可能會放多個資料，那么最多是可以放多少個資料呢？很明顯，是arr.length個，這里的arr.length指的是需要進行排序的陣列中元素的個數
再然后，這十個桶應該就是一個二維陣列（其實可以用其他的實作形式，比如陣列+鏈表或者陣列+堆疊都行，有興趣的自己實作一下）
最后，我們每次將陣列中共的資料丟到桶里，然后需要拿出來吧！所以我們也需要有個地方記錄一下每個桶中元素的數量
代碼如下，注釋也比較清楚：
1 public class Study0712 { 2 /** 3 * 基數排序 4 * @Title: radixSort 5 * @Description: 6 * @param arr 7 * @return: void 8 * @throws 9 */ 10 public static void radixSort(int[] arr) { 11 12 // 將陣列中最大的數字max找到 13 int max = arr[0]; 14 for (int i = 1; i < arr.length; i++) { 15 if (arr[i] > max) { 16 max = arr[i]; 17 } 18 } 19 System.out.println("max=" + max); 20 // 十個桶 21 int[][] buckets = new int[10][arr.length]; 22 // 該陣列存放每一個桶中元素的數量,這個陣列的索引和桶的索引對應 23 int[] bucketCount = new int[10]; 24 25 // 需要排序的次數肯定就是max的位數 26 int sortNum = Integer.toString(max).length(); 27 for (int j = 0; j < sortNum; j++) { 28 // 遍歷陣列，第一次排序是用個位進行比較,第二次是用十位進行比較 29 for (int m = 0; m < arr.length; m++) { 30 // 取出陣列中每一個數字的某一位上的數字,這個數字就是桶的索引 31 int val = (int) (arr[m] / Math.pow(10, j) % 10); 32 // 如果val == 2,那就放在第二個桶中，第二桶中也可能有bucketCount[val]個元素了，所以放完元素之后需要++ 33 buckets[val][bucketCount[val]++] = arr[m]; 34 } 35 36 printTwo(buckets); 37 38 // 前面已經將元素都放進桶里了，現在取出來放到陣列中 39 int index = 0; 40 for (int n = 0; n < bucketCount.length; n++) { 41 //遍歷bucketCount中的元素，如果不為0，說明該對應的桶中有元素 42 if (bucketCount[n] != 0) { 43 for (int x = 0; x < bucketCount[n]; x++) { 44 //獲取桶中的元素，然后放入陣列中，并將桶中該元素置為0 45 arr[index++] = buckets[n][x]; 46 buckets[n][x] = 0; 47 } 48 } 49 //每一次將桶里的元素取出來的時候，需要將對應陣列中表示該桶中元素數量置為0 50 //如果不置為0，那么在第二次從桶中拿元素放到陣列中的時候，遍歷bucketCount中的資料是之前桶中元素的資料（也許有6個桶中有資料） 51 bucketCount[n] =0; 52 } 53 System.out.println("第" + (j + 1) + "次排序的結果為：" + Arrays.toString(arr)); 54 55 } 56 57 } 58 59 /** 60 * 遍歷二維資料中的元素 61 * @Title: printTwo 62 * @Description: 63 * @param arrs 64 * @return: void 65 * @throws 66 */ 67 public static void printTwo(int[][] arrs) { 68 for (int i = 0; i < arrs.length; i++) { 69 int[] arr = arrs[i]; 70 for (int j = 0; j < arr.length; j++) { 71 System.out.print(arr[j]); 72 } 73 System.out.println(); 74 } 75 } 76 77 public static void main(String[] args) { 78 int[] arr = { 13, 5, 112, 46 }; 79 radixSort(arr); 80 81 } 82 83 }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/144549.html
標籤：Java