桶排序

桶排序期望的運行時間是Θ(n)
局限：輸入數組要在[0,1)之間（下面有更通用的版本3??）
1??內置排序沒有用插入排序而是c++自帶的sort，要用插入排序可保證算法穩定性。

void bucket_sort(float *array,int length){vector<vector<float>> bucket(length);for (int i = 0; i < length; ++i) {bucket[(int)(length*array[i])].push_back(array[i]);}for (int i = 0; i < length; ++i) {sort(bucket[i].begin(),bucket[i].end());}int index = 0;for (int i = 0; i < length; ++i) {while (bucket[i].size()>0){array[index] = bucket[i][bucket[i].size()-1];bucket[i].pop_back();index++;}} }

2??對半徑為1的圓周內不包含邊界的點，對離圓心的距離進行排序

void bucket_sort(vector<Vector2>& array) {vector<vector<Vector2>> buckets(array.size());for (int i = 0; i < array.size(); ++i) {buckets[(int)(array[i].module()*array.size())].push_back(array[i]);}for (int i = 0; i < array.size(); ++i) {sort(buckets[i].begin(),buckets[i].end(), compare);}int index = 0;for (int i = 0; i < array.size(); ++i) {while (buckets[i].size()>0){array[index] = buckets[i][buckets[i].size()-1];buckets[i].pop_back();index++;}} }

輔助Vector2類

class Vector2 { public:float x;float y; public:Vector2(float x = 0.0,float y = 0.0);float module() const; }; static bool compare(const Vector2 &item1,const Vector2 &item2) {return item1.module() <= item2.module(); } #include "Vector2.h" Vector2::Vector2(float x,float y):x(x),y(y){} float Vector2::module() const{return sqrt(x*x+y*y); }

3??對變長整數的排序
算法導論第三版8-3a題，變長數據項的排序

void bucket_sort_variable_length(int *array,int length) {vector<vector<int>> positive_bucket(length);vector<vector<int>> negative_bucket(length);for (int i = 0; i < length; ++i) {int len = get_int_length(array[i]);if(array[i]<0){negative_bucket[len-1].push_back(array[i]);}else{positive_bucket[len-1].push_back(array[i]);}}for (int i = 0; i < length -1; ++i) {if(negative_bucket[i].size()>0){radix_sort(negative_bucket[i],i+1);}if(positive_bucket[i].size()>0){radix_sort(positive_bucket[i],i+1);}}int index = 0;for (int i = length -1; i >= 0; --i) {if(negative_bucket[i].size()>0){copy(negative_bucket[i].begin(),negative_bucket[i].end(),array+index);index += negative_bucket[i].size();}}for (int i = 0; i < length -1; ++i) {if(positive_bucket[i].size()>0){copy(positive_bucket[i].begin(),positive_bucket[i].end(),array+index);index += positive_bucket[i].size();}} }

輔助函數 get_int_length

int get_int_length(int value) {int length = 0;while (value != 0){value /=10;length++;}return length == 0 ? 1 : length; }

輔助排序地址
1??基數排序
2??計數排序

4??對變長字符串數組的的排序
算法導論第三版8-3b題，變長數據項的排序

void bucket_sort(vector<string>& array){vector<vector<string>> bucket(26);for (int i = 0; i < array.size(); ++i) {bucket[tolower(array[i][0])-'a'].push_back(array[i]);}sort(bucket.begin(),bucket.end());int index = 0;for (int i = 0; i < 26; ++i) {while (bucket[i].size()>0){array[index] = bucket[i][0];bucket[i].erase(bucket[i].begin());index++;}} }

總結

以上是生活随笔為你收集整理的算法-排序-桶排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。