1、算法概念
桶排序:一种非比较的排序算法。桶排序采用了一些分类和分治的思想,把元素的值域分成若干段,每一段对应一个桶。在排序的时候,首先把每一个元素放到其对应的桶中,再对每一个桶中的元素分别排序,再按顺序把每个桶中的元素依次取出,合并成最终答案。
2、步骤
- 将值域分成瑞杆端,每段对应一个桶
- 将待排序元素放入对应的桶中
- 将个桶内的元素进行排序
- 将桶中的元素一次取出
C++语言
桶中只有一种数值
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 7;
int n;
int bucket[MAXN];//一个值对应一个桶
int main() {
cin >> n ;
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
//由于每个桶中只有一个值,我们只需要记录桶中的元素个数
bucket[x]++;
}
for(int i = 0; i <= n; i++){
//值为i的元素有bucket[i]个
for (int j = 0; j <= bucket[i]; ++j) {
cout << i << " ";
}
}
cout << endl;
}
桶中有多种数值
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 7;
int n;
vector<int> bucket[MAXN];
int main() {
cin >> n ;
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
bucket[x / 1000].push_back(x);
}
for(int i = 0;i < MAXN;i++){
//对每个桶的操作
}
for(int i = 0; i < MAXN; i++){
for (auto item : bucket[i]) {
cout << item << " ";
}
}
cout << endl;
}
Java语言
import java.util.*;
public class Main {
private static final int MAXN = 500007;
private static int[] bucket = new int[MAXN];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 1; i <= n; i++) {
int x = scanner.nextInt();
bucket[x]++;
}
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= bucket[i]; j++) {
System.out.print(i + " ");
}
}
System.out.println();
scanner.close();
}
}
import java.util.*;
public class Main {
private static final int MAXN = 500007;
private static List<Integer>[] bucket = new ArrayList[MAXN];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 0; i < MAXN; i++) {
bucket[i] = new ArrayList<>();
}
for (int i = 1; i <= n; i++) {
int x = scanner.nextInt();
bucket[x / 1000].add(x);
}
for (int i = 0; i < MAXN; i++) {
Collections.sort(bucket[i]);
}
for (int i = 0; i < MAXN; i++) {
for (int item : bucket[i]) {
System.out.print(item + " ");
}
}
System.out.println();
scanner.close();
}
}
3、桶排序的优势
- 对于数据量较大但值域较小的数据,如n>,<,可以做到每个值对应一个桶,桶排序的时间复杂度为O(n)。推荐使用桶排序。
- 对于值域较小的数据,桶排序的时间复杂度与每个桶内排序的方法有关,优势不明显,对于这种数据一般不适用桶排序。
例题---计数排序
https://www.lanqiao.cn/problems/1314/learning/
给定一个长度为n的数组a,请你将a排完序后输出。
输入描述:
第一行包含一个整数n,表示数组a的长度。
第二行包含n个整数,分别表示a1~an。
输出描述:
输出共一行,包含n个整数,表示排完序后的数组a。
示例:5
4 3 2 1 5 1 2 3 4 5