十大排序 —— 桶排序

我们今天来接着来看桶排序：

什么是桶排序

桶排序（Bucket Sort）是一种分布式排序算法，它将待排序的数组分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序的工作原理如下：

1. 初始化：首先确定桶的数量和大小，理想情况下桶的数量与待排序数组中的最大值和最小值的范围相关，且各个桶之间是互斥的。例如，如果数组中的元素范围是0到100，可以创建100个桶，每个桶负责收集一个数值范围内的元素。

2. 分配：遍历原始数组，将每个元素放入对应的桶中。这个过程通常是通过计算元素值与桶区间的关系来决定元素应归属的桶。例如，如果数组元素是0到1之间的浮点数，可以将它们乘以桶的数量然后取整，以此作为桶的索引来分配元素。

3. 桶内排序：对于每个非空的桶，单独对桶内的元素进行排序。这一步可以使用任何有效的排序算法，比如插入排序、快速排序等。如果桶内元素数量很少，插入排序往往是一个不错的选择。

4. 收集：按顺序遍历所有的桶，将桶中的元素依次取出并合并成一个有序数组。这一步是线性的，只需将各桶的元素依次连接起来即可。

桶排序的优点是，当输入数据均匀分布在桶中时，排序效率非常高，时间复杂度接近O(n)，其中n是数组长度。然而，如果数据分布极不均匀，桶排序的效率会大大降低，最坏情况下的时间复杂度接近O(n^2)，特别是当所有元素都落在同一个桶中时。

桶排序适用于数据范围明确且分布较为均匀的情况，比如在处理大量浮点数排序时，若这些浮点数的分布已知且较为集中，桶排序可以发挥很好的效果。

我们先来一个版本：

// 选取最大的数据作为新数组的大小
int size = sizeof(score) / sizeof(score[0]);
int max = score[0];
for (int i = 0; i < size; i++) {
    if (score[i] > max) {
        max = score[i];
    }
}

// 开辟数组，并初始化所有对应下标储存元素为0
std::vector<int> newArray(max + 1, 0);

for (int j = 0; j < size; j++) {
    newArray[score[j]]++;
}

// 遍历数组
for(int i = 0; i <= max; i++) {
    // 对应元素的打印次数
    for (int j = 0; j < newArray[i]; j++) {
        std::cout << i << " ";
    }
}

int main()
{
    int a1[] = { 92,84,99,81,77,100,102,113,100 };
   
    buckets_sort(a1,sizeof(a1)/sizeof(a1[0]));

}

还有例外一个版本，这个版本，是每个位置都是一个桶，不是标记次数：

void buckets_sort(vector<int>& array) {
    // 首先寻找数组中的最大元素，以确定桶的数量
    int Max = array[0];
    for(int i = 1; i < array.size(); i++) {
        if(array[i] > Max) {
            Max = array[i]; // 更新最大值
        }
    }

    // 根据最大值开辟空间，创建相应数量的桶，注意索引从0开始，所以桶的大小为Max + 1
    vector<vector<int>> buckets;
    buckets.resize(Max + 1);

    // 遍历原数组，将每个元素放入对应的桶中，元素值即为其所在桶的索引
    for(auto num : array) {
        buckets[num].push_back(num); // 将num放入其值对应的桶内
    }

    // 对每个桶内的元素进行排序，这里使用了std::sort，实际可以根据情况选择不同的排序算法
    for (auto& bucket : buckets) {
        std::sort(bucket.begin(), bucket.end()); // 对桶内元素进行排序
    }

    // 收集排序后的元素回到原数组
    int index = 0;
    for(auto& bucket : buckets) {
        for(auto number : bucket) {
            array[index++] = number; // 依次将排序后的元素放回原数组
        }
    }
}
}

int main()
{
    vector<int> a2 = { 77,92,84,99,81,77,100,102,113,100 };
  
    buckets_sort(a2);

    for(auto e : a1)
   {
       cout << e << " ";
   }
}

这个方法有点像哈希表的拉链法，只不过我们对桶的内部进行了排序。

这里有两道例题：

字符串中的第一个唯一字符

https://leetcode.cn/problems/first-unique-character-in-a-string/

这道题就非常适合用桶排序：

class Solution {
public:
    int firstUniqChar(string s) 
    {
        int arrayA[26]={0};

        for(int i = 0;i<s.size();i++)
        {
            arrayA[s[i]-'a']++;
        }

        for(int i = 0;i<s.size();i++)
        {
            if(arrayA[s[i]-'a']==1)
            {
                return i;
            }
        }

    return -1;
    }
};

数组的相对排序

https://leetcode.cn/problems/relative-sort-array/

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) 
    {
        //寻找最大数
        int max = 0;
        for(int i = 0;i < arr1.size(); i++)
        {
            max = fmax(max,arr1[i]);
        }

        //开辟第一个数组
        vector<int> Array1(max + 1);

        for(auto number : arr1)
        {
            Array1[number]++;
        }

        //开辟第二个数组
        vector<int> Array2(arr1.size());

        int x = 0;
        for(auto index : arr2)
        {
            while(Array1[index]!=0)
            {
                Array2[x++] = index;
                Array1[index]--;
            }
        }

        //没出现在arr2中元素，需要再次遍历一遍，放在数组最后面
        for(int i = 0; i < max + 1; i++)
        {
            for(int j = 0; j< Array1[i]; j++)
            {
                Array2[x++] = i;
            }
        }

        return Array2;
        
    }
};