桶排序是计数排序的升级版. 它利用了函数的映射关系, 高效与否的关键就在于这个映射函数的确定. 为了使桶排序更加高效, 我们需要做到这两点:
在额外空间充足的情况下, 尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时, 对于桶中元素的排序, 选择何种比较排序算法对于性能的影响至关重要.
什么时候最快
当输入的数据可以均匀的分配到每一个桶中.
什么时候最慢
当输入的数据被分配到了同一个桶中.
代码实现
- JavaScript
- function bucketSort(arr, bucketSize) {
- if (arr.length === 0) {
- return arr;
- }
- var i;
- var minValue = arr[0];
- var maxValue = arr[0];
- for (i = 1; i <arr.length; i++) {
- if (arr[i] < minValue) {
- minValue = arr[i]; // 输入数据的最小值
- } else if (arr[i]> maxValue) {
- maxValue = arr[i]; // 输入数据的最大值
- }
- }
- // 桶的初始化
- var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为 5
- bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
- var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
- var buckets = new Array(bucketCount);
- for (i = 0; i <buckets.length; i++) {
- buckets[i] = [];
- }
- // 利用映射函数将数据分配到各个桶中
- for (i = 0; i < arr.length; i++) {
- buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
- }
- arr.length = 0;
- for (i = 0; i < buckets.length; i++) {
- insertionSort(buckets[i]); // 对每个桶进行排序, 这里使用了插入排序
- for (var j = 0; j < buckets[i].length; j++) {
- arr.push(buckets[i][j]);
- }
- }
- return arr;
- }
- Java
- public class BucketSort implements IArraySort {
- private static final InsertSort insertSort = new InsertSort();
- @Override
- public int[] sort(int[] sourceArray) throws Exception {
- // 对 arr 进行拷贝, 不改变参数内容
- int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
- return bucketSort(arr, 5);
- }
- private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
- if (arr.length == 0) {
- return arr;
- }
- int minValue = arr[0];
- int maxValue = arr[0];
- for (int value : arr) {
- if (value < minValue) {
- minValue = value;
- } else if (value> maxValue) {
- maxValue = value;
- }
- }
- int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
- int[][] buckets = new int[bucketCount][0];
- // 利用映射函数将数据分配到各个桶中
- for (int i = 0; i <arr.length; i++) {
- int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
- buckets[index] = arrAppend(buckets[index], arr[i]);
- }
- int arrIndex = 0;
- for (int[] bucket : buckets) {
- if (bucket.length <= 0) {
- continue;
- }
- // 对每个桶进行排序, 这里使用了插入排序
- bucket = insertSort.sort(bucket);
- for (int value : bucket) {
- arr[arrIndex++] = value;
- }
- }
- return arr;
- }
- /**
- * 自动扩容, 并保存数据
- *
- * @param arr
- * @param value
- */
- private int[] arrAppend(int[] arr, int value) {
- arr = Arrays.copyOf(arr, arr.length + 1);
- arr[arr.length - 1] = value;
- return arr;
- }
- }
- PHP
- function bucketSort($arr, $bucketSize = 5)
- {
- if (count($arr) === 0) {
- return $arr;
- }
- $minValue = $arr[0];
- $maxValue = $arr[0];
- for ($i = 1; $i < count($arr); $i++) {
- if ($arr[$i] < $minValue) {
- $minValue = $arr[$i];
- } else if ($arr[$i]> $maxValue) {
- $maxValue = $arr[$i];
- }
- }
- $bucketCount = floor(($maxValue - $minValue) / $bucketSize) + 1;
- $buckets = array();
- for ($i = 0; $i <count($buckets); $i++) {
- $buckets[$i] = [];
- }
- for ($i = 0; $i < count($arr); $i++) {
- $buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];
- }
- $arr = array();
- for ($i = 0; $i < count($buckets); $i++) {
- $bucketTmp = $buckets[$i];
- sort($bucketTmp);
- for ($j = 0; $j < count($bucketTmp); $j++) {
- $arr[] = $bucketTmp[$j];
- }
- }
- return $arr;
- }
- C++
- #include<iterator>
- #include<iostream>
- #include<vector>
- using namespace std;
- const int BUCKET_NUM = 10;
- struct ListNode{
- explicit ListNode(int i=0):mData(i),mNext(NULL){}
- ListNode* mNext;
- int mData;
- };
- ListNode* insert(ListNode* head,int val){
- ListNode dummyNode;
- ListNode *newNode = new ListNode(val);
- ListNode *pre,*curr;
- dummyNode.mNext = head;
- pre = &dummyNode;
- curr = head;
- while(NULL!=curr && curr->mData<=val){
- pre = curr;
- curr = curr->mNext;
- }
- newNode->mNext = curr;
- pre->mNext = newNode;
- return dummyNode.mNext;
- }
- ListNode* Merge(ListNode *head1,ListNode *head2){
- ListNode dummyNode;
- ListNode *dummy = &dummyNode;
- while(NULL!=head1 && NULL!=head2){
- if(head1->mData <= head2->mData){
- dummy->mNext = head1;
- head1 = head1->mNext;
- }else{
- dummy->mNext = head2;
- head2 = head2->mNext;
- }
- dummy = dummy->mNext;
- }
- if(NULL!=head1) dummy->mNext = head1;
- if(NULL!=head2) dummy->mNext = head2;
- return dummyNode.mNext;
- }
- void BucketSort(int n,int arr[]){
- vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
- for(int i=0;i<n;++i){
- int index = arr[i]/BUCKET_NUM;
- ListNode *head = buckets.at(index);
- buckets.at(index) = insert(head,arr[i]);
- }
- ListNode *head = buckets.at(0);
- for(int i=1;i<BUCKET_NUM;++i){
- head = Merge(head,buckets.at(i));
- }
- for(int i=0;i<n;++i){
- arr[i] = head->mData;
- head = head->mNext;
- }
- }
来源: http://www.bubuko.com/infodetail-3314444.html