前言
首先这里列出的大家熟知的排序算法：冒泡排序、插入排序、归并排序、堆排序、快速排序等。对于能在O(n lgn)时间内进行排序的算法，归并排序和堆排序达到了最坏的情况下的上界；快速排序在平均情况下达到了该上界。
这些算法都有一个共同点：在排序的最终结果中，各元素的次序依赖于它们之间的比较。我们称这类排序算法为比较排序。
比较排序在排序的排序过程可以抽象成一棵决策树。在最坏的情况下，任何比较排序算法都需要做Ω（n lgn）次比较。
线性时间排序
下面介绍两种线性时间排序的算法：计数排序、基数排序。
计数排序
计数排序假设n个输入的元素中每一个都是在[0，k]区间内的一个整数，其中k为某个整数。当k=O(n)时，排序的运行时间为θ(n)。
计数排序执行过程：
- 开辟计数数组空间，并遍历待排序数组对带排序数组进行计数赋值；
- 对计数数组进行叠加操作，得到元素所在的最后的位置；
- 遍历待排序数组，根据得出的计数数组完成输出数组的赋值；
计数排序图例
计数排序Java 代码：
/**
*
* @param a 数组
* @param k 范围;例如 k equals 5 ,range is [0,4]
*/
public void countingSort(int[] a,int[] b,int k) {
if(k<0||(a==null||a.length<1)) return;
int[] c=new int[k];
//counting
for(int j=0;j<a.length;j++) {
c[a[j]]+=1;
}
//convert
for(int i=1;i<k;i++) {
c[i]=c[i]+c[i-1];
}
for(int j=(a.length-1);j>=0;j--) {
b[c[a[j]]-1]=a[j];
c[a[j]]-=1;
}
}
测试代码：
public static void main(String[] args) {
//假设a数组中的数都是[0,10)之间的数
int[] a= {4,6,3,3,2,2,9,0,1,4,4,8,7,7};
//排序数组
int[] b=new int[a.length];
new RadixSort().countingSort(a, b, 10);
for(int i=0;i<b.length;i++) {
System.out.println(i+" is "+b[i]);
}
}
测试结果：
0 is 0
1 is 1
2 is 2
3 is 2
4 is 3
5 is 3
6 is 4
7 is 4
8 is 4
9 is 6
10 is 7
11 is 7
12 is 8
13 is 9
基数排序
基数排序是先按最低有效位进行排序解决排序问题，算法用到了稳定排序算法-计数排序。
基数排序的伪代码很简单：
RADIX_SORT(A,d)
for i =1 to d
use a stable sort to sort array A on digit i;
基数排序排序过程
基数排序Java 代码：
/**
* 10的次方数的结果值
* @param d 次方数
* @return 10的n次方的结果
*/
private int tenPow(int d) {
int result=1;
for(int i=0;i<d;i++) {
result*=10;
}
return result;
}
/**
* 为计数排序优化的计数排序
* @param a 待排序数组
* @param b 输出的数组
* @param k 范围;例如 k equals 5 ,range is [0,9]
*/
public void countingSort4Radix(int[] a,int[] b,int k) {
if(k<0||(a==null||a.length<1)) return;
int[] temps=new int[a.length];
for(int x=0;x<temps.length;x++) {//copying
temps[x]=b[x];
}
int[] c=new int[k];
//counting
for(int j=0;j<a.length;j++) {
c[a[j]]+=1;
}
//convert
for(int i=1;i<k;i++) {
c[i]=c[i]+c[i-1];
}
for(int j=(a.length-1);j>=0;j--) {
b[c[a[j]]-1]=temps[j];
c[a[j]]-=1;
}
}
/**
* 基数排序
* @param a 待排序数组
* @param d 位数 如：834102 d eauals 6
*/
public void radixSort(int[] a,int d) {
//存放相应位数据的临时数组
int[] digitsTemp=new int[a.length];
for(int j=0;j<d;j++) {
//1.为相应位赋值
for(int i=0;i<digitsTemp.length;i++) {
digitsTemp[i]=(a[i]/tenPow(j))%10;
System.out.println((j+1)+"位："+"digitsTemp["+i+"] is "+ digitsTemp[i]);
}
//2.使用稳定的计数排序算法进行从低位到高位的按位排序
countingSort4Radix(digitsTemp, a, 10);
for(int x=0;x<a.length;x++) {
System.out.println(" radixing->"+x+" is "+a[x]);
}
}
}
测试代码：
public static void main(String[] args) {
int[] x= {834102,634101,834112,512311};
new RadixSort().radixSort(x, 6);
System.out.println("-------基数排序的结果-------");
for(int i=0;i<x.length;i++) {
System.out.println(i+" is "+x[i]);
}
}
测试结果：
1位：digitsTemp[0] is 2
1位：digitsTemp[1] is 1
1位：digitsTemp[2] is 2
1位：digitsTemp[3] is 1
radixing->0 is 634101
radixing->1 is 512311
radixing->2 is 834102
radixing->3 is 834112
2位：digitsTemp[0] is 0
2位：digitsTemp[1] is 1
2位：digitsTemp[2] is 0
2位：digitsTemp[3] is 1
radixing->0 is 634101
radixing->1 is 834102
radixing->2 is 512311
radixing->3 is 834112
3位：digitsTemp[0] is 1
3位：digitsTemp[1] is 1
3位：digitsTemp[2] is 3
3位：digitsTemp[3] is 1
radixing->0 is 634101
radixing->1 is 834102
radixing->2 is 834112
radixing->3 is 512311
4位：digitsTemp[0] is 4
4位：digitsTemp[1] is 4
4位：digitsTemp[2] is 4
4位：digitsTemp[3] is 2
radixing->0 is 512311
radixing->1 is 634101
radixing->2 is 834102
radixing->3 is 834112
5位：digitsTemp[0] is 1
5位：digitsTemp[1] is 3
5位：digitsTemp[2] is 3
5位：digitsTemp[3] is 3
radixing->0 is 512311
radixing->1 is 634101
radixing->2 is 834102
radixing->3 is 834112
6位：digitsTemp[0] is 5
6位：digitsTemp[1] is 6
6位：digitsTemp[2] is 8
6位：digitsTemp[3] is 8
radixing->0 is 512311
radixing->1 is 634101
radixing->2 is 834102
radixing->3 is 834112
-------基数排序的结果-------
0 is 512311
1 is 634101
2 is 834102
3 is 834112
总结
- 计数排序 适用于k比较小的场景下，比如“某大型企业有两万名员工，希望根据年龄为员工们排序，并计算平均年龄？”，这个问题在不使用数据库和磁盘相关算法（B树）的前提下，计数排序是较优的解决方案。
- 基数排序是一种原地排序算法，不需要额外的空间进行辅助；但是我的代码中计数排序是还是开辟了空间，这是一个值得优化的点。
以上，谢谢阅读，希望你有所收获！
算法导论公开课笔记（一）算法分析与设计
算法导论公开课笔记（二）快速排序和随机化算法
算法导论公开课笔记（三）线性时间排序
算法导论公开课笔记（四）顺序统计、中值
动态规划算法
竟然有人，为这个文章赞赏了￥2.0，虽然写博客的目的不是为了挣钱，但是也好开心！！！
谢谢匿名的大神的鼓励，事事顺利！
网友评论