桶排序

定义

---

桶排序

桶排序将要排序的元素放到不同的桶中，再对各个桶进行排序，最后从桶中取出元素组成排好的序列。若元素均匀地放到了各个桶中，则桶内排序使用插入排序会更高效。若桶内元素分布不均匀，如全部元素都放到了同一个桶中，则复杂度退化到桶内排序算法的复杂度。

实现

---

int MAX_N, n, w, a[MAX_N];  
vector<int> bucket[N];  
  
void insertion_sort(vector<int> a)  
{  
    for (int i = 1; i < a.size(); i++)  
    {  
       int key = a[i];  
       int j = i - 1;  
       while (j >= 0 && a[j] > key)  
       {  
          a[j + 1] = a[j];  
          j--;  
       }  
       a[j + 1] = key;  
    }  
}  
  
void bucket_sort()  
{  
    int bucket_size = N / n + 1; // 将值域划分为 n 个桶  
    for (int i = 0; i < n; i++)  
       bucket[a[i] / bucket_size].emplace_back(a[i]); // 将元素放入对应的桶中  
    int cnt = 0;  
    for (int i = 0; i < N; i++)  
    {  
       insertion_sort(bucket[i]); // 对每个桶进行插入排序  
       for (int j = 0; j < bucket[i].size(); j++)  
          a[cnt++] = bucket[i][j];  
    }  
}