web中桶排序的示例分析

桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。

为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。 1. 什么时候最快 当输入的数据可以均匀的分配到每一个桶中。 2. 什么时候最慢 当输入的数据被分配到了同一个桶中。 3. 示意图 元素分布在桶中： 然后，元素在每个桶中排序：

代码实现

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 if (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 for (i = 0; i for (i = 0; i for (var j = 0; 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 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 for (int[] bucket : buckets) {           if (bucket.length 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 $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 $buckets); $i++) {       $buckets[$i] = [];   }   for ($i = 0; $i $arr); $i++) {       $buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];   }   $arr = array();   for ($i = 0; $i $buckets); $i++) {       $bucketTmp = $buckets[$i];       sort($bucketTmp);       for ($j = 0; $j $bucketTmp); $j++) {           $arr[] = $bucketTmp[$j];       }   }   return $arr;}

C++

实例

#include#include#includeusing 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->mDatamNext;       }       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 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 buckets(BUCKET_NUM,(ListNode*)(0));       for(int i=0;imData;               head = head->mNext;       }}