sort:让计数排序适用性更广吧

计数排序的时间复杂度很低，但是，能够应用的场合就很少了。这个时候，我们就需要对计数排序进行升级

---

根据计数排序的思想，他对于集合当中的每一个元素都进行标记，最后，按照标记数组的标记数量进行元素的输出就可以达成排序的效果了。但是，这个排序方式有一个比较局限的地方，那就是，一旦集合中的元素拥有浮点数之类的无法被数组下标所量化标记的时候，计数排序就失去其效果了。

这个时候，我们就需要引入一些辅助的手段，那就是桶(bucket)，而这个升级过后的排序方式就叫做桶排序

首先，先来介绍一下什么是桶

每一个桶代表着一个区间范围，比如对于以下的元素

4.5 0.84 3.25 2.18 0.5

bucket: [0.5,1.5)
	[1.5,2.5)
	[2.5,3.5)
	[3.5,4.5)
	[4.5,4.5]

至于桶具体有多少个，如何确立桶的范围，方法有很多，在这里，桶的区间范围=(最大值-最小值)/(桶的数量-1)

然后，我们将具体的元素都放到对应区间的桶当中

bucket: [0.5,1.5)  0.5,0.84
	[1.5,2.5)  2.18
	[2.5,3.5)  3.25
	[3.5,4.5)  
	[4.5,4.5]  4.5

由于，仅仅只是放入桶当中，桶中的元素是没有经过排序的，因为，下一步就是对每个桶里面的元素进行排序

最终，以此输出桶中的元素

   vector<int> sortArray(vector<int>& nums) {
       if(nums.empty())
           return{};
       //step1:找出最大值
       int max = nums[0],min = nums[0];
       for(int i = 1;i < nums.size();i++)
       {
           if(max < nums[i])
               max = nums[i];
           if(min > nums[i])
               min = nums[i];
       }
//step2:建立桶并将元素加入桶中
       vector<vector<int>> buckets(max - min + 1);
       for(int i : nums)
           buckets[i - min].push_back(i);
//step3:对桶内元素进行排序
       for(auto& vec : buckets)
           sort(vec.begin(),vec.end());
//step4:按顺序输出桶内的内容
       vector<int> res;
       for(int i = 0;i < buckets.size();i++)
           for(int j = 0;j < buckets[i].size();j++)
               res.push_back(buckets[i][j]);

       return res;
   }

可见，桶排序的基本思想和计数排序差不多，都是对元素本身的位置进行标记，而不是直接对元素进行交换排序。而再使用了大量的桶的情况下，更加的可以减少排序算法当中需要排序的元素的个数(假如元素在桶中分布比较均匀的时候，基本上是不需要使用到排序算法对桶内元素进行排序的)

桶排序的时间复杂度就比较复杂了，首先要算出最大最小值，需要耗费时间n，然后，要创建空桶m个，遍历数组将元素放入桶中耗时n，然后每一个桶内都得进行排序，为了要快，桶内元素的排序算法应该是O(nlogn)的，因此运算量为m (n/m log(n/m)),最后要输出数组耗时n

总的来说就是3n+m+n(logn-logm),也就是O(n+m+n(logn-logm))
而空间复杂度则是O(n+m)，在这里使用的sort其实就是一种快速排序，那么空间就是O(n)了

不过，当元素在桶内比较平均分布的时候，也就是n=m的时候，时间复杂度就变成O(n)了，而假如，大量元素都集中在一个桶当中的时候，时间复杂度将会退化到O(nlogn)，并且，白白浪费了空间去创建大量的桶