基數排序
基數排序(桶排序)介紹:
- 基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或 bin sort，顧 名思義，它是通過鍵值的各個位的值，將要排序的元素分配至某些“桶”中，達到排序的作用
- 基數排序法是屬于穩定性的排序，基數排序法的是效率高的穩定性排序法
- 基數排序(Radix Sort)是桶排序的擴展
- 基數排序是 1887 年赫爾曼·何樂禮發明的，它是這樣實作的：將整數按位數切割成不同的數字，然后按每個 位數分別比較
基數排序基本思想
將所有待比較數值統一為同樣的數位長度，數位較短的數前面補零，然后，從最低位開始，依次進行一次排序， 這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列，
基數排序圖文說明
將陣列 {53, 3, 542, 748, 14, 214} 使用基數排序, 進行升序排序
基數排序代碼實作
要求：將陣列 {53, 3, 542, 748, 14, 214} 使用基數排序, 進行升序排序
分析看上面的圖片
package DataStructures.com.atguigu.sort;
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){
//定義一個二維陣列，表示10個桶, 每個桶就是一個一維陣列
//說明
//1. 二維陣列包含10個一維陣列
//2. 為了防止在放入數的時候，資料溢位，則每個一維陣列(桶)，大小定為arr.length
//3. 名明確，基數排序是使用空間換時間的經典演算法
int[][] bucket = new int[10][arr.length];
//為了記錄每個桶中，實際存放了多少個資料,我們定義一個一維陣列來記錄各個桶的每次放入的資料個數
//可以這里理解
//比如：bucketElementCounts[0] , 記錄的就是 bucket[0] 桶的放入資料個數
int[] bucketElementCounts = new int[10];
//第一輪(針對每個元素的個位進行排序處理)
for(int j = 0;j < arr.length;j++){
//取出每個元素的個位的值
int digitOfElement = arr[j] / 1 % 10;
//放入到對應的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
//按照這個桶的順序（一維陣列的下標依次取出資料，放入原來陣列）
int index = 0;
//遍歷每一桶，并將桶中的資料，放入原來陣列
for(int k = 0;k <bucketElementCounts.length;k ++){
//如果桶中有資料，我們才放入到原陣列
if(bucketElementCounts[k] != 0){
//回圈該桶即第K個桶（即第k個一維陣列）,放入
for(int l = 0;l < bucketElementCounts[k];l++){
//取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第l輪處理后，需要將每個bucketElementCounts[k] = 0!!!
bucketElementCounts[k] = 0;
}
System.out.println("第1輪，對個位的排序處理arr=" + Arrays.toString(arr));
//==========================================
//第2輪(針對每個元素的十位進行排序處理)
for (int j = 0; j < arr.length; j++) {
// 取出每個元素的十位的值
int digitOfElement = arr[j] / 10 % 10; //748 / 10 => 74 % 10 => 4
// 放入到對應的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
// 按照這個桶的順序(一維陣列的下標依次取出資料，放入原來陣列)
index = 0;
// 遍歷每一桶，并將桶中是資料，放入到原陣列
for (int k = 0; k < bucketElementCounts.length; k++) {
// 如果桶中，有資料，我們才放入到原陣列
if (bucketElementCounts[k] != 0) {
// 回圈該桶即第k個桶(即第k個一維陣列), 放入
for (int l = 0; l < bucketElementCounts[k]; l++) {
// 取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第2輪處理后，需要將每個 bucketElementCounts[k] = 0 ！！！！
bucketElementCounts[k] = 0;
}
System.out.println("第2輪，對十位的排序處理 arr =" + Arrays.toString(arr));
//第3輪(針對每個元素的百位進行排序處理)
for (int j = 0; j < arr.length; j++) {
// 取出每個元素的百位的值
int digitOfElement = arr[j] / 100 % 10; // 748 / 100 => 7 % 10 = 7
// 放入到對應的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
// 按照這個桶的順序(一維陣列的下標依次取出資料，放入原來陣列)
index = 0;
// 遍歷每一桶，并將桶中是資料，放入到原陣列
for (int k = 0; k < bucketElementCounts.length; k++) {
// 如果桶中，有資料，我們才放入到原陣列
if (bucketElementCounts[k] != 0) {
// 回圈該桶即第k個桶(即第k個一維陣列), 放入
for (int l = 0; l < bucketElementCounts[k]; l++) {
// 取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第3輪處理后，需要將每個 bucketElementCounts[k] = 0 ！！！！
bucketElementCounts[k] = 0;
}
System.out.println("第3輪，對百位的排序處理 arr =" + Arrays.toString(arr));
}
}
運行結果：
推廣到一般情況：
代碼如下：
package DataStructures.com.atguigu.sort;
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){
//根據前面的推導程序，我們可以得到最終的基數排序代碼
//1. 得到陣列中最大的數的位數
int max = arr[0];//假設第一數就是最大數
for(int i = 1;i < arr.length;i++){
if(arr[i] > max){
max = arr[i];
}
}
//得到最大數是幾位數
int maxLength = (max + "").length();
//定義一個二維陣列，表示10個桶, 每個桶就是一個一維陣列
//說明
//1. 二維陣列包含10個一維陣列
//2. 為了防止在放入數的時候，資料溢位，則每個一維陣列(桶)，大小定為arr.length
//3. 名明確，基數排序是使用空間換時間的經典演算法
int[][] bucket = new int[10][arr.length];
//為了記錄每個桶中，實際存放了多少個資料,我們定義一個一維陣列來記錄各個桶的每次放入的資料個數
//可以這里理解
//比如：bucketElementCounts[0] , 記錄的就是 bucket[0] 桶的放入資料個數
int[] bucketElementCounts = new int[10];
//這里我們使用回圈將代碼處理
for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
//(針對每個元素的對應位進行排序處理)， 第一次是個位，第二次是十位，第三次是百位..
for(int j = 0; j < arr.length; j++) {
//取出每個元素的對應位的值
int digitOfElement = arr[j] / n % 10;
//放入到對應的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
//按照這個桶的順序(一維陣列的下標依次取出資料，放入原來陣列)
int index = 0;
//遍歷每一桶，并將桶中是資料，放入到原陣列
for(int k = 0; k < bucketElementCounts.length; k++) {
//如果桶中，有資料，我們才放入到原陣列
if(bucketElementCounts[k] != 0) {
//回圈該桶即第k個桶(即第k個一維陣列), 放入
for(int l = 0; l < bucketElementCounts[k]; l++) {
//取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第i+1輪處理后，需要將每個 bucketElementCounts[k] = 0 ！！！！
bucketElementCounts[k] = 0;
}
System.out.println("第"+(i+1)+"輪，排序處理 arr =" + Arrays.toString(arr));
}
}
}
運行結果：
結果跟之前一樣
基數排序的說明
1.基數排序是對傳統桶排序的擴展，速度很快.
2.基數排序是經典的空間換時間的方式，占用記憶體很大, 當對海量資料排序時，容易造成 OutOfMemoryError ，
- 基數排序時穩定的，[注:假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些 記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前， 則稱這種排序演算法是穩定的；否則稱為不穩定的]
這篇博客是我在B站看韓順平老師資料結構和演算法的課時的筆記，記錄一下，防止忘記，也希望能幫助各位朋友，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/524884.html
標籤：Java
上一篇：多執行緒 & 反射 & 注解 & JDBC 核心點總結
下一篇：在腳本中實作多執行緒/并行處理