C/C++桶排序

C/C++桶排序

桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。简言之，将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。

算法描述

• 设置一个定量的数组当作空桶子。
• 寻访序列，并且把项目一个一个放到对应的桶子去。
• 对每个非空的桶子进行排序。
• 从不是空的桶子里把项目再放回原来的序列中。

动态演示

代码实现

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;void insert_sort(vector<int>& arr) {int n = arr.size();int j = 0, cur = 0;for (int i = 1; i < n; i++) {cur = arr[i];j = i - 1;//进行比较，插入while (j >= 0 && arr[j] > cur) {arr[j + 1] = arr[j];j--;}arr[j+1] = cur;}
}
void bucket_sort(vector<int>& arr) {if (arr.size() == 0) return;int minvalue = arr[0];int maxvalue = arr[0];for (int i = 1; i < arr.size(); i++) {if (arr[i] < minvalue) {minvalue = arr[i];                // 输入数据的最小值}else if (arr[i] > maxvalue) {maxvalue = arr[i];                // 输入数据的最大值}}//桶进行初始化int DEFAULT_BUCKET_SIZE = 5;              // 桶的大小的默认为5int bucketCount = (maxvalue - minvalue) / DEFAULT_BUCKET_SIZE + 1;  //计算桶的数量vector<vector<int>> buckets(bucketCount, vector<int>());// 利用映射函数将数据分配到各个桶中for (int i = 0; i < arr.size(); i++) {buckets[(arr[i] - minvalue) / DEFAULT_BUCKET_SIZE].push_back(arr[i]);}int index = 0;for (int i = 0; i < buckets.size(); i++) {insert_sort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序for (int j = 0; j < buckets[i].size(); j++) {arr[index++] = buckets[i][j];}}
}
void print_arr(vector<int>& arr) {int n = arr.size();for (int i = 0; i < n; i++) {cout << arr[i] << "  ";}cout << endl;
}
int main() {vector<int> arr = { 9,15,64,6,18,214,1,64,46,12,55,3,815,7,4,12,5,3,1 };cout << "排序前：" << endl;print_arr(arr);bucket_sort(arr);cout << "排序后：" << endl;print_arr(arr);system("pause");return 0;
}

结果输出

桶排序，网上版本比较多，各种都不相同，我也比较迷糊。但是总体思想应该是没问题的，如果有错误，希望大家及时指出。