“线性时间排序（未完，待续）”

发表于 | 分类于 | 本文总阅读量 次

引：排序慢慢来，今天要接触到线性时间排序了：计数排序，基数排序，桶排序。

计数排序

前提条件：知道输入数组的最大值。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] countingsort(int[] a,int k){
//初始化临时数组,k为数组的最大值
int[] c = new int[k+1];
for(int i=0; i<=k; i++) {
c[i]=0;
}
//获得等于i的元素个数
for(int i= 0; i<a.length-1;i++) {
c[a[i]] = c[a[i]]+1;
}
//获得小于等于i的元素个数(隐含了递归调用)
for(int i = 1; i<=k; i++) {
c[i] = c[i] +c[i-1];
}
//按顺序分到输出数组
int[] b = new int[a.length];
for(int i = a.length-1; i>=0; i--) {
b[c[a[i]]] = a[i];
c[a[i]] = c[a[i]]-1;
}
return b;
}

优劣：实现了线性时间，但是空间损失惨重，像是叫你排序这三个数：1，3，1000000000000，马上高低立见。

基数排序

IBM创始人发明，利用进制数的位进行从低到高比较。其中会将原来的数转化为r进制数，使时间复杂度变为线性。
写一下伪代码

1
2
3
redix-sort(A,d)
for i = 1 to d
use a stable sort to sort array A on digit i

桶排序

桶排序假设数据服从均匀分布，讲一个区间分成若干个桶，先将数据放到桶中分开排序再合并。
伪代码如下

1
2
3
4
5
6
7
8
9
10
bucket-sort(A)
n = A.length
let B[0.. n-1] be a new array
for i = 0 to n - 1
make  B[i] an empty list
for i = 1 to n
insert A[i] into list B[nA[i]]
for i = 0 to n - 1
sort list B[i] with insertion sort
concatenete the lists B[0],B[1].. B[n-1] together in order

它的期望时间为线形。

总结

其中对于基数排序和桶排序理解得不是很好，需要加深理解，写出具体实现代码，未完，待续…