十大经典排序算法总结（含Java代码实现）

10.3 代码实现

/** 
 * 基数排序 
 * @param array 
 * @return 
 */ 
 public static int[] RadixSort(int[] array) { 
 if (array == null || array.length < 2) 
 return array; 
 // 1.先算出最大数的位数； 
 int max = array[0]; 
 for (int i = 1; i < array.length; i++) { 
 max = Math.max(max, array[i]); 
 } 
 int maxDigit = 0; 
 while (max != 0) { 
 max /= 10; 
 maxDigit++; 
 } 
 int mod = 10, div = 1; 
 ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>(); 
 for (int i = 0; i < 10; i++) 
 bucketList.add(new ArrayList<Integer>()); 
 for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) { 
 for (int j = 0; j < array.length; j++) { 
 int num = (array[j] % mod) / div; 
 bucketList.get(num).add(array[j]); 
 } 
 int index = 0; 
 for (int j = 0; j < bucketList.size(); j++) { 
 for (int k = 0; k < bucketList.get(j).size(); k++) 
 array[index++] = bucketList.get(j).get(k); 
 bucketList.get(j).clear(); 
 } 
 } 
 return array; 
 } 

10.4 算法分析

最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)

基数排序有两种方法：

• MSD 从高位开始进行排序
• LSD 从低位开始进行排序

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶
• 计数排序：每个桶只存储单一键值
• 桶排序：每个桶存储一定范围的数值

（编辑：晋中站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!