- 1.桶排序(Bucket sort)
- 1.1 是否可以替代之前的排序算法
- 1.2 桶排序比较适合用在外部排序中。
- 2. 计数排序(Counting sort)
- 3. 基数排序(Radix sort)
- 4. 解答开篇
问题: 如何根据年龄给100万用户排序?
1.桶排序(Bucket sort)把要排序的数据分到几个有序的桶,每个桶里的数据再单独进行排序,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。
时间复杂度:O(n)
n个数据,均分到m个桶,每个桶k=n/m个元素。 每个桶用快速排序,时间复杂度为O(k * logk)。m个桶排序的时间复杂度就是O(m * k * logk)。因为k=n/m,所以桶排序的时间复杂度就是O(n*log(n/m)),当m接近n时,接近O(n)。
否。
- 数据要很容易分成m个桶,桶与桶有天然的大小关系,
- 各个桶数据要比较均分,极端情况,如果数据都在一个桶,就退化成O(nlogn).
外部排序:内存有限,无法装载全部数据。
比如:订单数据有10个G,内存只有几百兆,想根据订单金额排序,怎么办?
先扫描一遍,获取最大最小金额,根据金额,分割成若干个桶,放入订单数据,如果某个桶还是大于内存,继续分割桶。
2. 计数排序(Counting sort)要排序的n个值,值范围不大,最大为k,直接分成k个桶。时间复杂度是O(n)
什么样的数据适合计数排序,比如高考成绩,人的年龄。
原理:8个考生,分数在0到5分之间。
成绩A[8]: 2,5,3,0,2,3,0,3
分数C[6]:下标位分数,保存小于等于分数k的考生个数。
算法过程:
// 计数排序,a是数组,n是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
if (n <= 1) return;
// 查找数组中数据的范围
int max = a[0];
for (int i = 1; i < n; ++i) {
if (max < a[i]) {
max = a[i];
}
}
int[] c = new int[max + 1]; // 申请一个计数数组c,下标大小[0,max]
for (int i = 0; i <= max; ++i) {
c[i] = 0;
}
// 计算每个元素的个数,放入c中
for (int i = 0; i < n; ++i) {
c[a[i]]++;
}
// 依次累加
for (int i = 1; i <= max; ++i) {
c[i] = c[i-1] + c[i];
}
// 临时数组r,存储排序之后的结果
int[] r = new int[n];
// 计算排序的关键步骤,有点难理解
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1;
r[index] = a[i];
c[a[i]]--;
}
// 将结果拷贝给a数组
for (int i = 0; i < n; ++i) {
a[i] = r[i];
}
}
3. 基数排序(Radix sort)
10万个手机号码,如何快速排序?有没有时间复杂度是O(n)的算法呢?
借助稳定排序算法,从后往前比较每一位的数据,然后排序。
利用桶排序或计数排序,复杂度可以降到O(n),因为有k位,所以实际是O(k*n),但k比较小,接近O(n)。
如果比较单词怎么办? 位数不够补"0".
基数排序的要求:可以分割出独立的“位”来比较,有递进的关系,如果a数据的高位比b数据大,那剩下的低位就不用比较了。每一位数据范围不能太大,可以利用桶排序或计数排序。
4. 解答开篇设置1岁到120岁的桶,遍历一遍放入相应的桶即可。



