1. 描述
对于待排序的base进制的一维数组。建立base(0~base - 1)个桶。
第digit轮, 根据 val % (base << (digit))将数据放入桶中,放桶时插入排序, 直到所有数据都放在了0号桶。
2. 代码
#include <iostream>
#include <algorithm>
struct bucket{
explicit bucket(int val = 0,struct bucket *next = nullptr):val_(val),next_(next)
{}
~bucket()
{ }
void insert(struct bucket *ins)
{
struct bucket *cur = this;
while (cur->next_ && ins->val_ >= cur->next_->val_)
cur = cur->next_;
ins->next_ = cur->next_;
cur->next_ = ins;
}
int nodeNum() const
{
int cnt = 0;
auto cur = this;
while (cur->next_) {
++cnt;
cur = cur->next_;
}
return cnt;
}
int val_;
struct bucket *next_;
};
int put2arr(int *arr, struct bucket *bucketArr, int base)
{
int bucketNum = 0;
int idx = 0;
for ( int i = 0; i < base; ++i) {
struct bucket *cur = &bucketArr[i];
if ( cur && cur->next_) {
++bucketNum;
cur = cur->next_;
while (cur) {
arr[idx++] = cur->val_;
cur = cur->next_;
}
}
bucketArr[i].next_ = nullptr;
}
return bucketNum;
}
void radixSort(int *arr, int len, int base)
{
if ( !len || !arr || (base < 0 || base > 16) )
return ;
auto bucketArr = new bucket[base];
auto dataArr = new bucket[len];
int nonEmptyCnt = 0;
int modNum = 1;
while ( nonEmptyCnt != 1) {
for (int i = 0;i < base;++i)
bucketArr[i].next_ = nullptr;
for (int i = 0; i < len; ++i) {
int bucketIdx = arr[i] / modNum % 10;
dataArr[i].val_ = arr[i];
dataArr[i].next_ = nullptr;
bucketArr[bucketIdx].insert(&dataArr[i]);
}
nonEmptyCnt = put2arr(arr, bucketArr, base);
modNum *= 10;
}
put2arr(arr, bucketArr, base);
for (int i = 0; i < len; ++i)
dataArr[i].next_ = nullptr;
delete []bucketArr;
delete []dataArr;
}
int main()
{
std::cout << "Hello, World!" << std::endl;
int arr[] = { 21,9, 1234, 19, 0, 8, 20, 11};
int len = static_cast<int>(sizeof(arr)/sizeof(arr[0]));
std::cout << len << std::endl;
radixSort( arr, len, 10);
for ( int i = 0; i < len; ++i)
std::cout << arr[i] << "\t";
std::cout << std::endl;
return 0;
}
3. 理解
k
次bucketsort
,和将桶内数据放回原数组。
k
=
f
l
o
o
r
(
l
o
g
b
a
s
e
(
m
a
x
V
a
l
)
)
‘
k = floor(log_{base}(maxVal))`
k=floor(logbase(maxVal))‘文章来源:https://www.toymoban.com/news/detail-469110.html
4. Ref
GeekForGeek文章来源地址https://www.toymoban.com/news/detail-469110.html
到了这里,关于基数排序--C++实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!