桶排序---

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>10^{7}a_i{}<10^{^{6}},可以做到每个值对应一个桶,桶排序的时间复杂度为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

上一篇:算法刷题记录 Day34


下一篇:蓝桥杯刷题day12——元素交换【算法赛】