阿西河

所有教程

公众号
🌙
阿西河前端的公众号

我的收藏

    最近访问  (文章)

      教程列表

      抓包专区
      测试专区

      桶排序

      基本概念

      桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:

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

      参考

      目录
      目录