桶排序---

1、算法概念

桶排序：一种非比较的排序算法。桶排序采用了一些分类和分治的思想，把元素的值域分成若干段，每一段对应一个桶。在排序的时候，首先把每一个元素放到其对应的桶中，再对每一个桶中的元素分别排序，再按顺序把每个桶中的元素依次取出，合并成最终答案。

2、步骤

1. 将值域分成瑞杆端，每段对应一个桶
2. 将待排序元素放入对应的桶中
3. 将个桶内的元素进行排序
4. 将桶中的元素一次取出

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