内容发布更新时间 : 2024/12/23 13:21:14星期一 下面是文章的全部内容请认真阅读。
//还原排好序的数组 int k = 0;
for(List bucket : buckets) { for(int ele : bucket) { arr[k++] = ele; } } }
/**
* 映射函数 * @param x * @return */
public static int f(int x) { return x / 10; } }
基数排序
基数排序又是一种和前面排序方式不同的排序方式，基数排序不需要进行记录关键字之间的比较。基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。所谓的多关键字排序就是有多个优先级不同的关键字。比如说成绩的排序，如果两个人总分相同，则语文高的排在前面，语文成绩也相同则数学高的排在前面。。。如果对数字进行排序，那么个位、十位、百位就是不同优先级的关键字，如果要进行升序排序，那么个位、十位、百位优先级一次增加。基数排序是通过多次的收分配和收集来实现的，关键字优先级低的先进行分配和收集。
举个栗子：
实现代码： /**
*@Description:基数排序算法实现 *@author 王旭 */
public class RadixSort {
public static void radixSort(int[] arr) { if(arr == null & arr.length == 0) return ;
int maxBit = getMaxBit(arr);
for(int i=1; i) {
List> buf = distribute(arr, i); //分配 collecte(arr, buf); //收集 }
}
/**
* 分配
* @param arr 待分配数组 * @param iBit 要分配第几位 * @return */
public static List> distribute(int[] arr, int iBit) { List> buf = new ArrayList>(); for(int j=0; j) {
buf.add(new LinkedList()); }
for(int i=0; i) {
buf.get(getNBit(arr[i], iBit)).add(arr[i]); }
return buf; }
/**
* 收集
* @param arr 把分配的数据收集到arr中 * @param buf */
public static void collecte(int[] arr, List> buf) { int k = 0;
for(List bucket : buf) { for(int ele : bucket) { arr[k++] = ele; } }
}
/**
* 获取最大位数 * @param x
* @return */
public static int getMaxBit(int[] arr) { int max = Integer.MIN_VALUE; for(int ele : arr) {
int len = (ele+\ if(len > max) max = len; }
return max; }
/**
* 获取x的第n位，如果没有则为0. * @param x * @param n * @return */
public static int getNBit(int x, int n) {
String sx = x + \ if(sx.length() n) return 0; else
return sx.charAt(sx.length()-n) - '0'; } } 总结
在前面的介绍和分析中我们提到了冒泡排序、选择排序、插入排序三种简单的排序及其变种快速排序、堆排序、希尔排序三种比较高效的排序。后面我们又分析了基于分治递归思想的归并排序还有计数排序、桶排序、基数排序三种线性排序。我们可以知道排序算法要么简单有效，要么是利用简单排序的特点加以改进，要么是以空间换取时间在特定情况下的高效排序。但是这些排序方法都不是固定不变的，需要结合具体的需求和场景来选择甚至组合使用。才能达到高效稳定的目的。没有最好的排序，只有最适合的排序。
下面就总结一下排序算法的各自的使用场景和适用场合。
从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。
上面说的简单排序包括除希尔排序之外的所有冒泡排序、插入排序、简单选择排序。其中直接插入排序最简单，但序列基本有序或者n较小时，直接插入排序是好的方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。
基数排序的时间复杂度也可以写成O(d*n)。因此它最使用于n值很大而关键字较小的的序列。若关键字也很大，而序列中大多数记录的最高关键字均不同，则亦可先按最高关键字不同，将序列分成若干小的子序列，而后进行直接插入排序。
从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为O(n^2)的简单排序也是稳定的。但是快速排序、堆排序、希尔排序等时间性能较好的排序方法都是不稳定的。稳定性需要根据具体需求选择。
上面的算法实现大多数是使用线性存储结构，像插入排序这种算法用链表实现更好，省去了移动元素的时间。具体的存储结构在具体的实现版本中也是不同的。 附：基于比较排序算法时间下限为O(nlogn)的证明：
基于比较排序下限的证明是通过决策树证明的，决策树的高度Ω（nlgn），这样就得出了比较排序的下限。
首先要引入决策树。 首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。 先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。 具有L片树叶的二叉树的深度至少是logL。 所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以