桶排序
【注】参考自教材「算法导论」。
1. 简介
桶排序是将待排序序列分到有限数量的桶中，然后对每一个桶分别进行排序。桶排序的前提假设为被排序序列的关键字数值符合均匀分布，此时桶排序的平均时间复杂度为 O(n + {n^2 \over k} + k)，最坏时间复杂度为 O(n^2)，其中 k 为桶的数量。当桶数量k \approx n时，此时桶排序的复杂度为线性复杂度 O(n) 。
桶排序是非原址的，其稳定性取决于内层排序的稳定性。一般采用稳定的插入排序作为内层排序算法，此时桶排序是稳定的。
2. 思想
桶排序的主要思想是对待排序序列的关键字数值进行分块，每一块对应一个桶，然后对每个桶使用插入排序（或其他排序算法）进行排序，最后将所有桶中的元素串联起来即得到有序序列。
3. 实现
3.1 伪代码
BucketSort(A, mx, n) {
// mx 为最大数值，n 为桶数量
// 定义 n 个桶
define bucket[n]
// 计算分块的块大小
bucketsize = mx/n + 1
// 根据元素的排序关键字数值分块
for i = 1 to A.length
bucket[A[i]/bucketsize].PushBack(A[i])
for i = 0 to n-1
InsertSort(bucket[i])
cnt = 0
for i = 0 to n-1
for j = 1 to bucket[i].length
A[++cnt] = bucket[i][j]
}3.2 模板
#include <bits/stdc++.h>
using namespace std;
#ifndef _BUCKET_
#define _BUCKET_
#define ll int
#define MAXN 100005
#define MAXBUK 1000
#define INF 10000000
// 桶排序
template < typename T >
struct Bucket {
vector < pair<T, ll> > bucket[MAXN];
Bucket() {}
// 插入排序
void insertSort(vector < pair<T, ll> > & bkt) {
for(ll i = 1; i < bkt.size(); ++i) {
pair <T, ll> key = bkt[i];
ll j = i - 1;
while(~j && bkt[j].second > key.second) {
bkt[j+1] = bkt[j];
j--;
}
bkt[j+1] = key;
}
}
// 桶排序
void bucketSort(T *bA, T *eA, ll *bK, ll *eK, ll mx = INF, ll bn = MAXBUK) {
ll len_A = eA - bA;
ll len_K = eK - bK;
T *A = bA;
ll *K = bK;
ll bucketsize = mx/bn + 1;
// 判断关键字数组大小与元素数组大小是否吻合
assert(len_A == len_K);
// 初始化桶
for(ll i = 0; i < bn; ++i) {
bucket[i].clear();
}
// 将元素放入桶中
for(ll i = 0; i < len_K; ++i) {
bucket[K[i]/bucketsize].push_back(pair<T, ll>{A[i], K[i]});
}
// 对每一个桶进行插入排序
ll cnt = 0;
for(ll i = 0; i < bn; ++i) {
insertSort(bucket[i]);
for(ll j = 0; j < bucket[i].size(); ++j) {
A[cnt++] = bucket[i][j].first;
}
}
}
};
#endif本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-08-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录