一、基數排序

（1）基數排序的簡介

　　基數排序不同于其他的排序算法，它不是基于比較的算法?；鶖蹬判蚴且环N借助多關鍵字排序的思想對單邏輯關鍵字進行排序的方法。它是一種穩定的排序算法?！?/p>

　　通常用于對數的排序選擇的是最低位優先法，即先對最次位關鍵字進行排序，再對高一位的關鍵字進行排序，以此類推。

（2）基數排序的思想

　　多關鍵字排序中有兩種方法：最高位優先法(MSD)和最低位優先法（LSD）。

元數據為k₁k₂k₃..k_n

A、最高位優先(Most Significant Digit first)法： 先按k₁排序分組，同一k₁組中記錄關鍵碼k₁相等，對各k₁組按k₂關鍵字排序分成k₂子組；同一k₂子組中記錄關鍵碼k₂相等，再對各k₂子組按k₃排序分成k₃子組，重復這樣步驟直至子組按k_n排序分成k_n子組。再將各組連接起來，便得到一個有序序列。 B、最低位優先(Least Significant Digit first)法： 先從k_n開始排序，再對k_n-1進行排序，依次重復，直到對k₁排序后便得到一個有序序列。

?

二、最高位優先(Most Significant Digit first)法

public static void radixSort(int[] data) {//位數if(data.length<2)return;int place = getPlace(data);//位數大于0if (place > 0) {sortUnit(data, 0, data.length, 1, place);}}/*** MSD算法* @param data* @param s 起始位置* @param e 截止位置，是最后一個數據的索引+1* @param curPlace 當前所在數據位置，從左邊開始，起始值為1* @param totalPlace 最大數據的位數*/private static void sortUnit(int[] data, int s, int e, int curPlace, int totalPlace) {//十個桶int[] counts = new int[10];int p;//計算各個桶的數據個數for (int i = s; i < e; i++) {p = getDigit(data[i], curPlace,totalPlace);//獲取數據當前位的值counts[p]++;}//計算各個桶的數據右邊索引界限for (int i = 1; i < counts.length; i++) {counts[i] = counts[i] + counts[i - 1];}//創建數組，將所有桶都存放在這個數組里面int[] bucket = new int[e - s];int dat;//從右往左掃描，保證了算法的穩定性for (int i = e-1; i >=s; i--) {dat = data[i];p = getDigit(dat, curPlace,totalPlace); //獲取數據當前位的值counts[p]--; //找到屬于桶的最后一個位置bucket[counts[p]] = dat;}//將數據回填回dataSystem.arraycopy(bucket, 0, data, s, bucket.length);int start;int end;//根據Ki分組的每個桶都去創建根據Ki+1分組的子桶for (int i = 0; i < counts.length; i++) {start = s + counts[i];//左邊界//右邊界if (i + 1 < counts.length) {end = s + counts[i + 1];} else {end = e;}//桶里數據大于2，基數位置未到Kn,繼續分子桶if (end - start > 1 && curPlace < totalPlace) {sortUnit(data, start, end, curPlace + 1, totalPlace);}}}

?

其他方法調用

/*** 獲取第curPlace位的數值* @param d* @param curPlace* @return */private static int getDigit(int d, int curPlace,int totalPlace) {d=d/((int) Math.pow(10, totalPlace-curPlace));return d % 10;}/*** 獲取元數據的位數** @param data* @return*/private static int getPlace(int[] data) {//null值或者長度為0if (data == null || data.length < 1) {return 0;}if(data.length==1){return String.format("%d", data[0]).length();}int[] mx = getMaxAndMin(data);//最大值的絕對值int max = Math.abs(mx[0]);//最小值的絕對值int min = Math.abs(mx[1]);//最大值的絕對值的十進制位數max = String.format("%d", max).length();//最小值的絕對值的十進制位數min = String.format("%d", min).length();return Math.max(max, min);//最大位數 }/*** 獲取最大和最小值* @param data* @return */public static int[] getMaxAndMin(int[] data) {int[] mx = {Integer.MIN_VALUE, Integer.MAX_VALUE};for (int d : data) {if (mx[0] < d) {mx[0] = d;} else if (mx[1] > d) {mx[1] = d;} }return mx;} View Code

?

三、最低位優先(Least Significant Digit first)法

public static void radixSort(int[] data) {//位數if (data.length < 2) {return;}int place = getPlace(data);//位數大于0for (int i = 0; i < place; i++) {sortUnit(data, i);}}/*** LSD算法** @param data* @param curPlace 當前所在數據位置，從右邊開始，起始值為0*/private static void sortUnit(int[] data, int curPlace) {//十個桶int[] counts = new int[10];int p;//計算各個桶的數據個數for (int i = 0; i < data.length; i++) {p = getDigit(data[i], curPlace);//獲取數據當前位的值counts[p]++;}//計算各個桶的數據右邊索引界限for (int i = 1; i < counts.length; i++) {counts[i] = counts[i] + counts[i - 1];}//創建數組，將所有桶都存放在這個數組里面int[] bucket = new int[data.length];int dat;//從右往左掃描，保證了算法的穩定性for (int i = data.length - 1; i >= 0; i--) {dat = data[i];p = getDigit(dat, curPlace); //獲取數據當前位的值counts[p]--; //找到屬于桶的最后一個位置bucket[counts[p]] = dat;}//將數據回填回dataSystem.arraycopy(bucket, 0, data, 0, bucket.length);}

?

其他方法

/*** 獲取第curPlace位的數值** @param d* @param curPlace 從0開始* @return*/private static int getDigit(int d, int curPlace) {d = d / ((int) Math.pow(10, curPlace));return d % 10;}/*** 獲取元數據的位數** @param data* @return*/private static int getPlace(int[] data) {//null值或者長度為0if (data == null || data.length < 1) {return 0;}if (data.length == 1) {return String.format("%d", data[0]).length();}int[] mx = getMaxAndMin(data);//最大值的絕對值int max = Math.abs(mx[0]);//最小值的絕對值int min = Math.abs(mx[1]);//最大值的絕對值的十進制位數max = String.format("%d", max).length();//最小值的絕對值的十進制位數min = String.format("%d", min).length();return Math.max(max, min);//最大位數 }/*** 獲取最大和最小值** @param data* @return*/public static int[] getMaxAndMin(int[] data) {int[] mx = {Integer.MIN_VALUE, Integer.MAX_VALUE};for (int d : data) {if (mx[0] < d) {mx[0] = d;} else if (mx[1] > d) {mx[1] = d;}}return mx;} View Code

?

四、算法的復雜度

基數排序的算法復雜度，最好時間復雜度、最壞時間復雜度和平均時間復雜度都為O(d(n+r))，空間復雜度為O(n+r)，是穩定的算法。

?

總結

以上是生活随笔為你收集整理的算法九之基数排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。