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;
       }
}